题解报告——Weed

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 行代表每次金坷垃的量为多少。

【输入样例】

【输出样例】

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
",t[root].vi);
85     }
86     return 0;
87 }