记录编号	472189	评测结果	AAAAAAAAAA
题目名称	贪婪大陆	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.291 s
提交时间	2017-11-07 13:58:54	内存使用	9.47 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define lson lc[rt],l,mid
#define rson rc[rt],mid+1,r

using namespace std;

const int M=100010;

int n,m,cnt;
int lc[M<<3],rc[M<<3],sum[M<<3],root[2];

inline int read(){

	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1;ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar(); }
	return x*f;

}

inline int query(int s,int t,int rt,int l,int r){

	if(s>t) return 0;
	if(!rt) return 0;

	if(s<=l&&r<=t) return sum[rt];

	int mid=l+r>>1,res=0;

	if(s<=mid) res+=query(s,t,lson);
	if(t>mid)  res+=query(s,t,rson);

	return res;

}

inline void update(int pos,int &rt,int l,int r){

	if(!rt) rt=++cnt;
	if(l==r) { ++sum[rt]; return ; }

	int mid=l+r>>1;

	if(pos<=mid) update(pos,lson);
	else update(pos,rson);

	sum[rt]=sum[lc[rt]]+sum[rc[rt]];

}

int main(){

	freopen("greedisland.in","r",stdin);
	freopen("greedisland.out","w",stdout);

	n=read(); m=read(); int xx,yy,opt;

	while(m--){

		opt=read(); xx=read(); yy=read();

		if(opt==1) { update(xx,root[0],1,M-10); update(yy,root[1],1,M-10); }

		else printf("%d\n",query(1,yy,root[0],1,M-10)-query(1,xx-1,root[1],1,M-10));

	}	return 0;

}