C++11(clang++ 3.9) 解法, 执行用时: 206ms, 内存消耗: 22364K, 提交时间: 2018-07-20 22:02:24

#include<bits/stdc++.h>
struct node;
typedef node* pn;
struct node{
	pn c[2];
	int l,r;
	bool red,nil;
	int ans,cl,cr,b2r;
	void col(int c){
		red=c;
		up();
	}
	void black_down(){
		c[0]->col(0);
		c[1]->col(0);
		col(1);
	}
	void up(){
		ans=c[0]->ans+c[1]->ans;
		if(red){
			cl=c[0]->b2r;
			cr=c[1]->b2r;
			b2r=0;
		}else{
			cl=cr=b2r=0;
			if(c[1]->red)b2r+=(c[0]->cl+c[0]->cr);
			else ans+=c[0]->cl+c[0]->cr*2;
			if(c[0]->red)b2r+=(c[1]->cl+c[1]->cr);
			else ans+=c[1]->cr+c[1]->cl*2;
		}
	}
}ns[1000007],*rt,*np=ns;
pn range(int l,int r){
	node*w=np++;
	w->c[0]=w->c[1]=ns;
	w->l=l;
	w->r=r;
	w->red=0;
	w->nil=1;
	w->ans=w->cl=w->cr=0;
	w->b2r=r-l+1;
	return w;
}
pn leaf(pn rt,int x){	
	pn w=np++;
	w->c[0]=range(rt->l,x);
	w->c[1]=range(x+1,rt->r);
	w->l=w->r=x;
	w->nil=0;
	w->col(1);
	return w;
}
void rot(pn& w,int d){
	pn u=w->c[d];
	w->c[d]=u->c[!d];
	u->c[!d]=w;
	std::swap(w->red,u->red);
	w->up();
	w=u;
	w->up();
}
void ins(pn& rt,int x){
	if(rt->nil){
		rt=leaf(rt,x);
		return;
	}
	int d=x>rt->l;
	pn& w=rt->c[d];
	ins(w,x);
	rt->up();
	if(w->red){
		if(w->c[d]->red){
			if(rt->c[!d]->red)rt->black_down();
			else rot(rt,d);
		}else if(w->c[!d]->red){
			if(rt->c[!d]->red)rt->black_down();
			else rot(w,!d),rot(rt,d);
		}
	}
}
pn get(pn rt,int x){
	if(rt->nil)return range(rt->l,std::min(rt->r,x));
	node*w=np++;
	*w=*rt;
	if(x>w->l)w->c[1]=get(w->c[1],x);
	else{
		w->c[0]=get(w->c[0],x);
		node*u=np++;
		*u=*w->c[1];
		u->ans=u->cl=u->cr=u->b2r=0;
		w->c[1]=u;
	}
	w->up();
	return w;
}
int _(int l,int r){
	int x=0;
	if(scanf("%d",&x)==1&&l<=x&&x<=r)return x;
	assert(0); 
}
int main(){
	range(1,0);
	rt=range(1,1e8);
	for(int n=_(1,200000),op,x;n--;){
		op=_(1,2);
		x=_(1,1e8);
		if(op==1){
			ins(rt,x);
			rt->col(0);
		}else{
			pn np0=np,tmp=get(rt,x);
			printf("%d\n",tmp->ans);
			np=np0;
		}
	}
	return 0;
}