[题解] ZJOI2019 线段树

Table of Contents

题目描述

九条可怜是一个喜欢数据结构的女孩子，在常见的数据结构中，可怜最喜欢的就是线段树。

线段树的核心是懒标记，下面是一个带懒标记的线段树的伪代码，其中 $t a g$ 数组为懒标记：

其中函数 $L s o n (N o d e)$ 表示 $N o d e$ 的左儿子， $R s o n (N o d e)$ 表示 $N o d e$ 的右儿子。

现在可怜手上有一棵 $[1, n]$ 上的线段树，编号为 $1$ 。这棵线段树上的所有节点的 $t a g$ 均为 $0$ 。接下来可怜进行了 $m$ 次操作，操作有两种：

$1 l r$ ，假设可怜当前手上有 $t$ 棵线段树，可怜会把每棵线段树复制两份（ $t a g$ 数组也一起复制），原先编号为 $i$ 的线段树复制得到的两棵编号为 $2 i - 1$ 与 $2 i$ ，在复制结束后，可怜手上一共有 $2 t$ 棵线段树。接着，可怜会对所有编号为奇数的线段树进行一次 $M o d i f y (r o o t, 1, n, l, r)$ 。
$2$ ，可怜定义一棵线段树的权值为它上面有多少个节点 $t a g$ 为 $1$ 。可怜想要知道她手上所有线段树的权值和是多少。

输入格式

第一行输入两个整数 $n, m$ 表示初始区间长度和操作个数。

接下来 $m$ 行每行描述一个操作，输入保证 $1 \leq l \leq r \leq n$ 。

输出格式

对于每次询问，输出一行一个整数表示答案，答案可能很大，对 $998244353$ 取模后输出即可。

样例输入

样例输出

0
1
6

解题思路

一道可写的简单线段树题

经过 $k$ 次 $1$ 操作后，将有 $2^{k}$ 棵线段树

将线段树合起来看，将线段树中一个节点编号为 $i$ 的 $t a g$ 为 $1$ 的概率记为 $f_{i}$ ，那么答案就为 $\sum_{i} f_{i} \times 2^{k}$

考虑 $u p d a t e$ 操作对答案的影响，我们先回顾这道题 $u p d a t e$ 的写法

void update(int root, int left, int right, int qleft, int qright){
    int lson = root << 1, rson = root << 1 | 1, mid = (left + right) >> 1;
    if(qleft <= left && right <= qright){
        tag[root] = 1;
        return;
    }

    pushdown(root, left, right);

    if(qleft <= mid)
        update(lson, left, mid, qleft, qright);
    if(mid < qright)
        update(rson, mid + 1, right, qleft, qright);
}

因为有 $p u s h d o w n$ 操作，我们考虑用 $g_{i}$ 表示节点编号为 $i$ 和父亲节点 $f a_{i}$ 中至少有一个 $t a g$ 为 $1$ 的概率

情况一：假如这个区间被完全覆盖

因为每一次修改只修改一半的线段树，没有被修改的对答案的贡献是 $\frac{f_{i}}{2}$ 和 $\frac{g_{i}}{2}$ ，被修改的对答案的贡献是 $\frac{1}{2}$ 和 $\frac{1}{2}$
$f_{i} \leftarrow \frac{f_{i} + 1}{2} g_{i} \leftarrow \frac{g_{i} + 1}{2}$
情况二：假如进行了 $p u s h d o w n$ 操作

被修改的线段树中，进行了 $p u s h d o w n$ 的线段树区间 $t a g$ 一定是 $0$ ，并且从根到这个区间路径上所有节点的 $t a g$ 都应该是 $0$

所以这一半线段树对答案的贡献是 $0$ 和 $0$
$f_{i} \leftarrow \frac{f_{i}}{2} g_{i} \leftarrow \frac{g_{i}}{2}$
情况三：假如进行了 $p u s h d o w n$ ，但子区间不符合递归 $u p d a t e$ 的条件

那么显然只对左儿子区间或右儿子区间的 $f$ 造成了影响，对答案的贡献是 $\frac{f_{s o n} + g_{s o n}}{2}$
$f_{s o n} \leftarrow \frac{f_{s o n} + g_{s o n}}{2}$
而 $g_{s o n}$ 是不变的

情况四：由于 $p u s h d o w n$ 或赋值操作，父区间 $t a g$ 被赋值为 $1$

这对区间的 $f_{i}$ 本身是没有影响的，影响只是 $g_{i}$ ，这一部分对答案的贡献是 $\frac{g_{i} + 1}{2}$
$g_{i} \leftarrow \frac{g_{i} + 1}{2}$
但是这种情况出现次数可能会很多，比如出现一次情况一，就会对其所有子树有影响

但我们发现每个子区间的权值都是乘上 $\frac{1}{2}$ 后加上 $\frac{1}{2}$

因此可以线段树维护 $m u l$ 标记和 $a d d$ 标记解决

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>

using namespace std;

const int MAXN = 100000 + 10;
const int MOD = 998244353;
const int INV = 499122177;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int n, m;
long long siz = 1;

namespace SEG{
    long long sum[MAXN << 3], f[MAXN << 3], g[MAXN << 3], add[MAXN << 3], mul[MAXN << 3];

    inline void init(){
        fill(mul, mul + (n << 2) + 1, 1);
    }

    inline void pushup(int root){
        int lson = root << 1, rson = root << 1 | 1;
        sum[root] = (sum[lson] + sum[rson] + f[root]) % MOD;
    }

    inline void pushdown(int root, int left, int right){
        int lson = root << 1, rson = root << 1 | 1;

        if(mul[root] != 1 || add[root] != 0){
            mul[lson] = (mul[root] * mul[lson]) % MOD;
            mul[rson] = (mul[root] * mul[rson]) % MOD;

            add[lson] = (mul[root] * add[lson] + add[root]) % MOD;
            add[rson] = (mul[root] * add[rson] + add[root]) % MOD;

            g[lson] = (mul[root] * g[lson] + add[root]) % MOD;
            g[rson] = (mul[root] * g[rson] + add[root]) % MOD;

            mul[root] = 1;
            add[root] = 0;
        }
    }

    inline void update(int root, int left, int right, int qleft, int qright){
        int lson = root << 1, rson = root << 1 | 1, mid = (left + right) >> 1;

        if(qleft <= left && right <= qright){
            f[root] = (f[root] * INV + INV) % MOD;
            g[root] = (g[root] * INV + INV) % MOD;

            mul[root] = (mul[root] * INV) % MOD;
            add[root] = (add[root] * INV + INV) % MOD;

            pushup(root);
            return;
        }

        pushdown(root, left, right);

        f[root] = (f[root] * INV) % MOD;
        g[root] = (g[root] * INV) % MOD;

        if(qleft <= mid){
            update(lson, left, mid, qleft, qright);
        }else{
            f[lson] = (f[lson] * INV + g[lson] * INV) % MOD;
            pushup(lson);
        }

        if(mid < qright){
            update(rson, mid + 1, right, qleft, qright);
        }else{
            f[rson] = (f[rson] * INV + g[rson] * INV) % MOD;
            pushup(rson);
        }

        pushup(root);
    }

}

int main(){
    freopen("segment.in", "r", stdin);
    freopen("segment.out", "w", stdout);

    n = read();
    m = read();

    for(register int i=1; i<=m; i++){
        int op = read();

        if(op == 2){
            printf("%lld\n", SEG::sum[1] * siz % MOD);
        }else{
            int l = read();
            int r = read();

            SEG::update(1, 1, n, l, r);

            siz = (siz << 1) % MOD;
        }
    }    
    return 0;
}

BLOG