FZU 1962 新击鼓传花游戏

新击鼓传花游戏

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on FZU. Original ID: 1962
64-bit integer IO format: %I64d Java class name: Main

N个小朋友，编号为1..N，玩新击鼓传花游戏。游戏由老师来主持，老师将下达M条命令，命令包含以下三种，

L k，让将当前游戏中剩余的小朋友中，编号第k小的小朋友离开游戏。

R x，让编号为x的小朋友重新回到游戏中，如果编号为x的小朋友已经在游戏中，那么不做任何变化。

Q k，查询并输出当前剩余小朋友中，编号第k小的小朋友的编号。

Input

第一行两个整数N, M（1<=N, M<=500,000），表示小朋友的人数和老师命令的条数。接下来m行，每行按指定格式给出一条命令，输入数据保证k不大于当前剩余的小朋友数量，而1<=x<=N。

Output

对测试数据中的查询语句，输出一行，表示当前编号第k小的小朋友编号。

Sample Input

5 5
L 1
L 1
Q 1
R 1
Q 1

Sample Output

3
1

Source

Contest for 2010 lecture I

解题：线段树或者树状数组

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn = 500010;
 6 int tree[maxn<<2];
 7 void pushup(int v){
 8     tree[v] = tree[v<<1] + tree[v<<1|1];
 9 }
10 void build(int L,int R,int v){
11     if(L == R) {
12         tree[v] = 1;
13         return;
14     }
15     int mid = (L + R)>>1;
16     build(L,mid,v<<1);
17     build(mid+1,R,v<<1|1);
18     pushup(v);
19 }
20 void update(int L,int R,int id,int val,int v){
21     if(L == R){
22         if(tree[v] != val) tree[v] = val;
23         return;
24     }
25     int mid = (L + R)>>1;
26     if(id <= mid) update(L,mid,id,val,v<<1);
27     if(id > mid) update(mid+1,R,id,val,v<<1|1);
28     pushup(v);
29 }
30 int query(int L,int R,int p,int v){
31     if(L == R) return L;
32     int mid = (L + R)>>1;
33     if(p <= tree[v<<1]) return query(L,mid,p,v<<1);
34     else return query(mid+1,R,p-tree[v<<1],v<<1|1);
35 }
36 int main(){
37     int n,m,o;
38     char tmp[10];
39     while(~scanf("%d %d",&n,&m)){
40         build(1,n,1);
41         while(m--){
42             scanf("%s%d",tmp,&o);
43             if(tmp[0] == 'L') update(1,n,query(1,n,o,1),0,1);
44             else if(tmp[0] == 'R') update(1,n,o,1,1);
45             else if(tmp[0] == 'Q') printf("%d
",query(1,n,o,1));
46         }
47     }
48     return 0;
49 }

View Code