记录编号	9016	评测结果	AAAAAAAAAAAAAA
题目名称	线段覆盖	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	4.329 s
提交时间	2009-02-14 14:08:20	内存使用	13.99 MiB

/* 
 * Problem: 线段覆盖问题
 * Author: Guo Jiabao
 * Time: 2009.2.13 22:10
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXL=400001;
struct seg_node
{
	int a,b,m;
	int tlen,cnt,cloth;
	bool lt,rt;
	seg_node *left,*right;
	inline int llen() {return left?left->tlen:0;}
	inline int rlen() {return right?right->tlen:0;}
	inline int lcnt() {return left?left->cnt:0;}
	inline int rcnt() {return right?right->cnt:0;}
};

int L,Q,SC=-1;
seg_node *root;
seg_node SS[MAXL];

seg_node* new_seg(int a,int b)
{
	SS[++SC].m=(a+b)/2;
	SS[SC].a=a; SS[SC].b=b;
	SS[SC].left=SS[SC].right=0;
	SS[SC].cloth=SS[SC].tlen=SS[SC].cnt=0;
	SS[SC].lt=SS[SC].rt=false;
	return &SS[SC];
}

void seg_build(seg_node *&p,int a,int b)
{
	p=new_seg(a,b);
	if (b>a)
	{
		seg_build(p->left,a,p->m);
		seg_build(p->right,p->m+1,b);
	}
}

void seg_edit(seg_node *p,int a,int b,int c)
{
	if (a==p->a && b==p->b)
	{
		if (c==1)
			p->cloth++;
		else
			p->cloth--;
	}
	else
	{
		if (b<=p->m)
			seg_edit(p->left,a,b,c);
		else if (a>=p->m+1)
			seg_edit(p->right,a,b,c);
		else
		{
			seg_edit(p->left,a,p->m,c);
			seg_edit(p->right,p->m+1,b,c);
		}
	}
	if (p->cloth>=1)
	{
		p->tlen=p->b-p->a+1;
		p->cnt=1;
		p->lt=p->rt=true;
	}
	else
	{
		p->lt=p->left && p->left->lt;
		p->rt=p->right && p->right->rt;
		p->tlen=p->llen() + p->rlen();
		p->cnt=p->lcnt() + p->rcnt();
		if (p->left && p->left->rt && p->right && p->right->lt) //p->left最右边 且 p->right 最左边
			p->cnt--;
	}
}

int main()
{
	freopen("xdfg.in","r",stdin);
	freopen("xdfg.out","w",stdout);
	scanf("%d%d",&L,&Q);
	seg_build(root,1,L);
	for (int i=1;i<=Q;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&c,&a,&b);
		seg_edit(root,a,a+b-1,c);
		printf("%d %d\n",root->cnt,root->tlen);
	}
	return 0;
}