【基数排序】bzoj1901 Zju2112 Dynamic Rankings

论NOIP级别的n²算法…… 跟分块比起来，理论上十万的数据只慢4、5倍左右的样子……
 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct Point{int v,p;}t[20001];
 5 bool operator < (const Point &a,const Point &b){return a.v<b.v;}
 6 struct ASK{char op[1];int x,y,k;}Ask[10001];
 7 int n,m,a[20001],en,ma[20001],en2,b[20001];
 8 int main()
 9 {
10     scanf("%d%d",&n,&m);
11     for(int i=1;i<=n;++i)
12       {
13           scanf("%d",&t[i].v);
14           t[i].p=i;
15       } en=n;
16     for(int i=1;i<=m;++i)
17       {
18           scanf("%s%d%d",Ask[i].op,&Ask[i].x,&Ask[i].y);
19           if(Ask[i].op[0]=='Q') scanf("%d",&Ask[i].k);
20           else
21             {
22                 t[++en].v=Ask[i].y;
23                 t[en].p=en;
24             }
25       } sort(t+1,t+en+1);
26     ma[a[t[1].p]=++en2]=t[1].v;
27     for(int i=1;i<=en;++i)
28       {
29           if(t[i].v!=t[i-1].v) en2++;
30           ma[a[t[i].p]=en2]=t[i].v;
31       } en=n;
32     for(int i=1;i<=m;++i)
33       {
34           if(Ask[i].op[0]=='Q')
35             {
36                 int cnt=0;
37                 for(int j=Ask[i].x;j<=Ask[i].y;++j) ++b[a[j]];
38                 for(int j=1;;++j)
39               {
40                   if(b[j]) cnt+=b[j];
41                   if(cnt>=Ask[i].k)
42                   {
43                       printf("%d
",ma[j]);
44                       for(int k=Ask[i].x;k<=Ask[i].y;k++) --b[a[k]];
45                       goto OUT;
46                   }
47               }
48             }
49           else a[Ask[i].x]=a[++en];
50           OUT:;
51       }
52     return 0;
53 }