记录编号	55356	评测结果	AAAAAAAAAAAAAA
题目名称	线段覆盖	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	4.237 s
提交时间	2013-03-18 12:22:33	内存使用	17.01 MiB

#include<fstream>
using namespace std;
ifstream fi("xdfg.in");
ofstream fo("xdfg.out");
class sss
{
public:
	int left,right,Lchild,Rchild;//left,right为区间起点终点，Lchild,Rchild是左儿子右儿子
	bool coverleft,coverright;//左右区间是否被覆盖
	int len;//把以root为根的子树中所有的黑布条叠加起来，被染黑区间的总长度。
	int count;//被覆盖次数
	int interval;//黑色区间的个数
	int connect;//左右区间是否连接
}tree[400000];
int line,n,total;
void maketree(int root,int l,int r)
{
	tree[root].left=l;
	tree[root].right=r;
	tree[root].coverleft=0;
	tree[root].coverright=0;
	tree[root].count=0;
	tree[root].len=0;
	tree[root].interval=0;
	tree[root].connect=0;
	if(l<r-1)
	{
		int mid=(l+r)/2;
		total++;
		tree[root].Lchild=total;
		maketree(total,l,mid);
		total++;
		tree[root].Rchild=total;
		maketree(total,mid,r);
	}
	else
	{
		tree[root].Lchild=-1;
		tree[root].Rchild=-1;
	}
}
void dealwithit(int root)
{
	if(tree[root].count>0)
		tree[root].len=tree[root].right-tree[root].left;
	else 
		if(tree[root].Lchild!=-1)
		{
			tree[root].len=tree[tree[root].Lchild].len+tree[tree[root].Rchild].len;
		}
		else{tree[root].len=0;}
	
	if(tree[root].count>0)
		tree[root].coverleft=true,tree[root].coverright=true;
	else 
		if(tree[root].Lchild!=-1)
		{
			tree[root].coverleft=tree[tree[root].Lchild].coverleft;
			tree[root].coverright=tree[tree[root].Rchild].coverright;
		}
		else
		{
			tree[root].coverleft=false;
			tree[root].coverright=false;
		}
		
	if(tree[root].Lchild!=-1)
	{
		if(tree[tree[root].Rchild].coverleft&&tree[tree[root].Lchild].coverright)
			tree[root].connect=1;
		else 
			tree[root].connect=0;
	}
	else{tree[root].connect=0;}
	
	if(tree[root].count>0)
		tree[root].interval=1;
	else 
		tree[root].interval=tree[tree[root].Lchild].interval+tree[tree[root].Rchild].interval-tree[root].connect;
}
void add(int root,int a,int b)
{
	if(root==-1)return;
	if(tree[root].left>=a&&tree[root].right<=b)
		tree[root].count++;
	else
	{
		if(b<=tree[root].left||tree[root].right<=a)return;
		add(tree[root].Lchild,a,b);
		add(tree[root].Rchild,a,b);
	}
	dealwithit(root);
}
void del(int root,int a,int b)
{
	if(root==-1)return;
	if(tree[root].left>=a&&tree[root].right<=b)tree[root].count--;
	else
	{
	if(b<=tree[root].left||tree[root].right<=a)return;
	del(tree[root].Lchild,a,b);
	del(tree[root].Rchild,a,b);
	}
	dealwithit(root);
}
int main()
{
	fi>>line>>n;total=0;
	maketree(total,0,line);
	int style,x,y;
	for(int i=1;i<=n;i++)
	{
		fi>>style>>x>>y;
		if(style==1)add(0,x,x+y);
		if(style==2)del(0,x,x+y);
		fo<<tree[0].interval<<' '<<tree[0].len<<endl;
	/*for(int i=0;i<=total;i++)
	fo<<i<<' '<<tree[i].left<<' '<<tree[i].right<<' '<<tree[i].count<<' '<<tree[i].len<<endl;
	fo<<endl;*/
	}
	return 0;
}