题意不难理解,解法具体看代码及注释吧。。
#include<bits/stdc++.h> using namespace std; typedef long long LL; ; int n,k; int ql,qr; int pos; //当前要出队的人在剩余人中排在第几靠左的地方 struct node { int l,r; int pre; //记录区间中剩余的最靠右的人在所有剩余人中的位置 int lz; //lazy标记 } a[maxn<<]; void push_up(int rt) { a[rt].pre=max(a[rt<<].pre,a[rt<<|].pre); } void build(int rt,int l,int r) { a[rt].l=l,a[rt].r=r; if(l==r) { a[rt].pre=l; return ; } ; build(rt<<,l,mid); build(rt<<|,mid+,r); push_up(rt); } void update(int rt) { int l=a[rt].l,r=a[rt].r; if(ql<=l&&r<=qr) { --a[rt].pre; --a[rt].lz; return ; } ; ); |); push_up(rt); } void push_down(int rt) { int& lz=a[rt].lz; ) return ; a[rt<<].lz+=lz; a[rt<<|].lz+=lz; a[rt<<].pre+=lz; a[rt<<|].pre+=lz; lz=; } int query(int rt) { int l=a[rt].l,r=a[rt].r; if(l==r) return l; push_down(rt); ; ].pre>=pos) ); |); } int main() { scanf("%d%d",&n,&k); build(,,n); int cnt=n; pos=; ;i<n;i++) { pos=(pos-+k+cnt*)%cnt+; //当前位置变更 --cnt; //少了个人 ); //出队人在原队伍中的位置 printf(? '\n':' '); ql=p,qr=n; //出队后,pre发生变化的区间范围 update(); } }