记录编号	431728	评测结果	AAAAAAAAAA
题目名称	贪婪大陆	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.255 s
提交时间	2017-08-01 17:29:45	内存使用	3.37 MiB

#include<cstdio>
#include <iostream>
#include<algorithm>
using namespace std;
/*
	一开始以为是裸区间加，后来发现并不是。 
	建立以1-n为坐标的线段树； 
	维护区间左端点数和右端点数；
	用ans表示L-R的地雷种类时；
	ans=1-R左端点数减去1-（L-1）右端点数；
	正确性：1-r左端点数等于1-r覆盖区间的总数；但是有一部分区间右端点未必在l-r内
	而1-l-1右端点数，就是那些不在l-r区间内区间总数；
	相减即为答案； 
*/
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=1e5+10;
int n,m;
int lsum[maxn*4];
int rsum[maxn*4];
inline void add(int o,int l,int r,int nl,int nr,int vl,int vr){
	if(l>=nl&&r<=nr){
		lsum[o]+=vl;
		rsum[o]+=vr;
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls+1;
	if(m>=nl)add(ls,l,m,nl,nr,vl,vr);
	if(m<nr)add(rs,m+1,r,nl,nr,vl,vr);
	lsum[o]=lsum[ls]+lsum[rs];
	rsum[o]=rsum[ls]+rsum[rs]; 
}
inline int find(int o,int l,int r,int nl,int nr,int t){
	if(l>=nl&&r<=nr){
		if(t==1)return lsum[o];
		if(t==2)return rsum[o];
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls+1;
	int ans=0;
	if(m>=nl)ans+=find(ls,l,m,nl,nr,t);
	if(m<nr)ans+=find(rs,m+1,r,nl,nr,t);
	return ans;
}
int main(){
	freopen("greedisland.in","r",stdin);
	freopen("greedisland.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int c=read(),x=read(),y=read();
		if(c==1){
			add(1,1,n,x,x,1,0);
			add(1,1,n,y,y,0,1);
		}
		if(c==2){
			int ans=find(1,1,n,1,y,1)-find(1,1,n,1,x-1,2);
			printf("%d\n",ans);
		}
	}
	return 0;
}