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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIPII;

int arr[2][100005];

struct Event{
    PII seg;
    int val;
};
vector<Event> events[200005];

void add_event(PII l, PII r, int val){
    if(r.first > r.second) return;
    events[l.first].push_back({r, val});
    events[l.second+1].push_back({r, -val});
}

struct Node{
    int sum;
    int cnt[21];
};
Node T[600000];

inline void MergeT(int v){
    for(int i=0;i<=20;i++) T[v].cnt[i] = 0;
    const int & s = T[v].sum;
    for(int i=s;i<=20;i++) T[v].cnt[i] = T[2*v].cnt[i-s] + T[2*v+1].cnt[i-s];
}

void UpdateT(int bl, int br, int l, int r, int val, int v){
    if(bl>r || br<l) return;
    if(bl == br){
        if(T[v].sum <= 20) T[v].cnt[T[v].sum] = 0;
        T[v].sum += val;
        if(T[v].sum <= 20) T[v].cnt[T[v].sum] = 1;
        return;
    }
    if(l<=bl && br<=r){
        T[v].sum += val;
        MergeT(v);
        return;
    }
    
    int bm = (bl+br)/2;
    UpdateT(bl,bm,l,r,val,2*v);
    UpdateT(bm+1,br,l,r,val,2*v+1);
    MergeT(v);
}

void Init(int bl, int br, int v){
    if(bl == br){
        T[v].cnt[0] = 1;
        return;
    }
    int bm = (bl+br)/2;
    Init(bl,bm,2*v);
    Init(bm+1,br,2*v+1);
    T[v].cnt[0] = T[2*v].cnt[0] + T[2*v+1].cnt[0];
}

void Update(int l, int r, int val, int n){
    UpdateT(1,2*n,l,r,val,1);
}
long long ans[205];

int main(){
    ios_base::sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>arr[0][i];
    for(int i=0;i<n;i++) cin>>arr[1][i];

    for(int i=0;i<n;i++){
        vector<PIPII> V = {{0,{-1,0}}, {2*n+1,{100,0}}};
        V.push_back({arr[0][i],{0,0}});
        V.push_back({arr[1][i],{1,0}});
        V.push_back({arr[0][(i+1)%n],{0,1}});
        V.push_back({arr[1][(i+1)%n],{1,1}});
        sort(V.begin(), V.end());

        for(int indl=1;indl<=4;indl++){
            for(int indr=indl;indr<=4;indr++){
                int marked[2][2];
                marked[0][0] = 0, marked[1][0] = 0, marked[0][1] = 0, marked[1][1] = 0;
                for(int j=indl;j<=indr;j++) marked[V[j].second.first][V[j].second.second] = 1;
                int sum = marked[0][0] + marked[1][0] + marked[0][1] + marked[1][1];
                PII bl={V[indl-1].first+1, V[indl].first};
                PII br={V[indr].first, V[indr+1].first-1};
                if(sum == 1) add_event(bl, br, 1);
                else if(sum == 2){
                    if(marked[0][0] && marked[1][0]) add_event(bl, br, 1);
                    if(marked[0][1] && marked[1][1]) add_event(bl, br, 1);
                    if(marked[0][0] && marked[1][1]) add_event(bl, br, 2);
                    if(marked[0][1] && marked[1][0]) add_event(bl, br, 2);   
                }
            }
        }
    }

    Init(1, 2*n, 1);

    for(int i=1;i<=2*n;i++){
        for(Event & ev: events[i]){
            Update(ev.seg.first, ev.seg.second, ev.val, n);
        }
        for(int j=0;j<=2*k;j+=2) ans[j] += T[1].cnt[j];
        Update(i, i, 21, n);
    }

    cout<<ans[0]+ans[2]<<" ";
    for(int i=2;i<=k;i++)cout<<ans[2*i]<<" ";
    cout<<endl;
}