hihocoder-1080题解

一、题目链接

　　http://hihocoder.com/problemset/problem/1080

二、题意

　　一维区间，需要做区间增加和区间置值，以及对整个区间求和。

三、思路

　　显然线段树是个利器。树状数组也可以支持快速区间增加和区间求和，而且编码也比线段树要短要简单（其实线段树也不难，越用越有味），但是对于区间置值，那就没辙了。

　　中途插入一点心情小插曲：这题确实让我对带延迟标记的线段树理解了不少，历经各种bug的磨难终于AC后，对带延迟标记的线段树的理解确实更上一层楼了。写这个题的时候，先按照自己的理解写了一个版本，过了样例，交上去WA了，之后一直没明白为什么WA。现在终于明白了，感觉还是蛮爽的。第二个版本是昨晚参考题面上给的思路提示写的，当时也没想太多，写好后，过了样例又交了一发，还是WA，然后带着不明白睡了。今天起来后，继续调这个题目。搞了一个上午后，终于找出问题来了（虽然还是没有AC）。接下来进入正题。

　　先说基本思路，再说本题最坑的地方。

　　基本思路：线段树的每一个节点维护所表示区间的和值，这毫无疑问。 另外，由于这题需要支持区间增加和区间置值两种操作，所以，线段树每个节点需要两个延迟标记，add和set，两者都是int类型的，分别表示当前节点所表示的区间增加的值和设置的值（至于从什么时候开始累计增加的值，这个先不管，继续往下看）。如果没想到要定义两个延迟标记，参考题目的思路提示后也可知道需要这么干。否则，只记录区间和值搞不定啊。是吧。然后，update函数的形参中多写一个bool型参数，表示当前做的更新是增加还是置值。当当前处理的区间包含于要更新的区间时，根据刚刚那个bool型参数来决定是增加还是重新设置当前处理区间的和值。当当前处理的区间不完全包含于要更新的区间时，这时就需要对当前区间做延迟标记下推的工作。然后递归地对两个子节点区间做处理，再合并两个子节点的和值，作为当前节点维护的和值。这应该不难，都是正常带延迟标记的线段树的套路。接下来，关键问题来了。也是本题最有意思的地方来了。

　　坑（最有趣的地方）：下推函数怎么写？这个可以参考题目的思路提示写出来，但是，写出来之后样例是过了，交上去不对啊，下推函数左看右看上看下看都和提示一样，怎么就WA了呢？原因在于，提示中的下推函数没写全，它只给了我们一些思路提示，让我们知道要往那个方向去想，并没有完全把全过程写出来。接下来详细说说提示中下推函数的坑点。举个有错的样例：　

   -

　　对于这个样例，第三次输出应该是1，但是完全按照提示中的下推函数来写，会输出-7。这明显就不对。原因在于，第一次把区间[1, 8]增加-4之后，区间[5, 6]也理所当然地增加了-4。第二次把区间[5, 6]设置为10，结果输出是-4也没错。第三次，输出结果就不对了。因为，第二次对区间[5, 6]置值之后，之前对[5, 6]的增加（也就是区间[5, 6]对应的节点的add值）值就没用了，应该设置为0，但是，思路提示中只是把它的子节点的add值设置成0而已。既然这样，那很简单，直接在下推函数中set下推的过程里面，把当前节点的add值设置为0就OK了。但是，如果这么干，又会带来这样的问题，还是举个反例：

　　第四次输出的正确结果应该是94，但打了补丁后的程序输出却是91。插入一句题外话：线段树节点下标从1开始，1号节点对应的区间是[0, 9]，2号节点对应的区间是[0, 4]。我们的补丁打的有问题，原因在于：第二次的更新中，2号节点（对应区间[0, 4]）的set值被设为12。第三次更新中，2号节点（对应区间[0, 4]）的add值被设为1，所以，2号节点的add != 0且set != -1。那么，在下推的过程中，先做置值，再做增加，在置值的过程中，由于我们加入“把当前节点的add值设为0”这么一行代码，导致下面的判增加的if代码块进不去，所以，当前节点的子节点没有获得区间置值后增加的值，导致结果不对。既然这样，那也好办，那就先做增加，再做置值。但是这样就更不对了，如果对于一个区间，第一次做了增加，还没下推。第二次又对这个区间置值。第三次对这个区间的子区间做更新，那么，下推这个区间的延迟标记时，因为是先做增加，再做置值，那么，第一次的add值就会下推给当前区间的子区间，导致结果偏大。

