对于每一个位置建立主席树，和静态主席树不一样。
由于 有修改操作，每一棵主席树维护的只是某一个位置，而不是静态中的前缀和或者后缀和
而这里的前缀后就交给树状数组去维护。
也就是主席树维护所有位置的信息，树状数组维护前缀和。
代码还是非常直观的。
在ZOJ只给了32M内存，而且n<=50000, 交了几发没有过
在BZOJ上没有问题，感觉自己写的主席树比较耗内存
再研究下看看能不能改进
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1000000005
#define M 2560005
#define N 61005
#define maxn 210005
#define eps 1e-8
#define zero(a) fabs(a)
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts("OK");
#define pi acos(-1.0)
#define lowbit(x) ((-(x))&(x))
#define HASH1 1331
#define HASH2 10001
#define C 240
#define vi vector
#define TIME 10
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int tot=0,n,m=0,q;
int a[N],h[N];
int T[N],c[M],lson[M],rson[M];
struct Question{
int kind;
int l,r,k;
Question(){}
Question(int k,int l,int r,int _k):kind(k),l(l),r(r),k(_k){}
}Q[N];
void Init_hash(int k){
sort(h,h+k);
m=unique(h,h+k)-h;
}
int hash(int x){
return lower_bound(h,h+m,x)-h;
}
int bulid(int l,int r){
int root=tot++;
if(l!=r){
int mid=(l+r)>>1;
lson[root]=bulid(l,mid);
rson[root]=bulid(mid+1,r);
}
return root;
}
int update(int root,int pos,int val){
int newroot=tot++,tmp=newroot;
int l=0,r=m-1;
c[newroot]=c[root]+val;
while(l
int mid=(l+r)>>1;
if(pos<=mid){
lson[newroot]=tot++;rson[newroot]=rson[root];
newroot=lson[newroot];root=lson[root];
r=mid;
}
else{
rson[newroot]=tot++;lson[newroot]=lson[root];
newroot=rson[newroot];root=rson[root];
l=mid+1;
}
c[newroot]=c[root]+val;
}
return tmp;
}
int use[N];
void add(int x,int pos,int val){
//更新的时候，维护树状数组
for(int i=x;i<=n;i+=lowbit(i))
T[i]=update(T[i],pos,val);
}
int sum(int x){
int ret=0;
for(int i=x;i;i-=lowbit(i))
ret+=c[lson[use[i]]];
return ret;
}
int query(int left,int right,int k){
int l=0,r=m-1;
for(int i=left-1;i;i-=lowbit(i)) use[i]=T[i];
for(int i=right;i;i-=lowbit(i)) use[i]=T[i];
while(l
int mid=(l+r)>>1;
int tmp=sum(right)-sum(left-1);
if(tmp>=k){
r=mid;
for(int i=left-1;i;i-=lowbit(i))
use[i]=lson[use[i]];
for(int i=right;i;i-=lowbit(i))
use[i]=lson[use[i]];
}
else{
l=mid+1;
k-=tmp;
for(int i=left-1;i;i-=lowbit(i))
use[i]=rson[use[i]];
for(int i=right;i;i-=lowbit(i))
use[i]=rson[use[i]];
}
}
return l;
}
void Init_tree(){
T[0]=bulid(0