【FOJ】1962 新击鼓传花游戏

 1 #include<cstdio>
 2 #define MAXN 500010
 3 int tree[MAXN<<2];
 4 inline void PushUp(int rt)
 5 {
 6     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 7 }
 8 void Build(int L,int R,int rt)
 9 {
10     if(L==R)
11         tree[rt]=1;
12     else
13     {
14         int mid=(L+R)>>1;
15         Build(L,mid,rt<<1);
16         Build(mid+1,R,rt<<1|1);
17         PushUp(rt);
18     }
19 }
20 void Leave(int k,int L,int R,int rt)
21 {
22     if(L==R)
23         tree[rt]=0;
24     else
25     {
26         int mid=(L+R)>>1;
27         if(tree[rt<<1]>=k)
28             Leave(k,L,mid,rt<<1);
29         else
30             Leave(k-tree[rt<<1],mid+1,R,rt<<1|1);
31         PushUp(rt);
32     }
33 }
34 void Back(int x,int L,int R,int rt)
35 {
36     if(L==R)
37         tree[rt]=1;
38     else
39     {
40         int mid=(L+R)>>1;
41         if(mid>=x)
42             Back(x,L,mid,rt<<1);
43         else
44             Back(x,mid+1,R,rt<<1|1);
45         PushUp(rt);
46     }
47 }
48 int Query(int k,int L,int R,int rt)
49 {
50     if(L==R)
51         return L;
52     int mid=(L+R)>>1;
53     if(tree[rt<<1]>=k)
54         return Query(k,L,mid,rt<<1);
55     else
56         return Query(k-tree[rt<<1],mid+1,R,rt<<1|1);
57 }
58 int main()
59 {
60     int n,m,k;
61     char ch;
62     while(~scanf("%d%d",&n,&m))
63     {
64         Build(1,n,1);
65         while(m--)
66         {
67             scanf(" %c%d",&ch,&k);
68             if(ch=='L')
69                 Leave(k,1,n,1);
70             else if(ch=='R')
71                 Back(k,1,n,1);
72             else
73                 printf("%d\n",Query(k,1,n,1));
74         }
75     }
76     return 0;
77 }
新博客：www.zhixiangli.com