洛谷 P2184 贪婪大陆

难度： 蓝

算法： 树状数组，线段树

这道题就相当于增加一个区间和查询一个区间内有多少个区间。

开两个数组，记为 $l$ 和 $r$。 分别记录该点的左端点个数和右端点个数。

对于增加区间 $[x,y]$，令 $l_x++$，$r_y++$。

对于查询 $[x,y]$，我们发现：

在区间 $[x,y]$ 中的区间，左端点不大于 $y$，右端点不小于 $x$。统计答案时只需要把左端点不大于 $y$ 的区间数减去右端点小于 $x$ 的区间数即可。

使用树状数组维护单点修改，区间查询操作。

代码见下（35 行）：

#include<bits/stdc++.h>
#define lowbit(a) a&-a 
using namespace std;
int n,q,op,l,r,le[100010],ri[100010],s1,s2;
void add(int u,int t){
	while(u<=n){
		if(t==1) le[u]++;
		else ri[u]++;
		u+=lowbit(u);
	}
}
int que(int u,int t){
	int ans=0;
	while(u){
		if(t==1) ans+=le[u];
		else ans+=ri[u];
		u-=lowbit(u);
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&q);
	while(q--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			add(l,1);
			add(r,2);
		}
		else{
			s1=que(r,1);
			s2=que(l-1,2);
			printf("%d\n",s1-s2);
		}
	}
}