Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int MX=1e6+5;
- typedef long long ll;
- int id,tree[4*MX],n,k;
- void insrt(int x=1,int l=1,int r=n)
- {
- if(id<l||id>r)return;
- if(id==r&&r==l)
- {
- tree[x]++;
- return;
- }
- insrt(2*x,l,(l+r)/2);
- insrt(2*x+1,(l+r)/2 +1 , r);
- tree[x]=tree[2*x]+tree[2*x+1];
- }
- int le,rr;
- int srch(int x=1,int l=1,int r=n)
- {
- if(le>rr)return 0;
- if(le>r||rr<l)return 0;
- if(le<=l&&r<=rr)return tree[x];
- return srch(2*x,l,(l+r)/2)+srch(2*x+1,(l+r)/2 +1 , r);
- }
- int main()
- {
- cin>>n>>k;
- int here=1,ans=1;
- for(int i=0;i<n;i++)
- {
- id =here;
- insrt();
- int there=(here+k);
- //cout<<there<<' '<<here<<endl;
- bool up=0;
- if(there>n)there-=n,up=1;
- id=there;
- insrt();
- if(up)
- {
- le = here+1;
- rr = n;
- ans+=srch();
- le=1;
- rr=there-1;
- ans+=srch();
- }else
- {
- le=here+1;
- rr=there-1;
- // cout<<here<<' '<<there<<'$'<<endl;
- // cout<<le<<' '<<rr<<' '<< endl;
- ans+=srch();
- }
- cout<<++ans<<' ';
- here =there;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement