Appoint description:
Description
秋实大哥以周济天下，锄强扶弱为己任，他常对天长叹：安得广厦千万间，大庇天下寒士俱欢颜。
所以今天他又在给一群小朋友发糖吃。
他让所有的小朋友排成一行，从左到右标号。在接下去的时间中，他有时会给一段区间的小朋友每人$v$颗糖，有时会问第$x$个小朋友手里有几颗糖。
这对于没上过学的孩子来说实在太困难了，所以你看不下去了，请你帮助小朋友回答所有的询问。
Input
第一行包含两个整数$n$，$m$，表示小朋友的个数，以及接下来你要处理的操作数。
接下来的$m$行，每一行表示下面两种操作之一：
0 l r v : 表示秋实大哥给[l,r]这个区间内的小朋友每人v颗糖
1 x : 表示秋实大哥想知道第x个小朋友手里现在有几颗糖
$1leq m, vleq 100000$，$1leq lleq rleq n$，$1leq xleq n$，$1leq nleq 100000000$。
Output
对于每一个$1$ $x$操作，输出一个整数，表示第$x$个小朋友手里现在的糖果数目。
Sample Input
3 4
0 1 3 1
1 2
0 2 3 3
1 3
Sample Output
1
4
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
const int maxn=100000;
ll tri[2*maxn+10];
int n,m;
set<int> judge;
vector<int> point;
struct Ope{
int op,l,r,v,pos;
};
int lowbit(int i)
{
return i&(-i);
}
ll query(int pos)
{
ll sum=0;
while(pos<=point.size())
{
sum+=tri[pos];
pos+=lowbit(pos);
}
return sum;
}//区间更新中的单点查询
void update(int l,int r,int v)
{
while(r>0)
{
tri[r]+=v;
r-=lowbit(r);
}
int k=l-1;
while(k>0)
{
tri[k]-=v;
k-=lowbit(k);
}
}//区间更新
int main()
{
while(~scanf("%d %d",&n,&m))
{
queue<Ope> opq;
judge.clear();
point.clear();
MM(tri,0);
for(int k=1;k<=m;k++)
{
int w,l,r,v,pos;
scanf("%d",&w);
if(w==0)
{
scanf("%d %d %d",&l,&r,&v);
if(!judge.count(l))
{
judge.insert(l);
point.push_back(l);
}
if(!judge.count(r))
{
judge.insert(r);
point.push_back(r);
}
opq.push((Ope){0,l,r,v,0});
}
else
{
scanf("%d",&pos);
if(!judge.count(pos))
{
judge.insert(pos);
point.push_back(pos);
}
opq.push((Ope){1,0,0,0,pos});
}
}
sort(point.begin(),point.end());//用point来离散化
while(opq.size())
{
Ope cur=opq.front();opq.pop();
if(cur.op==1)
{
int pos=lower_bound(point.begin(),point.end(),cur.pos)-point.begin()+1;
printf("%lld
",query(pos));
}//pos代表离散化后在BIT中的位置
else
{
int l=lower_bound(point.begin(),point.end(),cur.l)-point.begin()+1;
int r=lower_bound(point.begin(),point.end(),cur.r)-point.begin()+1;
update(l,r,cur.v);
}
}
}
return 0;
}
1：set可以用来判重judge.count(判断元素的值)，但是不能对其进行迭代器的加减法；
2：对要进行操作的点进行离散化；
3：BIT区间更新+单点查询