Description
假设一开始，荷官拿出了一副新牌，这副牌有N张不同的牌，编号依次为1到N。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为1, 2,……直到N，N号牌在牌库底。为了发完所有的牌，荷官会进行N次发牌操作，在第i次发牌之前，他会连续进行R_i次销牌操作，R_i由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？
举个例子，假设N = 4，则一开始的时候，牌库中牌的构成顺序为{1, 2, 3, 4}。
假设R1=2，则荷官应该连销两次牌，将1和2放入牌库底，再将3发给玩家。目前牌库中的牌顺序为{4, 1, 2}。
假设R2=0，荷官不需要销牌，直接将4发给玩家，目前牌库中的牌顺序为{1,2}。
假设R3=3，则荷官依次销去了1, 2, 1，再将2发给了玩家。目前牌库仅剩下一张牌1。
假设R4=2，荷官在重复销去两次1之后，还是将1发给了玩家，这是因为1是牌库中唯一的一张牌。
Input
第1行，一个整数N，表示牌的数量。第2行到第N + 1行，在第i + 1行，有一个整数R_i， 0≤R_i<N
Output
第1行到第N行：第i行只有一个整数，表示玩家收到的第i张牌的编号。
Sample Input
4 2 0 3 2
Sample Output
3 4 2 1
HINT
N<=70万
Solution
一看是splay裸题就上splay硬艹结果因为人傻常数大只有80……于是换了线段树写法
开个线段树存一下每种牌的数量0/1
在值域线段树上二分即可。代码简单易懂最后面贴一下我GG的splay
Code
1 #include2 #include 3 #define N (700000+1000) 4 using namespace std; 5 6 int Segt[N<<2]; 7 8 inline int read() 9 {10 int x=0,w=1; char c=getchar();11 while (!isdigit(c)&&c!='-') c=getchar();12 if (c=='-') c=getchar(),w=-1;13 while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}14 return x*w;15 }16 17 void Build(int now,int l,int r)18 {19 if (l==r){Segt[now]=1; return;}20 int mid=(l+r)>>1;21 Build(now<<1,l,mid); Build(now<<1|1,mid+1,r);22 Segt[now]=Segt[now<<1]+Segt[now<<1|1];23 }24 25 void Update(int now,int l,int r,int k)26 {27 Segt[now]--;28 if (l==r){printf("%d\n",l); return;}29 int mid=(l+r)>>1;30 if (k<=Segt[now<<1]) Update(now<<1,l,mid,k);31 else Update(now<<1|1,mid+1,r,k-Segt[now<<1]);32 }33 34 int main()35 {36 int n,x,p=0;37 n=read();38 Build(1,1,n);39 for (int i=1; i<=n; ++i)40 {41 x=read();42 p=(p+x)%(n-i+1);43 Update(1,1,n,p+1);44 }45 }
1 #include2 #include 3 #define N (700000+1000) 4 using namespace std; 5 6 int n,x,Root,Father[N],Son[N][2],Size[N]; 7 8 void Update(int x){Size[x]=1+Size[Son[x][0]]+Size[Son[x][1]];} 9 int Get(int x){ return Son[Father[x]][1]==x;}10 11 inline int read()12 {13 int x=0,w=1;14 char c=getchar();15 while (!isdigit(c)&&c!='-') c=getchar();16 if (c=='-') c=getchar(),w=-1;17 while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}18 return x*w;19 }20 21 void Build(int fa,int l,int r)22 {23 if (l>r) return;24 if (l==r) Size[l]=1;25 int mid=(l+r)>>1;26 Build(mid,l,mid-1);27 Build(mid,mid+1,r);28 Father[mid]=fa; Son[fa][mid>fa]=mid;29 Update(mid);30 }31 32 void Rotate(int x)33 {34 int wh=Get(x);35 int fa=Father[x],fafa=Father[fa];36 if (fafa) Son[fafa][Son[fafa][1]==fa]=x;37 Father[fa]=x; Son[fa][wh]=Son[x][wh^1];38 Father[x]=fafa; Son[x][wh^1]=fa;39 if (Son[fa][wh]) Father[Son[fa][wh]]=fa;40 Update(fa); Update(x);41 }42 43 void Splay(int x,int tar)44 {45 for (int fa; (fa=Father[x])!=tar; Rotate(x))46 if (Father[fa]!=tar)47 Rotate(Get(fa)==Get(x)?fa:x);48 if (!tar) Root=x;49 }50 51 int Findkth(int x)52 {53 int now=Root;54 while (1)55 if (Size[Son[now][0]]>=x) now=Son[now][0];56 else57 {58 x-=Size[Son[now][0]];59 if (x==1){ /*Splay(now,0);*/ return now;}60 x--; now=Son[now][1];61 }62 }63 64 int Split(int l,int r)65 {66 int x=Findkth(l);67 int y=Findkth(r+2);68 Splay(x,0); Splay(y,x);69 return Son[y][0];70 }71 72 int main()73 {74 n=read();75 Build(0,1,n+2);76 Root=(n+3)>>1;77 for (int i=1; i<=n; ++i)78 {79 x=read();80 x%=n-i+1;81 if (x)82 {83 int now=Split(1,x);84 Son[Father[now]][Son[Father[now]][1]==now]=0;85 Father[now]=0;86 int fa=Split(n-i+1-x,n-i+1-x);87 Son[fa][1]=now; Father[now]=fa;88 Splay(now,0);89 }90 int now=Split(1,1); printf("%d\n",now-1);91 Son[Father[now]][0]=0;92 Father[now]=0; Update(Son[Root][1]);93 }94 }