【题意】
给定一个含有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。
【分析】
带修改的区间第k大。
如果只是询问区间的第k大的话，就是可持久化字母树。
然后，其实我想了挺久。。。。可以看看GDXB的题解。。http://www.cnblogs.com/KonjakJuruo/p/6031832.html
她打的是树状数组套线段树。 其实就是树状数组搞区间，然后线段树搞数值。
因为带修改的话，是动态的。相当于不修改的时候，我们只要记录前缀和，就可以知道某段区间的和（两个前缀相减），但是修改了之后，就要用树状数组或者线段树等维护。
这个也是这个道理，用数据结构维护区间。
本蒟蒻打的是线段树套字母树（区间第k大，深爱字母树，耶！）
其实树状数组套字母树应该更简单？？
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 10010
#define Maxd 32 int a[Maxn],nw[Maxn],al;
char s[]; struct trie
{
int son[],cnt;
}tr[Maxn**];int tot; void upd(int x)
{
tr[x].son[]=tr[x].son[]=;
tr[x].cnt=;
} void add(int now,int y,int c)
{
for(int i=Maxd;i>=;i--)
{
int ind=y>>i-;
y=y%(<<i-);
if(!tr[now].son[ind])
{
tr[now].son[ind]=++tot;
upd(tot);
}
now=tr[now].son[ind];
tr[now].cnt+=c;
}
} int query(int k)
{
int ans=;
for(int i=Maxd;i>=;i--)
{
int ls=;
for(int j=;j<=al;j++) ls+=tr[tr[nw[j]].son[]].cnt;
if(ls>=k)
{
for(int j=;j<=al;j++) nw[j]=tr[nw[j]].son[];
}
else
{
k-=ls;
ans+=(<<i-);
for(int j=;j<=al;j++) nw[j]=tr[nw[j]].son[];
}
}
return ans;
} struct node
{
int l,r,lc,rc,rt;
}t[Maxn*];int len; int build(int l,int r)
{
int x=++len;
t[x].l=l;t[x].r=r;t[x].rt=++tot;
upd(tot);
if(l!=r)
{
int mid=(l+r)>>;
t[x].lc=build(l,mid);
t[x].rc=build(mid+,r);
}
else t[x].lc=t[x].rc=;
return x;
} void change(int x,int y,int z)
{
add(t[x].rt,z,);
if(a[y]!=-) add(t[x].rt,a[y],-);
if(t[x].l==t[x].r) return;
int mid=(t[x].l+t[x].r)>>;
if(y<=mid) change(t[x].lc,y,z);
else change(t[x].rc,y,z);
} void ffind(int x,int l,int r)
{
if(t[x].l==l&&t[x].r==r)
{
nw[++al]=t[x].rt;
return;
}
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) ffind(t[x].lc,l,r);
else if(l>mid) ffind(t[x].rc,l,r);
else
{
ffind(t[x].lc,l,mid);
ffind(t[x].rc,mid+,r);
}
} int n,m;
void init()
{
len=;tot=;
scanf("%d%d",&n,&m);
build(,n);
memset(a,-,sizeof(a));
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
change(,i,x);
a[i]=x;
}
} int main()
{
init();
for(int i=;i<=m;i++)
{
scanf("%s",s);
if(s[]=='C')
{
int x,y;
scanf("%d%d",&x,&y);
change(,x,y);
a[x]=y;
}
else
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
al=;
ffind(,x,y);
printf("%d\n",query(k));
}
}
return ;
}
2016-11-08 14:33:10
话说树套树的离线题可以用CDQ分治？？
不会。。