记录编号	60599	评测结果	AAAAAAAAAA
题目名称	贪婪大陆	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.475 s
提交时间	2013-05-27 14:27:23	内存使用	7.94 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEL=200001;
int n,m;
class SEGMENT{
public:
	int l,r;
	int lchild,rchild;
	int sum;//区间和
};
SEGMENT ls[SIZEL],rs[SIZEL];//布雷区间的左,右端点数区间和
#define now s[root]
int tot;
void build(SEGMENT s[SIZEL],int root,int x,int y){
	#define onit s[root]
	onit.l=x,onit.r=y;
	onit.sum=0;
	if(y>x){
		int mid=(x+y)>>1;
		onit.lchild=++tot;
		build(s,tot,x,mid);
		onit.rchild=++tot;
		build(s,tot,mid+1,y);
	}
	else{
		onit.lchild=-1;
		onit.rchild=-1;
	}
}
int getsum(SEGMENT s[SIZEL],int root,int x,int y){
	if(root==-1||now.r<x||now.l>y) return 0;
	if(now.l>=x&&now.r<=y) return now.sum;
	return getsum(s,now.lchild,x,y)+getsum(s,now.rchild,x,y);
}
void add(SEGMENT s[SIZEL],int root,int x){//a[x]++
	if(root==-1||now.r<x||now.l>x) return;
	now.sum++;
	add(s,now.lchild,x);
	add(s,now.rchild,x);
}
void init(void){
	scanf("%d%d",&n,&m);
	tot=0;
	build(ls,0,1,n);
	tot=0;
	build(rs,0,1,n);
}
void work(void){
	int count=0;
	int i;
	int op,lnow,rnow,temp;
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&op,&lnow,&rnow);
		if(op==1){//布雷
			count++;
			add(ls,0,lnow);
			add(rs,0,rnow);
		}
		else{//询问
			temp=getsum(rs,0,1,lnow-1)+getsum(ls,0,rnow+1,n);
			printf("%d\n",count-temp);
		}
	}
}
int main(){
	freopen("greedisland.in","r",stdin);
	freopen("greedisland.out","w",stdout);
	init();
	work();
	return 0;
}