P3586，用的动态开点权值线段树

#include<cstdio>
const int M=1e6+10;

struct node{
	int lc,rc,cnt;
	long long sum;
}tr[M*20];
int root=1,cntp=1;
void pushup(int k){
	tr[k].cnt=tr[tr[k].lc].cnt+tr[tr[k].rc].cnt;
	tr[k].sum=tr[tr[k].lc].sum+tr[tr[k].rc].sum;
}
void insert(int &k,int l,int r,int pos){//线段树插入pos值 
	if(!k) k=++cntp;
	if(l==pos and r==pos){
		tr[k].sum+=pos;
		tr[k].cnt++;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) insert(tr[k].lc,l,mid,pos);
	else insert(tr[k].rc,mid+1,r,pos);
	pushup(k);
}
void remove(int &k,int l,int r,int pos){//线段树删除pos值 
	if(!k) return;
	if(l==pos and r==pos){
		tr[k].sum-=pos;
		tr[k].cnt--;
		if(tr[k].cnt==0) k=0;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) remove(tr[k].lc,l,mid,pos);
	else remove(tr[k].rc,mid+1,r,pos);
	pushup(k);
	if(tr[k].cnt==0) k=0;
}
int query_cnt(int k,int l,int r,int L,int R){
	if(!k) return 0;
	if(L<=l and r<=R) return tr[k].cnt;
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans+=query_cnt(tr[k].lc,l,mid,L,R);
	if(R>mid)  ans+=query_cnt(tr[k].rc,mid+1,r,L,R);
	return ans;
}
long long query_sum(int k,int l,int r,int L,int R){
	if(!k) return 0;
	if(L<=l and r<=R) return tr[k].sum;
	int mid=(l+r)>>1;
	long long ans=0;
	if(L<=mid) ans+=query_sum(tr[k].lc,l,mid,L,R);
	if(R>mid)  ans+=query_sum(tr[k].rc,mid+1,r,L,R);
	return ans;
}

int n,m,a[M];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		char op[2];
		scanf(" %s",op);
		scanf("%d%d",&u,&v);
		if(op[0]=='U'){
			if(a[u]!=0) remove(root,1,1e9,a[u]);
			if(v!=0) insert(root,1,1e9,v);
			a[u]=v;
		}
		if(op[0]=='Z'){
			long long sum=query_sum(1,1,1e9,1,v)-query_sum(1,1,1e9,v,v);
			int cnt=query_cnt(1,1,1e9,v,1e9);
			if(sum>=(long long)(u-cnt)*v) printf("TAK\n");
			else printf("NIE\n");
		}
	}
	return 0;
}