Weed
【题目描述】
duyege 的电脑上面已经长草了，经过辨认上面有金坷垃的痕迹。
为了查出真相，duyege 准备修好电脑之后再进行一次金坷垃的模拟实验。
电脑上面有若干层金坷垃，每次只能在上面撒上一层高度为 vi 的金坷垃，或者除掉最新 vi 层（不是量）撒的金坷垃(即撤回之前vi次撒的操作)。如果上面只留有不足 vi 层金坷垃，那么就相当于电脑上面没有金坷垃了。
duyege 非常严谨，一开始先给你 m 个上述操作要你依次完成。然后又对实验步骤进行了 q 次更改，每次更改都会改变其中一个操作为另外一个操作。每次修改之后都会询问最终金坷垃的量有多少，操作是叠加的。
【输入】
输入第一行为两个正整数 m、q，接下来 m 行每行 2 个整数 k、vi。k 为 0 时撒金坷垃，为 1 时除金坷垃。接下来 q 行每行 3 个整数 ci、k、vi，ci 代表被更改的操作是第 ci 个，后面 2 个数描述更改为这样的操作。
【输出】
输出 q 行代表每次金坷垃的量为多少。
【输入样例】
3 3 0 10 1 1 0 11 1 1 10 2 0 20 3 1 1
【输出样例】
11 31 0
【提示】
对于 30%的数据，m≤1000,q≤1000. 对于另外 20%的数据，每次 k=1 时都会将金坷垃清空。
对于 100%的数据，m≤2*10^5,q≤2*10^5,vi≤10^4。
【来源】
这是一道2016 noip的模拟题，前天被用来考楼下的同学，van dark爷 又说要我们做一做这3道模拟题，所以就来看看了，第一题还好，写个贪心一遍过，但是到了这道题，我就傻眼了，大脑直接掉线，除了暴力还能干蛤？？！！
就在我无尽懵逼的时候，前排的那位大佬（当时楼下唯一做起了这道题的人）满脸轻松地对我说“这不是线段树的板子题吗”，当场傻了，这是线段树的板子？？？我是不是学了假的OI，我当然想过用线段树，但怎么维护嘛！维护每个操作，然后操作之间进行合并。对啊！！！我们可以维护操作，于是马上开始码代码。
码到一半，发现好像没有维护够东西，总感觉自己的合并有BUG，但又说不出为什么，这时前排大佬有满脸轻松地说了一句，维护一个对前面删除的变量，我当时没太搞明白，又不想，看别人博客，所以就没理前排大佬，继续按我的思路来，结果果然GG，调了一下午都没调出来。
回了家之后，越想越觉得自己的思路有问题，发现我还是需要记录一个删除变量，所以只有从头开始。最终，调了半个晚上，哇！！！我真的写出来了，内心一阵狂感动。。。
所以，停了好久没写博客的我，决定还是花点时间，记录下这道煞费苦心的题（太菜了）。
【思路分析】
这道题是线段树模板？？？虽然很感谢那位前排大佬，但是想到那张漫不经心的脸，和那句“这不是线段树的板子题吗””，内心就是一阵MMP，一度觉得自己是不是不适合学OI了，难道是我真的太菜了，不存在的吧。反而觉得，这道题是一道很不错的线段树（模板？？？）。
首先对于线段树的每个节点，我们维护的是这个区间的操作带来的影响，分别维护ci——>金克拉层数，vi——>金克拉的量，cut——>当前区间会对前面的区间造成多少的删除操作的影响。最后的根节点就是整个一系列操作带来的最终影响，这样修改起来十分迅捷，是logn的。
这道题最关键的就是update，即区间合并，我们需要好好考虑一下如何合并区间
因为对于每个节点右儿子都是后进行的操作，所以我们就需要优先考虑右儿子，再谈左儿子的事。
1 int ask(int v,int GG)
2 {
3 int ls=t[v].son[0],rs=t[v].son[1];
4 if(t[rs].ci==GG)//优先查找右儿子，如果右儿子刚好，那么但前区间的左儿子会全部都没被删
5 return t[v].vi-t[rs].vi;
6 if(GG<t[rs].ci)
7 return t[v].vi-t[rs].vi+ask(rs,GG);//如果右儿子剩多了，那么就到右儿子里面去查
8 else
9 return ask(ls,GG-t[rs].ci+t[rs].cut);//如果右儿子不够就到左儿子里去，但我们就只需要查左儿子还差多少
10 }
11 void update(int v)
12 {
13 int ls=t[v].son[0],rs=t[v].son[1];
14 if(t[rs].cut>=t[ls].ci)//右儿子把左儿子删完了
15 {
16 t[v].cut=t[rs].cut+t[ls].cut-t[ls].ci;//那么当前区间的删除会有剩余
17 t[v].ci=t[rs].ci;
18 t[v].vi=t[rs].vi;//因为左儿子被删完了
19 }
20 else
21 if(t[rs].cut==0)//右儿子无删除操作
22 {
23 t[v].cut=t[ls].cut;
24 t[v].ci=t[ls].ci+t[rs].ci;
25 t[v].vi=t[ls].vi+t[rs].vi;//右儿子不会影响当前区间
26 }
27 else//右儿子把左儿子删不完
28 {
29 t[v].cut=t[ls].cut;//右儿子的删除用没了
30 t[v].ci=t[rs].ci+t[ls].ci-t[rs].cut;//当前区间的层数会有剩余
31 t[v].vi=t[rs].vi+ask(ls,t[rs].cut);//查询我们删除后左儿子剩下的金克拉量
32 }
33 }
在代码实现环节之前，我还是要好好强调一下这道题的价值，至少对我来说，它让我明白了线段树能维护的东西很多，要敢于去想，去思考。不要拿着一颗线段树，整天就只知道区间最大值，区间和，区间乘（当然区间乘还是很扯淡的），也锻炼了我们线段树update的能力，挺有价值，你值得拥有！！！
【代码实现】
1 #include<cstdio>
2 #include<vector>
3 #include<queue>
4 #include<cstring>
5 using namespace std;
6 const int maxn=2e5+5;
7 int root,cnt;
8 struct sd{
9 int ci,vi,cut,son[2],l,r;
10 }t[maxn*2];
11 int cc[maxn],vv[maxn];
12 int ask(int v,int GG)
13 {
14 int ls=t[v].son[0],rs=t[v].son[1];
15 if(t[rs].ci==GG)
16 return t[v].vi-t[rs].vi;
17 if(GG<t[rs].ci)
18 return t[v].vi-t[rs].vi+ask(rs,GG);
19 else
20 return ask(ls,GG-t[rs].ci+t[rs].cut);
21 }
22 void update(int v)
23 {
24 int ls=t[v].son[0],rs=t[v].son[1];
25 if(t[rs].cut>=t[ls].ci)
26 {
27 t[v].cut=t[rs].cut+t[ls].cut-t[ls].ci;
28 t[v].ci=t[rs].ci;
29 t[v].vi=t[rs].vi;
30 }
31 else
32 if(t[rs].cut==0)
33 {
34 t[v].cut=t[ls].cut;
35 t[v].ci=t[ls].ci+t[rs].ci;
36 t[v].vi=t[ls].vi+t[rs].vi;
37 }
38 else
39 {
40 t[v].cut=t[ls].cut;
41 t[v].ci=t[rs].ci+t[ls].ci-t[rs].cut;
42 t[v].vi=t[rs].vi+ask(ls,t[rs].cut);
43 }
44 }
45 void build(int &v,int l,int r)
46 {
47 cnt++,v=cnt,t[v].l=l,t[v].r=r;
48 if(l==r)
49 {
50 if(cc[l]==0) t[v].ci=1,t[v].vi=vv[l],t[v].cut=0;
51 else t[v].vi=0,t[v].ci=0,t[v].cut=vv[l];
52 return;
53 }
54 int mid=(l+r)/2;
55 build(t[v].son[0],l,mid);
56 build(t[v].son[1],mid+1,r);
57 update(v);
58 }
59 void change(int v,int pos,int c1,int v1)
60 {
61 if(t[v].l==t[v].r&&t[v].l==pos)
62 {
63 if(c1==0) t[v].ci=1,t[v].vi=v1,t[v].cut=0;
64 else t[v].vi=0,t[v].ci=0,t[v].cut=v1;
65 return;
66 }
67 int mid=(t[v].r+t[v].l)/2;
68 if(pos<=mid) change(t[v].son[0],pos,c1,v1);
69 else change(t[v].son[1],pos,c1,v1);
70 update(v);
71 }
72 int main()
73 {
74 int n,q,num=0;
75 scanf("%d%d",&n,&q);
76 for(int i=1;i<=n;i++)
77 scanf("%d%d",&cc[i],&vv[i]);
78 build(root,1,n);
79 for(int i=1;i<=q;i++)
80 {
81 int k,c1,v1;
82 scanf("%d%d%d",&k,&c1,&v1);
83 change(root,k,c1,v1);
84 printf("%d\n",t[root].vi);
85 }
86 return 0;
87 }