「一本通 4.1 例 3」校门外的树

原题链接

Problem

加入和查询 /(2/) 个操作，加入操作每次加入一个区间，询问操作询问一个区间与多少个区间有交。

Solution

考虑使用 /(2/) 个树状数组维护，一个 /(c/) 数组记左端点数，另一个 /(c1/) 数组记右端点数。当询问 /([l,r]/) 区间时，在 /([1,r]/) 找左端点数，即有可能相交的；在 /([1,l-1]/) 找右端点数，即不能相交的。最后相减即为答案。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
	x=r*w;
}
const int N=2e6+100;
int c[N],n,c1[N];
int lowbit(int x){return x&-x;}
void add(int *c,int x,int y)
{
	while(x<=n)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
}
int query(int *c,int x)
{
	int ans=0;
	while(x>=1)
		ans+=c[x],x-=lowbit(x);
	return ans;	
}
main()
{
	int T;
	read(n);read(T);
	while(T--)
	{
		int op,l,r;read(op);
		read(l);read(r);
		if(op==1)add(c,l,1),add(c1,r,1);
		else printf("%lld/n",query(c,r)-query(c1,l-1));
	}
	return 0;
}