1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,int> PLI;

struct Cand{
    int len_up;
    int len_down;
    int max_len;
};

const int INF=1e9;

int A[300005];
int B[300005];
long long res[600005];

vector<Cand> dp[405][405][2];
int tmp_down[1005];
int tmp_up[1005];

void compress(vector<Cand> & c){
    if(c.size() < 4) return;
    vector<Cand> ans;
    int max_len = 0;
    for(const Cand & u: c){
        if(u.len_up == 1){
            tmp_down[u.max_len] = min(tmp_down[u.max_len], u.len_down);
        }
        else{
            tmp_up[u.max_len] = min(tmp_up[u.max_len], u.len_up);
        }
    }
    for(const Cand & u: c){
        if(u.len_up == 1 && tmp_down[u.max_len] != INF){
            ans.push_back({1, tmp_down[u.max_len], u.max_len});
            tmp_down[u.max_len] = INF;
        }
        else if(u.len_down == 1 && tmp_up[u.max_len] != INF){
            ans.push_back({tmp_up[u.max_len], 1, u.max_len});
            tmp_up[u.max_len] = INF;
        }
    }

    c.clear();
    for(const auto & u: ans) c.push_back(u);
    // c = ans;
}

void solve(int l1, int l2, int n, int m){
    for(int i=0;i<=n-l1+1;i++) for(int j=0;j<=m-l2+1;j++){
        dp[i][j][0].clear();
        dp[i][j][1].clear();
    }

    for(int r1=0;r1<=n-l1+1;r1++){
        for(int r2=0;r2<=m-l2+1;r2++){
            int ind1 = l1+r1;
            int ind2 = l2+r2;

            if(r1 == 0 && r2 == 0){
                dp[1][0][0].push_back({1,1,1});
                dp[0][1][1].push_back({1,1,1});
                continue;
            }

            int ans = 1e9;

            // cout<<endl<<"  "<<r1<<" "<<r2<<" "<<0<<endl;
            compress(dp[r1][r2][0]);
            for(Cand c: dp[r1][r2][0]){
                // cout<<c.len_up<<" "<<c.len_down<<" "<<c.max_len<<endl;
                ans = min(ans, c.max_len);
                if(ind1 <= n){
                    if(A[ind1] > A[ind1-1]) dp[r1+1][r2][0].push_back({c.len_up+1, 1, max(c.max_len, c.len_up+1)});
                    else dp[r1+1][r2][0].push_back({1, c.len_down+1, max(c.max_len, c.len_down+1)});
                }
                if(ind2 <= m){
                    if(B[ind2] > A[ind1-1]) dp[r1][r2+1][1].push_back({c.len_up+1, 1, max(c.max_len, c.len_up+1)});
                    else dp[r1][r2+1][1].push_back({1, c.len_down+1, max(c.max_len, c.len_down+1)});
                }
            }

            // cout<<"  "<<r1<<" "<<r2<<" "<<1<<endl;
            compress(dp[r1][r2][1]);
            for(Cand c: dp[r1][r2][1]){
                // cout<<c.len_up<<" "<<c.len_down<<" "<<c.max_len<<endl;
                ans = min(ans, c.max_len);
                if(ind1 <= n){
                    if(A[ind1] > B[ind2-1]) dp[r1+1][r2][0].push_back({c.len_up+1, 1, max(c.max_len, c.len_up+1)});
                    else dp[r1+1][r2][0].push_back({1, c.len_down+1, max(c.max_len, c.len_down+1)});
                }
                if(ind2 <= m){
                    if(B[ind2] > B[ind2-1]) dp[r1][r2+1][1].push_back({c.len_up+1, 1, max(c.max_len, c.len_up+1)});
                    else dp[r1][r2+1][1].push_back({1, c.len_down+1, max(c.max_len, c.len_down+1)});
                }
            }

            if(r1 > 0 && r2 > 0) res[ans]++;
            // cout<<max(dp[r1][r2][0].size(), dp[r1][r2][1].size())<<endl;
        }
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int j=1;j<=m;j++) cin>>B[j];

    for(int i=0;i<=n+m;i++) tmp_up[i] = INF, tmp_down[i] = INF;

    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j][0].reserve(605);
            dp[i][j][1].reserve(605);
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            solve(i, j, n, m);
        }
    }

    for(int i=1;i<=n+m;i++) cout<<res[i]<<" ";
    cout<<endl;
}