题目链接：LOJ 3043

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

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

其中函数 $\text{Lson}(\text{Node})$ 表示 $\text{Node}$ 的左儿子，$\text{Rson}(\text{Node})$ 表示 $\text{Node}$ 的右儿子。

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

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

数据范围：$1 \le n, m \le 10 ^ 5$。

Solution

显然不能每次复制一份线段树，而是要将所有节点分成若干类，分别维护信息。

对于一次 $\text{Modify}(\text{root}, 1, n, l, r)$，我们将节点分为 $5$ 类。这里使用一张 Sooke 神仙的图。

这些节点分为如下 $5$ 类：

1. 白点：在修改过程中经过，并且标记被下传的节点。
2. 黑点：修改的目标节点，被直接打上标记。
3. 灰点：在修改区域内，但是不会经过的节点。
4. 橙点：在 $\text{Pushdown}$ 操作中可能获得父节点标记的节点。
5. 黄点：完全无关的节点。

我们用 $f(i)$ 表示点 $i$ 有 tag 的情况数量。设当前是第 $k$ 次修改操作，我们对这 $5$ 类点分别转移：

1. 白点：$f(i) \leftarrow f(i)$

   新建的一份线段树中标记被全部清空。

2. 黑点：$f(i)\leftarrow f(i) + 2 ^ {k - 1}$

   新建的一份线段树中这些节点全部有标记。

3. 灰点：$f(i) \leftarrow 2f(i)$

   新建的一份线段树中节点标记不会变化。

4. 橙点：$f(i) \leftarrow f(i) + g(i)$

   其中 $g(i)$ 表示节点 $i$ 到 $\text{root}$ 这条路径上有标记的情况数。

5. 黄点：$f(i) \leftarrow 2f(i)$

   新建的一份线段树中节点标记不会变化。

发现我们又多了一个 $g(i)$ 需要维护。定义 $g(i)$ 表示节点 $i$ 到 $\text{root}$ 这条路径上有标记的情况数。我们考虑转移：

$$ g(i) = \begin{cases} g(i) & \text{白点}\\ g(i) + 2 ^ {k - 1} & \text{黑点}\\ g(i) + 2 ^ {k - 1} & \text{灰点}\\ 2g(i) & \text{橙点}\\ 2g(i) & \text{黄点}\\ \end{cases} $$

我们直接用线段树维护 $f(i), g(i)$ 和子树 $f(i)$ 的和，支持加法、乘法操作。

时间复杂度：$\mathcal O(m\log n)$

Code

#include <cstdio>
#define lson p << 1
#define rson p << 1 | 1

const int N = 8e5 + 5;
const int P = 998244353;

int n, m, s, f[N], g[N], fMul[N], gAdd[N], gMul[N], sum[N];

void build(int p, int l, int r) {
    fMul[p] = gMul[p] = 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
}
void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void mul(int &x, int y) {
    x = 1LL * x * y % P;
}
void mulTagF(int p, int v) {
    mul(f[p], v), mul(fMul[p], v), mul(sum[p], v);
}
void addTagG(int p, int v) {
    add(g[p], v), add(gAdd[p], v);
}
void mulTagG(int p, int v) {
    mul(g[p], v), mul(gAdd[p], v), mul(gMul[p], v);
}
void pushup(int p) {
    sum[p] = f[p], add(sum[p], sum[lson]), add(sum[p], sum[rson]);
}
void pushdown(int p) {
    if (fMul[p] > 1) {
        mulTagF(lson, fMul[p]), mulTagF(rson, fMul[p]), fMul[p] = 1;
    }
    if (gMul[p] > 1) {
        mulTagG(lson, gMul[p]), mulTagG(rson, gMul[p]), gMul[p] = 1;
    }
    if (gAdd[p] > 0) {
        addTagG(lson, gAdd[p]), addTagG(rson, gAdd[p]), gAdd[p] = 0;
    }
}
void update(int p, int opt) {
    if (opt == 1) {
        add(f[p], s), mulTagF(lson, 2), mulTagF(rson, 2);
        add(g[p], s), addTagG(lson, s), addTagG(rson, s);
    } else {
        add(f[p], g[p]), mulTagF(lson, 2), mulTagF(rson, 2);
        add(g[p], g[p]), mulTagG(lson, 2), mulTagG(rson, 2);
    }
    pushup(p);
}
void modify(int p, int l, int r, int x, int y, int opt) {
    pushdown(p);
    if (x <= l && r <= y) {
        update(p, opt);
        return;
    }
    int mid = (l + r) >> 1;
    if (y <= mid) {
        modify(lson, l, mid, x, y, opt);
    } else if (x > mid) {
        modify(rson, mid + 1, r, x, y, opt);
    } else {
        modify(lson, l, mid, x, mid, opt);
        modify(rson, mid + 1, r, mid + 1, y, opt);
    }
    pushup(p);
}
int main() {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    s = 1;
    for (int i = 1; i <= m; i++) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int l, r;
            scanf("%d%d", &l, &r);
            modify(1, 1, n, l, r, 1);
            if (l > 1) modify(1, 1, n, 1, l - 1, 2);
            if (r < n) modify(1, 1, n, r + 1, n, 2);
            mul(s, 2);
        } else {
            printf("%d\n", sum[1]);
        }
    }
    return 0;
}