题目描述
有编号从1到N的N个小朋友在玩一种出圈的游戏。开始时N个小朋友围成一圈，编号为I+1的小朋友站在编号为I小朋友左边。编号为1的小朋友站在编号为N的小朋友左边。首先编号为1的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字M时就出圈。直到只剩下1个小朋友，则游戏完毕。
现在给定N,M，求N个小朋友的出圈顺序。
输入
唯一的一行包含两个整数N,M。（1<=N,M<=30000）
输出
唯一的一行包含N个整数，每两个整数中间用空格隔开，第I个整数表示第I个出圈的小朋友的编号。
样例输入
5 3
样例输出
3 1 5 2 4
很好想的一道题，就是求出每次需要出圈的人的排名，然后输出并删除。
然而N为30000怎么办？
网上的题解是线段树，然而线段树不能删除，过于麻烦。
于是想到Treap。
代码有点长，但很好理解。
需要注意rn是上次的排名，但是这次第一个人的排名却应该与rn相同，因为已经减少一个人，对应排名-1。
因此rn初始值为1。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int l[30001] , r[30001] , num[30001] , si[30001] , rnd[30001] , tot , root;
void pushup(int k)
{
si[k] = si[l[k]] + si[r[k]] + 1;
}
void zig(int &k)
{
int t = l[k];
l[k] = r[t];
r[t] = k;
si[t] = si[k];
pushup(k);
k = t;
}
void zag(int &k)
{
int t = r[k];
r[k] = l[t];
l[t] = k;
si[t] = si[k];
pushup(k);
k = t;
}
void ins(int &k , int x)
{
if(!k)
{
k = ++tot;
num[k] = x;
si[k] = 1;
rnd[k] = rand();
return;
}
si[k] ++ ;
if(x < num[k])
{
ins(l[k] , x);
if(rnd[l[k]] < rnd[k])
zig(k);
}
else
{
ins(r[k] , x);
if(rnd[r[k]] < rnd[k])
zag(k);
}
}
void del(int &k , int x)
{
if(!k) return;
if(x == num[k])
{
if(l[k] * r[k] == 0)
k = l[k] + r[k];
else if(rnd[l[k]] < rnd[r[k]])
zig(k) , del(k , x);
else
zag(k) , del(k , x);
}
else if(x < num[k])
si[k] -- , del(l[k] , x);
else
si[k] -- , del(r[k] , x);
}
int getrank(int k , int x)
{
if(x == num[k]) return si[l[x]] + 1;
else if(x < num[k]) return getrank(l[k] , x);
else return getrank(r[k] , x) + si[l[x]] + 1;
}
int find(int k , int x)
{
if(x <= si[l[k]]) return find(l[k] , x);
else if(x > si[l[k]] + 1) return find(r[k] , x - si[l[k]] - 1);
else return num[k];
}
int main()
{
int n , m , i , rn = 1 , c;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ )
ins(root , i);
for(i = 1 ; i <= n ; i ++ )
{
rn = (rn + m - 2 + si[root]) % si[root] + 1;
c = find(root , rn);
printf("%d " , c);
del(root , c);
}
printf("\n");
return 0;
}