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
131
132
133
134
135
//#pragma GCC optimize("O2")
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=200010;
int a[N][2];
vector<pair<int,int> > add[N];
int val[N];
ll ans[11];
int n,k;
struct node{
    int mn[11];
    int cnt[11];

};
node t[N*4];
int w[N*4];
void push(int v){
    if (w[v]){
        w[v+v]+=w[v];
        w[v+v+1]+=w[v];
        for (int i=0;i<k;i++){
            t[v+v].mn[i]+=w[v];
            t[v+v+1].mn[i]+=w[v];
        }
        w[v]=0;
    }
}
void build(int v,int l,int r){
    t[v].mn[0]=k+1;
    t[v].cnt[0]=r-l+1;
    for (int i=1;i<k;i++){
        t[v].mn[i]=N;
        t[v].cnt[i]=0;
    }
    w[v]=0;
    if (l==r) return;
    int m=(l+r)/2;
    build(v+v,l,m);
    build(v+v+1,m+1,r);
}
void upd(int v,int l,int r,int L,int R,int x){
    if (l>R || r<L) return;
    if (l>=L && r<=R){
        w[v]+=x;
        for (int i=0;i<k;i++) t[v].mn[i]+=x;
        return;
    }
    push(v);
    int m=(l+r)/2;
    upd(v+v,l,m,L,R,x);
    upd(v+v+1,m+1,r,L,R,x);
    int i=0,j=0;
    int ind=0;
    while (ind<k){
        if (t[v+v].mn[i]==t[v+v+1].mn[j]){
            t[v].mn[ind]=t[v+v].mn[i];
            t[v].cnt[ind++]=t[v+v].cnt[i++]+t[v+v+1].cnt[j++];
        } else if (t[v+v].mn[i]<t[v+v+1].mn[j]){
            t[v].mn[ind]=t[v+v].mn[i];
            t[v].cnt[ind++]=t[v+v].cnt[i++];
        } else {
            t[v].mn[ind]=t[v+v+1].mn[j];
            t[v].cnt[ind++]=t[v+v+1].cnt[j++];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    n=100000;
//    k=10;
////    cin>>n>>k;
//    vector<int>r;
//    for (int i=1;i<=2*n;i++) r.push_back(i);
////    random_shuffle(r.begin(),r.end());
//    for (int i=0;i<n;i++){
//        a[i][0]=r.back();
//        r.pop_back();
//    }
//    for (int i=0;i<n;i++){
//        a[i][1]=r.back();
//        r.pop_back();
//    }
    cin>>n>>k;
    for (int i=0;i<n;i++) cin>>a[i][0];
    for (int i=0;i<n;i++) cin>>a[i][1];

    k++;

    vector<pair<pair<int,int>,int> >seg;
    for (int i=0;i<n;i++){
        int l=a[i][0];
        int r=a[i][1];
        if (l>r) swap(l,r);
        seg.push_back({{l,r},-1});
    }

    for (int i=0;i<n;i++){
        int nxt=(i+1)%n;
        int l1=a[i][0],r1=a[nxt][0];
        int l2=a[i][1],r2=a[nxt][1];
        if (l1>r1) swap(l1,r1);
        if (l2>r2) swap(l2,r2);
        if (l1<l2){
            swap(l1,l2);
            swap(r1,r2);
        }
        seg.push_back({{l1,r1},-1});
        seg.push_back({{l2,r2},-1});
        seg.push_back({{min(l1,l2),max(r1,r2)},1});
    }
    for (auto cur:seg){
        add[cur.first.first].push_back({cur.first.second,cur.second});
    }
    build(1,1,2*n);
    for (int i=2*n;i>=1;i--){
        upd(1,1,n*2,i,i,-k-1);
        upd(1,1,n*2,i,2*n,1);

        for (auto cur:add[i]){
            upd(1,1,2*n,cur.first,2*n,cur.second);
        }
        for (int j=0;j<k;j++){
            if (t[1].mn[j]<k) ans[t[1].mn[j]]+=t[1].cnt[j];
        }
    }
    ans[1]+=ans[0];
    k--;
    for (int i=1;i<=k;i++) cout<<ans[i]<<" ";
    cout<<endl;

    return 0;
}