题目链接：http://acm.uestc.edu.cn/#/problem/show/1059
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
秋实大哥以周济天下，锄强扶弱为己任，他常对天长叹：安得广厦千万间，大庇天下寒士俱欢颜。
所以今天他又在给一群小朋友发糖吃。
他让所有的小朋友排成一行，从左到右标号。在接下去的时间中，他有时会给一段区间的小朋友每人vv颗糖，有时会问第xx个小朋友手里有几颗糖。
这对于没上过学的孩子来说实在太困难了，所以你看不下去了，请你帮助小朋友回答所有的询问。
Input
第一行包含两个整数nn，mm，表示小朋友的个数，以及接下来你要处理的操作数。
接下来的mm行，每一行表示下面两种操作之一：
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
对于每一个11 xx操作，输出一个整数，表示第xx个小朋友手里现在的糖果数目。
Sample input and output
| Sample Input | Sample Output |
|---|---|
3 4 |
1 |
用了跟UESTC 1057一样的模板，可以说跟1057一脉相承（click to http://www.cnblogs.com/dilthey/p/6824863.html）
当然啦，如果是完全一样的写法，还不如不做，肯定有不同之处。
不难看到，这题的n达到了1e8，不可能开一个4倍的MAXN的node数组，这时候便需要进行离散化。
引用：
(source: http://blog.csdn.net/code12hour/article/details/46596503)
然后观察了半天网上的题解，看的我莫名烦躁，就自己写想了个办法离散化；
①我们可以用栈来存储所有的input的操作，等到所有input完成，建树操作也完成后，再从栈里一个个取出操作，完成这些操作。
②我们可以利用map自带升序、单对单映射的功能来实现上述的离散化。
对于每个在input里出现的点，我们都在把他放到map里，等input结束，我们用迭代器对map进行遍历，因为正好迭代器是从小到大遍历map，我们就可以借此把这些点映射到1~k；
最后，我们在update和query时记得把l、r、x都先进行映射，再传给update()、query()函数就行。
#include<cstdio>
#include<map>
#include<queue>
#define MAXM 100000+5
typedef long long ll;
using namespace std;
map<int,int> point;
struct Op{
int type,l,r,v,x;
};
queue<Op> op;
struct Node{
int l,r;
ll sum,lazy;
void update(ll x)
{
sum+=(r-l+)*x;
lazy+=x;
}
}node[*MAXM];
int n,m,size;
void pushdown(int root)
{
if(node[root].lazy)
{
node[root*].update(node[root].lazy);
node[root*+].update(node[root].lazy);
node[root].lazy=;
}
}
void pushup(int root)
{
node[root].sum=node[root*].sum+node[root*+].sum;
}
void build(int root,int l,int r)
{
node[root].l=l; node[root].r=r;
node[root].sum=; node[root].lazy=;
if(l==r) node[root].sum=;
else
{
int mid=l+(r-l)/;
build(root*,l,mid);
build(root*+,mid+,r);
pushup(root);
}
}
void update(int root,int st,int ed,int val)
{
if(st>node[root].r || ed<node[root].l) return;
if(st<=node[root].l && node[root].r<=ed) node[root].update(val);
else
{
pushdown(root);
update(root*,st,ed,val);
update(root*+,st,ed,val);
pushup(root);
}
}
ll query(int root,int st,int ed)
{
if(ed<node[root].l || node[root].r<st) return ;
if(st<=node[root].l && node[root].r<=ed) return node[root].sum;
else
{
ll ans=;
pushdown(root);
ans+=query(root*,st,ed);
ans+=query(root*+,st,ed);
pushup(root);
return ans;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
Op tmp;
scanf("%d",&tmp.type);
if(tmp.type)
{
scanf("%d",&tmp.x);
tmp.l=tmp.r=tmp.v=-;
if(!point.count(tmp.x)) point[tmp.x]=;
op.push(tmp);
}
else
{
scanf("%d%d%d",&tmp.l,&tmp.r,&tmp.v);
tmp.x=-;
if(!point.count(tmp.l)) point[tmp.l]=;
if(!point.count(tmp.r)) point[tmp.r]=;
op.push(tmp);
}
}
size=;
for(map<int,int>::iterator i=point.begin();i!=point.end();i++) (*i).second=(++size);
build(,,size);
while(!op.empty())
{
Op now=op.front();op.pop();
if(now.type)
{
printf("%lld\n",query(,point[now.x],point[now.x]));
}
else
{
update(,point[now.l],point[now.r],now.v);
}
}
}
note:再次强调要认真估计一下node[]数组要开的大小……跟UESTC1057一样，第一发都RE在test 8上，真是僵硬……