记录编号	84898	评测结果	AAAAAAAAAAAAAA
题目名称	线段覆盖	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	1.543 s
提交时间	2013-12-21 18:57:29	内存使用	11.29 MiB

#include <cstdio>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define M(a,b) (((a)+(b))>>1)

const int MAXLEN=524300;

int n,m,a,b,c;

struct segtr
{
	int l[MAXLEN],r[MAXLEN],co[MAXLEN],ct[MAXLEN],len[MAXLEN];
	bool lc[MAXLEN],rc[MAXLEN];
	void build(int p,int pl,int pr)
	{
		l[p]=pl; r[p]=pr;
		if (pl<pr)
		{
			build(L(p),pl,M(pl,pr));
			build(R(p),M(pl,pr)+1,pr);
		}
	}
	void insert(int p,int pl,int pr,int tt)
	{
		if (pl==l[p]&&pr==r[p])
		{
			if (tt==1) co[p]++;
			else if (tt==2) co[p]--;
		}
		else
		{
			if (pr<=M(l[p],r[p]))
				insert(L(p),pl,pr,tt);
			else if (pl>M(l[p],r[p]))
				insert(R(p),pl,pr,tt);
			else
			{
				insert(L(p),pl,M(l[p],r[p]),tt);
				insert(R(p),M(l[p],r[p])+1,pr,tt);
			}
		}
		if (co[p])
		{
			len[p]=r[p]-l[p]+1;
			ct[p]=1;
			lc[p]=rc[p]=true;
		}
		else
		{
			if (l[p]==r[p])
			{
				lc[p]=rc[p]=false;
				len[p]=0; ct[p]=0;
			}
			else
			{
				lc[p]=lc[L(p)];
				rc[p]=rc[R(p)];
				len[p]=len[L(p)]+len[R(p)];
				ct[p]=ct[L(p)]+ct[R(p)];
				if (rc[L(p)]&&lc[R(p)]) ct[p]--;
			}
		}		
	}
};

segtr T;

int main()
{
	freopen("xdfg.in","r",stdin);
	freopen("xdfg.out","w",stdout);
	scanf("%d%d",&n,&m);
	T.build(1,1,n);
	while (m--)
	{
		scanf("%d%d%d",&c,&a,&b);
		T.insert(1,a,a+b-1,c);
		printf("%d %d\n",T.ct[1],T.len[1]);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}