[bzoj 4942][noi 2017]整数【線分樹】

【テーマの説明】
 http://www.lydsy.com/JudgeOnline/upload/Noi2017D1.pdf
【題解】
 各操作は進退せずに暴力的に修正します.そうでないと線分樹で次の退位できるところを見つけて、中間部分を反転します.(0は1、1は0になります.)
30のバイナリビットをまとめて保存します.このように修正すると最大2回まで後退します.複雑度O(n logn)

/* --------------
    user Vanisher
    problem bzoj-4942 
----------------*/
# include 
# define 	ll 		long long
# define 	N 		1000100
# define 	inf 	(1<<30)
using namespace std;
int read(){
	int tmp=0, fh=1; char ch=getchar();
	while (ch'9'){if (ch=='-') fh=-1; ch=getchar();}
	while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
	return tmp*fh;
}
struct Tree{
	int pl,pr,l,r,tag,num0,num1;
}T[N*3];
int now[N],n,place,rt;
int build(int l, int r){
	int p=++place;
	T[p].l=l; T[p].r=r;
	T[p].num0=0; T[p].num1=r-l+1;
	if (l!=r){
		int mid=(l+r)/2;
		T[p].pl=build(l,mid);
		T[p].pr=build(mid+1,r);
	}
	return p;
}
void pushtag(int p){
	if (T[p].tag%2!=0){
		swap(T[p].num0,T[p].num1);
		if (T[p].l!=T[p].r) T[T[p].pl].tag++, T[T[p].pr].tag++;
			else now[T[p].l]=inf-1-now[T[p].l];
	}
	T[p].tag=0;
}
void reser(int p, int l, int r){
	pushtag(p);
	if (T[p].l==l&&T[p].r==r){
		T[p].tag++; return;
	}
	int mid=(T[p].l+T[p].r)/2;
	if (mid>=r) reser(T[p].pl,l,r);
		else if (mid=x) join1(T[p].pl,x); else join1(T[p].pr,x);
	}
}
void join0(int p, int x){
	pushtag(p); T[p].num0--;
	if (T[p].l!=T[p].r){
		int mid=(T[p].l+T[p].r)/2;
		if (mid>=x) join0(T[p].pl,x); else join0(T[p].pr,x);
	}
}
void del1(int p, int x){
	pushtag(p); T[p].num1++;
	if (T[p].l!=T[p].r){
		int mid=(T[p].l+T[p].r)/2;
		if (mid>=x) del1(T[p].pl,x); else del1(T[p].pr,x);
	}
}
void del0(int p, int x){
	pushtag(p); T[p].num0++;
	if (T[p].l!=T[p].r){
		int mid=(T[p].l+T[p].r)/2;
		if (mid>=x) del0(T[p].pl,x); else del0(T[p].pr,x);
	}
}
void getdown(int p, int x){
	pushtag(p);
	if (T[p].l==T[p].r) return;
	int mid=(T[p].l+T[p].r)/2;
	if (x<=mid) getdown(T[p].pl,x);
		else getdown(T[p].pr,x);
}
int findnex0(int p, int l){
	pushtag(p);
	if (T[p].num0==0) return -1;
	if (T[p].l==T[p].r&&T[p].num0==1) return T[p].l;
	int mid=(T[p].l+T[p].r)/2,k;
	if (T[p].l<=l){
		if (l<=mid){
			k=findnex0(T[p].pl,l);
			if (k!=-1) return k;
			return findnex0(T[p].pr,l);
		}
		else return findnex0(T[p].pr,l);
	}
	else {
		pushtag(T[p].pl); pushtag(T[p].pr);
		if (T[T[p].pl].num0!=0)
			return findnex0(T[p].pl,l);
				else return findnex0(T[p].pr,l);
	}
}
int findnex1(int p, int l){
	pushtag(p);
	if (T[p].num1==0) return -1;
	if (T[p].l==T[p].r&&T[p].num1==1) return T[p].l;
	int mid=(T[p].l+T[p].r)/2,k;
	if (T[p].l<=l){
		if (l<=mid){
			k=findnex1(T[p].pl,l);
			if (k!=-1) return k;
			return findnex1(T[p].pr,l);
		}
		else return findnex1(T[p].pr,l);
	}
	else {
		pushtag(T[p].pl); pushtag(T[p].pr);
		if (T[T[p].pl].num1!=0)
			return findnex1(T[p].pl,l);
				else return findnex1(T[p].pr,l);
	}
}
void modify(int p, int num){
	if (num==0) return;
	getdown(rt,p);
	if (now[p]==inf-1) del1(rt,p);
	if (now[p]==0) del0(rt,p);
	now[p]=now[p]+num;
	if (now[p]>=inf) {
		now[p]=now[p]-inf;
		int nex=findnex1(rt,p+1);
		if (p+1<=nex-1) reser(rt,p+1,nex-1);
		modify(nex,1);
	}
	if (now[p]<0) {
		now[p]=now[p]+inf;
		int nex=findnex0(rt,p+1);
		if (p+1<=nex-1) reser(rt,p+1,nex-1);
		modify(nex,-1);
	}
	if (now[p]==inf-1) join1(rt,p);
	if (now[p]==0) join0(rt,p);
}
int main(){
	n=read(); 
	int t1=read(), t2=read(), t3=read(),tmp1,tmp2,a,b,opt,fh;
	rt=build(0,n);
	for (int i=1; i<=n; i++){
		opt=read();
		if (opt==1){
			a=read(), b=read();
			if (a<0) fh=-1,a=-a; else fh=1;
			tmp1=(a%(1<>(30-b%30); 
			modify(b/30,tmp1*fh); modify(b/30+1,tmp2*fh);
		}
		else {
			a=read();
			getdown(rt,a/30);
			if ((now[a/30]&(1<