主席树

struct ZXS{
	int tot=0;
	TREE tr[N*32];
	int xin(int p){
		tot++,tr[tot]=tr[p];
		return tot;
	}
	void up(int p){
		int ls=tr[p].ls,rs=tr[p].rs;
		tr[p].val=tr[ls].val+tr[rs].val;
	}
	int build(int p,int l,int r){
		p=++tot;
		if(l==r){
			tr[p].val=0;
			return p;
		}
		int mid=(l+r)>>1;
		tr[p].ls=build(tr[p].ls,l,mid);
		tr[p].rs=build(tr[p].rs,mid+1,r);
		return p;
	}
	int add(int p,int l,int r,int x,int y){
		p=xin(p);
		if(l==r){
			tr[p].val+=y;
			return p;
		}
		int mid=(l+r)>>1;
		if(x<=mid) tr[p].ls=add(tr[p].ls,l,mid,x,y);
		else tr[p].rs=add(tr[p].rs,mid+1,r,x,y);
		up(p);
		return p;
	}
	int cal(int p1,int p2){
		return tr[p1].val-tr[p2].val;
	}
	int find(int p1,int p2,int l,int r,int x){
		if(!x) return 0;
		if(!p1) return 0;
		if(l==r) return cal(p1,p2);
		int mid=(l+r)>>1;
		if(x<=mid) return find(tr[p1].ls,tr[p2].ls,l,mid,x);
		else return cal(tr[p1].ls,tr[p2].ls)+find(tr[p1].rs,tr[p2].rs,mid+1,r,x);
	}	
}T[2];