记录编号	232028	评测结果	AAAAAAAAAAAAAA
题目名称	线段覆盖	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	2.624 s
提交时间	2016-02-28 16:38:30	内存使用	13.02 MiB

#include<cstdio>
#define T(a,b) a=b=1
#define F(a,b) a=b=0
struct Node{
	int l,r,L,R;
	bool coverleft,coverright;
	int len,count,nub;
	int connect;//左右区间是否连接
}G[400000];
int line,n,cnt;
void Build(int root,int l,int r){
	G[root].l=l;G[root].r=r;
	F(G[root].coverleft,G[root].coverright);
	F(G[root].count,G[root].len);
	F(G[root].nub,G[root].connect);
	if(l<r-1){	
		int mid=(l+r)>>1;
		cnt++; G[root].L=cnt;
		Build(cnt,l,mid);
		cnt++; G[root].R=cnt;
		Build(cnt,mid,r);
	}
	else G[root].L=G[root].R=-1;
}
void update(int root){
	//update len
	if(G[root].count>0) G[root].len = G[root].r-G[root].l;
	else if(G[root].L!=-1) G[root].len= G[ G[root].L ].len + G[ G[root].R ].len;
	else G[root].len=0;
	//update coverleft and coverright
	if(G[root].count>0) T(G[root].coverleft,G[root].coverright);
	else if(G[root].L!=-1){
			G[root].coverleft = G[ G[root].L ].coverleft;
			G[root].coverright= G[ G[root].R ].coverright;
	}
	else F(G[root].coverleft,G[root].coverright);
	//update connect
	if(G[root].L !=-1 ){
		if(G[G[root].R].coverleft && G[G[root].L].coverright) G[root].connect=1;
		else G[root].connect=0;
	}
	else G[root].connect=0;
	//update nub
	if(G[root].count>0) G[root].nub=1;
	else  G[root].nub = G[G[root].L].nub + G[G[root].R].nub - G[root].connect;//if connect then nub--
}
void add(int root,int a,int b){
	if(root==-1) return;
	if(a<= G[root].l && G[root].r<=b) G[root].count++;
	else{
		if(b <=G[root].l || G[root].r <=a) return;
		add(G[root].L,a,b);add(G[root].R,a,b);
	}
	update(root);
}
void del(int root,int a,int b){
	if(root==-1)return;
	if( a<= G[root].l && G[root].r <=b)G[root].count--;
	else{
		if(b<=G[root].l||G[root].r<=a) return;
		del(G[root].L,a,b);del(G[root].R,a,b);
	}
	update(root);
}
void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=x*10+ch-'0',ch=getchar(),ch>'!');
	return;
}
int main(){
	freopen("xdfg.in","r",stdin);
	freopen("xdfg.out","w",stdout);
	read(line);read(n);
	//scanf("%d%d",&line,&n);
	Build(0,0,line);
	int x,y,type;
	for(int i=1;i<=n;i++){
		read(type);read(x);read(y);
		//scanf("%d%d%d",&type,&x,&y);
		if(type==1) add(0,x,x+y);
		if(type==2) del(0,x,x+y);
		printf("%d %d\n",G[0].nub,G[0].len);
	}
	return 0;
}