记录编号	316665	评测结果	AAAAAAAAAAAAAA
题目名称	线段覆盖	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	1.754 s
提交时间	2016-10-07 06:21:20	内存使用	15.55 MiB

#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 200010
int n,m,type;
struct Tree{
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define mid  ((l+r)>>1)
#define lc (rt<<1)
#define rc (rt<<1|1)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
	int Max[maxn<<2],Min[maxn<<2],lazy[maxn<<2],R[maxn<<2],L[maxn<<2];
	void Update(int rt){
		int data=lazy[rt];
		Min[rc]+=data; Max[rc]+=data;
		lazy[rc]+=data; lazy[lc]+=data;
		Min[lc]+=data; Max[lc]+=data;
		R[lc]+=data; R[rc]+=data; L[lc]+=data; L[rc]+=data;
		lazy[rt]=0;
	}
	void Insert(int s,int t,int rt,int l,int r){
		if(s<=l && t>=r){
			int data=0;
			if(type==1)data=1; if(type==2)data=-1;
			lazy[rt]+=data; Min[rt]+=data; Max[rt]+=data;
			R[rt]+=data; L[rt]+=data;	
			return ;
		}	
	
		if(lazy[rt])Update(rt);
		if(s<=mid)Insert(s,t,lson);
		if(t>mid) Insert(s,t,rson);
		Min[rt]=MIN(Min[lc],Min[rc]); Max[rt]=MAX(Max[lc],Max[rc]);
		R[rt]=R[rc]; L[rt]=L[lc];
	}
	int Querycon(int rt,int l,int r){
		if(Min[rt]>=1)return 1;
		if(Max[rt]==0)return 0;
		int ans=0; if(lazy[rt])Update(rt);
		ans+=Querycon(lson)+Querycon(rson);
		if(R[lc] && L[rc])ans--;
		return ans;	
	}
	int Querysum(int rt,int l,int r){
		if(Min[rt]>=1)return r-l+1;
		if(Max[rt]==0)return 0;
		if(lazy[rt])Update(rt);
		return 	Querysum(lson)+Querysum(rson);
	}
}T;
int main(){
	freopen("xdfg.in","r",stdin); freopen("xdfg.out","w",stdout);
	scanf("%d%d",&n,&m);
	while ( m-- ){
		int s,t;scanf("%d%d%d",&type,&s,&t);
		t+=s-1; T.Insert(s,t,1,1,n); 
		printf("%d ",T.Querycon(1,1,n));
		printf("%d\n",T.Querysum(1,1,n));
	}
	return 0;	
}