记录编号	141130	评测结果	AAAAAAAAAAAAAA
题目名称	线段覆盖	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	1.607 s
提交时间	2014-11-29 13:08:11	内存使用	14.82 MiB

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#define root 1,0,L
#define lson node<<1,l,(l+r)>>1
#define rson node<<1|1,((l+r)>>1)+1,r
struct S{
	int num,sum,len;
	bool l,r;
}tree[800004];
char * ptr=(char *)malloc(5000000);
inline void update(int node,int l,int r){
	if(tree[node].num){
			tree[node].sum=1;
			tree[node].l=1;
			tree[node].r=1;
			tree[node].len=r-l;
	}
	else{
		tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum-(tree[node<<1].r&tree[node<<1|1].l);
		tree[node].l=tree[node<<1].l;
		tree[node].r=tree[node<<1|1].r;
		tree[node].len=tree[node<<1].len+tree[node<<1|1].len+(tree[node<<1].r&tree[node<<1|1].l);
	}
}
inline void add(int node,int l,int r,int a,int b,int x){
	if(a<=l&&r<=b){
		tree[node].num+=x;
		if(l!=r)update(node,l,r);
		else{
			tree[node].sum=(bool)tree[node].num;
			tree[node].l=(bool)tree[node].num;
			tree[node].r=(bool)tree[node].num;
			tree[node].len=0;
		}
		return;
	}
	if(a>r||b<l)return;
	add(lson,a,b,x);
	add(rson,a,b,x);
	update(node,l,r);
}
inline void in(int &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
int main(){
	freopen("xdfg.in","r",stdin);
	freopen("xdfg.out","w",stdout);
	fread(ptr,1,5000000,stdin);
	int L,n,flag,a,T;
	in(L),in(n);
	while(n--){
		in(flag),in(a),in(T);
		add(root,a,a+T,flag-1?-1:1);
		printf("%d %d\n",tree[1].sum,tree[1].len);
	}
}