题解 P4939 【Agent2】

先看题目描述，总结起来就是：

1. 区间修改

2. 单点查询

于是：

标准的线段树、树状数组题目。

墙裂推荐树状数组~~（只要能用）~~，码量小，空间和时间都比线段树优

所以，这里只讲树状数组

这里的树状数组采用了差分和前缀和的思想，利用树状数组维护差分数组的前缀和（不懂树状数组的出门左转这里。话说会树状数组的还看题解干嘛）

久违的放代码时间：

#include<iostream>
using namespace std;
int n,m;
long long c[100000005];
inline int lowbit(int x){return x&(-x);}//树状数组的标志
void add(int x,int t){//单点加（为什么要t看后面）
	while(x<=n){
		c[x]+=t;
		x+=lowbit(x);
	}
}
long long sum(int x){//求和
	long long ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	int opt,x,y;
	for(int i=0;i<m;i++){
		cin>>opt;
		if(!opt){
			cin>>x>>y;
			add(x,1);
			add(y+1,-1);//差分，用到上面的t了~
		}
		else{
			cin>>x;
			cout<<sum(x)<<endl;
		}
	}
	return 0;
}//完结撒花！