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
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <vector>
#define LL long long
#define M 1000000007
#define MAXN 300002

using namespace std;

int n, m, t;
vector<int> v, w;

vector<LL> totres(2 * MAXN); // endresult

int getRes(vector <int> &a, vector<int> &b) { // |a'| > |b'|
    vector<int> inc = {-1}, lens = {0};
    vector<int> prefb = {0};
    int maxlen = 0;
    for (int i = 1; i < a.size(); i++) inc.push_back(a[i] - a[i - 1] > 0 ? 1 : 0);
    for (int i = 1; i < inc.size(); i++) {
        if (inc[i] == inc[i - 1]) {
            lens.push_back(lens.back() + 1);
        } else {
            lens.push_back(1);
        }
        if (lens.back() > maxlen) maxlen = lens.back();
    }
    for (auto el : lens) cerr << el << " ";
    cerr << " lens\n";

    for (int i = 0; i < b.size(); i++) {
        prefb.push_back(prefb.back() + b.size() - i);
        cerr << prefb.back() << " ";
    }
    cerr << " prefb\n";
    
    int addrow = prefb[0];
    int totrow = prefb[0];
    int maxcur = 0;
    for (int i = 1; i < lens.size(); i++) {
        if (i > 0 && lens[i] > 1) {
            if (lens[i] > maxcur) maxcur = lens[i];
        }

        if (i < prefb.size()) {
            addrow += prefb[i];
        } else {
            addrow += prefb.back();
        }
        totrow += addrow;
        cerr << i << ": " << lens[i] << "," 
             << ", row: " << addrow << " " << totrow << "\n";

        int sumrow = 0;
        vector<int> res(maxlen + 1);
        int maxs = min((int)prefb.size() - 1, i);
        
        
        for (int x = maxcur; x > 1; x--) {
            cerr << " [" << x;
            int s = 0;
            int prevs = 0, cur = 1, curs = 0, nful = 0;
            for (int j = i; j > 0; j--) {
                if (j != i && inc[j] == inc[j + 1]) {
                    cur++;
                    curs = (cur - 1) / x;
                    if (cur  % x == 0) nful++;
                } else {
                    prevs += curs;
                    curs = 0;
                    cur = 1;
                }
                s = prevs + curs;
                if (nful > 0) s += nful - 1;

                cerr << " <" << j << "," << prevs << "," << curs << "," << cur << "," << nful;
                if (s > maxs) {
                    cerr << "  MAXS " << s << ", " << maxs << "\n";
                    break;
                }
                int add = prefb[s];
                res[x] += add;
                cerr << "(" << add << ")";
                sumrow += add;
            }
            cerr << "\n";
        }
        res[1] += addrow - sumrow;
        for (int i = 0; i < res.size(); i++) totres[i] += res[i];
    }
        
    cerr << "\n";
    
    return 0;
}

void getSame(vector <int> &a, vector<int> &b) { // |a'| == |b'|
    for (int i = 0; i < a.size() && i < b.size(); i++) {
        totres[1] += (a.size() - i) * (b.size() - i);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> t;
        v.push_back(t);
    }
    for (int i = 0; i < m; i++) {
        cin >> t;
        w.push_back(t);
    }

    getRes(v, w);
    getRes(w, v);
    getSame(v, w);

    for (int i = 0; i < v.size() + w.size(); i++) cout << totres[i] << " ";
    cout << "\n";
    
    return 0;
}