Zju2112 Dynamic Rankings
Time Limit:10000MS Memory Limit:165536K
Total Submit:18 Accepted:7
Case Time Limit:1000MS
Description
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在 a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对 改变后的a继续回答上面的问题。
你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。
第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。
第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。
接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。
Q i j k 或者 C i t
Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
Input
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
Output
Sample Input
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
Hint
20%的数据中，m,n≤100;
40%的数据中，m,n≤1000;
100%的数据中，m,n≤10000。
Source
各位神牛至少3KB的代码量让我很冏。。一般来说是要树套树的把，但我感觉那样很难写，索性写个块状数组算了。。结果发现速度非常快冏。。。
对每个块保存排序的结果，同时保存整体所有的数，那么查询一个数在一个区间中比它小的数数量是
O(N^0.5LogN)的。。再加上二分找这个数，就是N^0.5*LogN^2了。。
还有修改的话直接修改一排序的结果（插入排序）和整体这个数，是O（N^0.5）的。。但我感觉查询都那么慢了修改也无所谓了，就暴力sort了冏。。。由于这里不能搞出当前所有数的排列，所以二分只能按照Log（10^9）=30来搞，实际上如果先离线一下读入所有数就可以直接在所有数中二分，那么就是Log(20000)=15..快一倍。。不过没必要。。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
const int inf=~0U>>1,maxn=10000,size=100;
int T[size][size],N[size]={},A[maxn],n,m,t,d=1<<6;
using namespace std;
void init()
{
scanf("%d%d",&n,&m);rep(i,n)scanf("%d",A+i),T[i/size][N[i/size]++]=A[i];
t=1+(n-1)/size;rep(i,t)sort(T[i],T[i]+N[i]);
}
int get(int*A,int s,int x)
{
int i,l;
for(i=s,l=d;l;l>>=1)
if(i-l>=0&&A[i-l]>=x)i-=l;
return i;
}
int Count(int l,int r,int x)
{
int a=l/size,b=r/size,s=0;;
if(a==b){For(i,l,r)s+=A[i]<x;return s;}
For(i,l,(a+1)*size-1)s+=A[i]<x;
For(i,b*size,r)s+=A[i]<x;a++;b–;
For(i,a,b)s+=get(T[i],N[i],x);
return s;
}
int kth(int l,int r,int k)
{
#define C(x) (Count(l,r,x))
int i,d;
for(i=0,d=1<<30;d;d>>=1)
if(C(i+d)<k)i+=d;
return i;
}
void Change(int p,int x)
{
int a=p/size;int t=A[p];A[p]=x;
t=lower_bound(T[a],T[a]+N[a],t)-T[a];
T[a][t]=x;sort(T[a],T[a]+N[a]);
}
int main()
{
//freopen("in","r",stdin);
init();char c;int i,j,k;
while(m–)
{
scanf("n%c",&c);
if(c==’C’)scanf("%d%d",&i,&j),Change(i-1,j);
else scanf("%d%d%d",&i,&j,&k),printf("%dn",kth(i-1,j-1,k));
}
}