A - 秋实大哥与小朋友
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
秋实大哥以周济天下，锄强扶弱为己任，他常对天长叹：安得广厦千万间，大庇天下寒士俱欢颜。
所以今天他又在给一群小朋友发糖吃。
他让所有的小朋友排成一行，从左到右标号。在接下去的时间中，他有时会给一段区间的小朋友每人v颗糖，有时会问第x个小朋友手里有几颗糖。
这对于没上过学的孩子来说实在太困难了，所以你看不下去了，请你帮助小朋友回答所有的询问。
Input
第一行包含两个整数n，m，表示小朋友的个数，以及接下来你要处理的操作数。
接下来的m行，每一行表示下面两种操作之一：
0 l r v : 表示秋实大哥给[l,r]这个区间内的小朋友每人v颗糖 1 x : 表示秋实大哥想知道第x个小朋友手里现在有几颗糖
1≤m,v≤100000，1≤l≤r≤n，1≤x≤n，1≤n≤100000000。
Output
对于每一个1 x操作，输出一个整数，表示第x个小朋友手里现在的糖果数目。
Sample input and output
3 4 | 1 |
解题报告
首先由于小朋友数目可以高达1e8，因此我们首先读入所有点，离散化..
之后上线段树还是上树状数组就随意了。。
我是采用的树状数组..这里我的离散化写的水，每次都要二分查位置（好吧，不要在意这些细节）
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
int size;
set<int>cv;
int point[maxn]; typedef struct oper
{
int l,r,v,ope;
oper(const int &ope, const int &l,const int &r,const int &v)
{
this->ope = ope , this->l = l , this->r = r , this->v = v;
}
}; queue<oper>query;
ll c[maxn]; inline int lowbit(int cur)
{
return cur&(-cur);
} void add(int l,ll v)
{
if (!l)
return;
while(l > )
{
c[l] += v;
l -= lowbit(l);
}
} ll find(int x)
{
ll res = ;
while(x <= size)
{
res += c[x];
x += lowbit(x);
}
return res;
} int main(int argc,char *argv[])
{
memset(c,,sizeof(c));
int n,m;
scanf("%d%d",&n,&m);
size = ;
while(m--)
{
int ope;
scanf("%d",&ope);
if (ope & )
{
int temp;
scanf("%d",&temp);
if (!cv.count(temp))
{
cv.insert(temp);
point[++size] = temp;
}
query.push(oper(ope,,,temp));
}
else
{
int l,r,v;
scanf("%d%d%d",&l,&r,&v);
if (!cv.count(l))
{
cv.insert(l);
point[++size] = l;
}
if (!cv.count(r))
{
cv.insert(r);
point[++size] = r;
}
query.push(oper(ope,l,r,v));
}
}
sort(point+,point++size);
while(!query.empty())
{
oper ss = query.front();query.pop();
if (ss.ope & )
{
int pos = lower_bound(point+,point+size,ss.v) - point;
printf("%lld\n",find(pos));
}
else
{
ll v = (ll)ss.v;
int pos = lower_bound(point+,point+size,ss.l) - point;
add(pos-,-v);
pos = lower_bound(point+,point+size,ss.r) - point;
add(pos,v);
}
}
return ;
}