UESTC 1059

题目链接：http://acm.uestc.edu.cn/#/problem/show/1059

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

秋实大哥以周济天下，锄强扶弱为己任，他常对天长叹：安得广厦千万间，大庇天下寒士俱欢颜。

所以今天他又在给一群小朋友发糖吃。

他让所有的小朋友排成一行，从左到右标号。在接下去的时间中，他有时会给一段区间的小朋友每人

这对于没上过学的孩子来说实在太困难了，所以你看不下去了，请你帮助小朋友回答所有的询问。

Input

第一行包含两个整数

接下来的

0 l r v : 表示秋实大哥给[l,r]这个区间内的小朋友每人v颗糖

1 x : 表示秋实大哥想知道第x个小朋友手里现在有几颗糖

Output

对于每一个

Sample input and output

Sample Input	Sample Output
3 4 0 1 3 1 1 2 0 2 3 3 1 3	1 4

用了跟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()函数就行。

  1 #include<cstdio>
  2 #include<map>
  3 #include<queue>
  4 #define MAXM 100000+5
  5 typedef long long ll;
  6 using namespace std;
  7 map<int,int> point;
  8 struct Op{
  9     int type,l,r,v,x;
 10 };
 11 queue<Op> op;
 12 struct Node{
 13     int l,r;
 14     ll sum,lazy;
 15     void update(ll x)
 16     {
 17         sum+=(r-l+1)*x;
 18         lazy+=x;
 19     }
 20 }node[8*MAXM];
 21 int n,m,size;
 22 void pushdown(int root)
 23 {
 24     if(node[root].lazy)
 25     {
 26         node[root*2].update(node[root].lazy);
 27         node[root*2+1].update(node[root].lazy);
 28         node[root].lazy=0;
 29     }
 30 }
 31 void pushup(int root)
 32 {
 33     node[root].sum=node[root*2].sum+node[root*2+1].sum;
 34 }
 35 void build(int root,int l,int r)
 36 {
 37     node[root].l=l; node[root].r=r;
 38     node[root].sum=0; node[root].lazy=0;
 39     if(l==r) node[root].sum=0;
 40     else
 41     {
 42         int mid=l+(r-l)/2;
 43         build(root*2,l,mid);
 44         build(root*2+1,mid+1,r);
 45         pushup(root);
 46     }
 47 }
 48 void update(int root,int st,int ed,int val)
 49 {
 50     if(st>node[root].r || ed<node[root].l) return;
 51     if(st<=node[root].l && node[root].r<=ed) node[root].update(val);
 52     else
 53     {
 54         pushdown(root);
 55         update(root*2,st,ed,val);
 56         update(root*2+1,st,ed,val);
 57         pushup(root);
 58     }
 59 }
 60 ll query(int root,int st,int ed)
 61 {
 62     if(ed<node[root].l || node[root].r<st) return 0;
 63     if(st<=node[root].l && node[root].r<=ed) return node[root].sum;
 64     else
 65     {
 66         ll ans=0;
 67         pushdown(root);
 68         ans+=query(root*2,st,ed);
 69         ans+=query(root*2+1,st,ed);
 70         pushup(root);
 71         return ans;
 72     }
 73 }
 74 int main()
 75 {
 76     scanf("%d%d",&n,&m);
 77     for(int i=1;i<=m;i++)
 78     {
 79         Op tmp;
 80         scanf("%d",&tmp.type);
 81         if(tmp.type)
 82         {
 83             scanf("%d",&tmp.x);
 84             tmp.l=tmp.r=tmp.v=-1;
 85             if(!point.count(tmp.x)) point[tmp.x]=0;
 86             op.push(tmp);
 87         }
 88         else
 89         {
 90             scanf("%d%d%d",&tmp.l,&tmp.r,&tmp.v);
 91             tmp.x=-1;
 92             if(!point.count(tmp.l)) point[tmp.l]=0;
 93             if(!point.count(tmp.r)) point[tmp.r]=0;
 94             op.push(tmp);
 95         }
 96     }
 97     size=0;
 98     for(map<int,int>::iterator i=point.begin();i!=point.end();i++) (*i).second=(++size); 
 99     build(1,1,size);
100     while(!op.empty())
101     {
102         Op now=op.front();op.pop();
103         if(now.type)
104         {
105             printf("%lld
",query(1,point[now.x],point[now.x]));
106         }
107         else
108         {
109             update(1,point[now.l],point[now.r],now.v);
110         }
111     }
112 }

note:再次强调要认真估计一下node[]数组要开的大小……跟UESTC1057一样，第一发都RE在test 8上，真是僵硬……