简单易懂权值线段树求条

#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
typedef long long ll;
const int N=1e6+6;
int mp[N]; 
struct dat{
	int l,r;
	ll sum;
	int pos[2];
};
struct Tree{
	dat tr[N<<2];
	void pushup(int id){
		tr[id].sum=tr[lid].sum+tr[rid].sum;
		if(tr[rid].sum) tr[id].pos[1]=tr[rid].pos[1];
		else tr[id].pos[1]=tr[lid].pos[1];
		if(tr[lid].sum) tr[id].pos[0]=tr[lid].pos[0];
		else tr[id].pos[0]=tr[rid].pos[0];
	}
	void build(int id,int l,int r){
		tr[id].l=l,tr[id].r=r;
		tr[id].sum=0;
		if(l==r){
			tr[id].pos[0]=tr[id].pos[1]=0;
			return ;
		}
		int mid=l+r>>1;
		build(lid,l,mid),build(rid,mid+1,r);
		pushup(id);
	}
	void modify(int id,int x,int v){
		if(tr[id].l==tr[id].r){
			tr[id].sum=v;
			tr[id].pos[0]=tr[id].pos[1]=x;
			return ;
		}
		int mid=tr[id].l+tr[id].r>>1;
		if(x<=mid) modify(lid,x,v);
		else modify(rid,x,v);
		pushup(id);
	}
	int del(int id,int tp){
		if(!tr[id].sum) return 0;
		if(tr[id].l==tr[id].r){
			int tmp=tr[id].sum;
			tr[id].sum=0;
			tr[id].pos[0]=tr[id].pos[1]=0;
			return tmp;
		}
		int tmp;
		if(tr[id].pos[tp]==tr[lid].pos[tp]) tmp=del(lid,tp);
		else tmp=del(rid,tp);
		pushup(id);
		return tmp;
	}
	void delbea(int id,int x){
		if(tr[id].l==tr[id].r){
			tr[id].sum=0;
			tr[id].pos[0]=tr[id].pos[1]=0;
			return ;
		}
		int mid=tr[id].l+tr[id].r>>1;
		if(x<=mid) delbea(lid,x);
		else delbea(rid,x);
		pushup(id);
	}
	ll query(){
		return tr[1].sum;
	}
}bea,cot;

int main(){
	int op,w,c;
	bea.build(1,1,1e6),cot.build(1,1,1e6);
	while(scanf("%d",&op)&&~op){
		if(op==1){
			scanf("%d%d",&w,&c);
			if(!mp[c]){
				mp[c]=w;
				bea.modify(1,w,w),cot.modify(1,c,c);
			}
		}
		else if(op==2){
			int tmp=cot.del(1,1);
			bea.delbea(1,mp[tmp]);
			mp[tmp]=0;
		}
		else{
			int tmp=cot.del(1,0);
			bea.delbea(1,mp[tmp]);
			mp[tmp]=0;
		}
	}
	printf("%lld %lld\n",bea.query(),cot.query());
	return 0;
}