　　加也不对，不加也不对，那不就没办法了么？确实，我当时也这么觉得。仔细分析第一种错误，你会发现，本来不该下推的add值被下推的主要原因是，当前区间被置值后，当前区间所对应的节点的add值没来得及置0。对于第二种错误，那是因为当前区间所对应的节点的add值置0置的太晚了，其实应该在区间被置值后立马就做的。既然这样，那我就把下推函数中判set的if代码块搬到update函数的区间置值完毕之后。这样，每次区间置值完毕，立马更新当前区间对应节点的add值为0，那么前两个问题不就愉快地解决了么？是的。就这样。然而，嘴上一分钟，嘴下十年功啊，我调了变天多才调出这么个法子来T_T。于是，最终AC的结果就如下所示了。

四、源代码

　　

#include<bits/stdc++.h>
using namespace std;
;
int n, m;
typedef struct {
    int add, set, sum;
} Node;
Node data[MAXN << ];

void init() {
    , t = MAXN << ; i < t; ++i) {
        data[i].add = ;
        data[i].sum = ;
        data[i].;
    }
}

void release_set(int root, int l, int r){
    ){//不是叶子节点
        , rch = root <<  | ;
        ;
        ) {
            data[lch].set = data[rch].set = data[root].set;
            data[lch].add = data[rch].add = ;
            data[lch].sum = data[root].);
            data[rch].sum = data[root].set * (r - mid);
            data[root].;
        }
    }
}

void release_add(int root, int l, int r) {
    ) {//不是叶子节点
        , rch = root <<  | ;
        ;
        ) {
            data[lch].add += data[root].add;
            data[rch].add += data[root].add;
            data[lch].sum += data[root].add * (mid - l + );
            data[rch].sum += data[root].add * (r - mid);
            data[root].add = ;
        }
    }
}

, , int r = n) {
    if(l > r)return;
    if(l > ur || r < ul)return;
    if(l >= ul && r <= ur) {
        if(isadd) {
            data[root].add += val;
            data[root].sum += val * (r - l + );
        } else {
            data[root].set = val;
            data[root].sum = val * (r - l + );
            release_set(root, l, r);
            data[root].add = ;//特别注意这句话
        }
        return;
    }
    release_set(root, l, r);//顺序不能乱。
    release_add(root, l, r);
    ;
    , l, mid);
     | , mid + , r);
    data[root].sum = data[root << ].sum + data[root <<  | ].sum;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input5.txt", "r", stdin);
    //freopen("output2.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int a, b, c, d;
    while(~scanf("%d%d", &n, &m)) {
        init();
        ; i <= n; ++i) {
            scanf("%d", &a);
            update(i, i, false, a);
        }
        ; i < m; ++i) {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            update(b, c, a == , d);
            printf(].sum);
            //for(int i = 1; i <= 19; ++i)printf("[%d](%d %d %d) ", i, data[i].add, data[i].set, data[i].sum); printf("\n\n");
            /*这是打出每个节点的信息，调试用的。*/
        }
    }
    ;
}

注：这是最终代码，中途经历很多个版本，很多种尝试，但那都不是关键，关键的地方也是本题最有意思的地方就在这里了。Last but not least，思路讲解有些地方可能讲的不够清楚明白，又或许有些地方语句不通顺或者有错别字，如果您还不明白，请在评论区留言，我们一起讨论。你懂得，博客这种东西，历经各种bug终于AC后感觉有很多话要说，一旦写起来，就不知道说些什么了。表达能力还有很大的提升空间。