跳转至

202109-5 箱根山岳险天下

前言——建立树模型

题目要求对一个数组进行以下几个操作，强制在线：

  • 删除数组中最后一个元素；
  • 在数组末尾加入一个元素，注意删掉后又加入的元素与之前元素不能视为相同的元素；
  • 在第 \(s\) 次操作后的数组中，将 \([l,r]\) 位置的所有元素乘以 \(y\)，这个操作是永久性的；
  • 查询在第 \(s\) 次操作后的数组中 \([l,r]\) 位置所有元素目前值的和。
如果知道主席树？

对于历史操作，我们会想到主席树。但使用主席树时会遇到以下问题：

  1. 强制在线，且操作中存在添加删除元素。主席树不太方便实现。
  2. 主席树一般只针对最后的数组进行操作，每次操作只会影响到 \(\mathrm{O}(\log n)\) 元素，减小空间占用。但这里的区间乘不是针对最终状态，影响范围很大，空间占用会很多。

考虑用什么样的结构去存储信息。

维护每个操作后的数组

一种朴素的想法是维护每次操作后的数组。

这种做法存在时间问题：对于修改操作，它影响到的范围是 \(\mathrm{O}(m^2)\) 的，总体复杂度 \(\mathrm{O}(m^3)\)。

合并元素

思考浪费时间的地方：

设 \(t\) 时刻 \(x\) 位置的值为 \(A_{x,t}\)。假设目前时刻是 \(t_{cur}\)，如果在 \(s\) 时刻修改了 \(x\) 位置的值且直到 \(t_{cur}\) 时刻该元素一直没有被删除，那么影响到的范围是 \(A_{x,s}, A_{x,s+1},\cdots,A_{x, t_{cur}}\) 且操作都是相同的。而题目中所有的查询只针对目前而言，即只需要 \(A_{x, t_{cur}}\)。我们不需要维护中间状态的具体值，只需要知道中间状态的每个元素的位置（排名）。

由此，我们可以只存储每个元素目前时刻的状态，在进行修改时，只针对当前情况修改即可。

查找位置对应元素

由于每个元素只保留了最终状态，我们无法直接确定某时刻某位置的元素。假设要确定在 \(s\) 时刻位置在 \(x\) 的元素，因为一个元素的位置是不变的，我们不妨记录每个位置对应的元素编号与加入时间，那么在 \(s\) 时刻位置子 \(x\) 的元素对应位置在 \(x\) 数组内最后一个加入时间小于等于 \(s\) 的元素。

但是这样也存在问题：要找到一段区间上的所有元素的复杂度是 \(\mathrm{O}(m\log m)\) 的，总体复杂度 \(\mathrm{O}(m^2\log m)\)，不太能接受。

转变一下思路，因为增加和删除都是在末端进行，所以在某个元素被删除之前，它前面的元素都是不变的（类似于栈顶元素先变化、栈底元素后变化）。我们不妨将数组视为一条链，那么对应操作：

  • 增加一个元素：在链的末端加入元素。
  • 删除一个元素：断开最后一个元素与链的连边，由于需要操作不能实际断开，可以通过维护最后一个元素来实现。那么经过该操作后，新的最后一个元素变为原来的倒数第二个元素。

可以看出这是一棵树（准确来说是森林，但可以维护一个位置为 \(0\) 的元素指向所有位置为 \(1\) 的元素，这样就处理成了一棵树），那么要查找一段区间的所有元素，我们可以找到两端，在树上确定了两端也就确定了整条路径。查找两点时间复杂度 \(\mathrm{O}(\log m)\)，确定路径复杂度 \(\mathrm{O}(m)\)，整体 \(\mathrm{O}(m)\)。

最终模型

用一棵树来维护每个元素的强度，同时记录当前数组的末端元素位置；用数组维护某位置中所有元素的加入时刻与编号，不妨称其为排名数组。

  • 增加元素：在当前数组末端元素的节点处增加新的子节点，并将其设为末端元素，同时更新排名数组。
  • 删除元素：当前数组末端元素变更为其父亲节点。
  • 修改元素：找到对应元素位置，进行链上修改。
  • 查询元素：找到对应元素位置，进行链上查询。

测试点 1——搜索确定路径

在建立树模型后，我们暴力进行对应的操作：

  • 增加元素：复杂度 \(\mathrm{O}(1)\)；
  • 删除元素：复杂度 \(\mathrm{O}(1)\)；
  • 修改元素：确定路径并修改复杂度 \(\mathrm{O}(m)\)；
  • 查询元素：确定路径并查询复杂度 \(\mathrm{O}(m)\)；

整体复杂度 \(\mathrm{O}(m^2)\)。

测试点 2——线段树

由于只有增加没有删除，所以最终形态是一条链。我们维护线段树即可，初始值为 \(0\)。

  • 增加元素：线段树单点修改，复杂度 \(\mathrm{O}(\log m)\)；
  • 修改元素：线段树区间修改，复杂度 \(\mathrm{O}(\log m)\)；
  • 查询元素：点段数区间查询，复杂度 \(\mathrm{O}(\log m)\)；

整体复杂度 \(\mathrm{O}(m\log m)\)；

不要求在线——树链剖分

关于树上的区间修改操作一般都可以用树链剖分完成，但树链剖分需要预先知道树的形状，而本题中点都是动态的，无法一开始就得知。如果是离线的话，可以预处理出树的形态，进行剖分。

整体复杂度 \(\mathrm{O}(m\log m)\)；

因为有对树的动态加点，所以能看出这是一个动态树问题。解决动态树问题的结构之一就是 LCT。

本题算是 LCT 的板子题，整体复杂度 \(\mathrm{O}(m\log m)\)。

代码实现
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define il inline
const int maxn = 300010;

int m, T;
ll mod;

// LCT 部分开始
#define ls ch[x][0]
#define rs ch[x][1]
int ch[maxn][2], fa[maxn];
ll val[maxn], sum[maxn];
int lazy_rev[maxn];
ll lazy_mul[maxn];
#define getch(x) (ch[fa[x]][1] == x)
#define isRoot(x) (ch[fa[x]][0] != x && ch[fa[x]][1] != x)
void pushdownRev(int x) {
    // 执行翻转操作
    swap(ls, rs);
    lazy_rev[x] ^= 1;
}
void pushdownMul(int x, ll v) {
    // 执行区间乘操作
    val[x] = (val[x] * v) % mod;
    sum[x] = (sum[x] * v) % mod;
    lazy_mul[x] = (lazy_mul[x] * v) % mod;
}
void pushdown(int x) {
    // 下传懒惰标记
    if (lazy_rev[x]) {
        if (ls)
            pushdownRev(ls);
        if (rs)
            pushdownRev(rs);
        lazy_rev[x] ^= 1;
    }
    if (lazy_mul[x] != 1) {
        if (ls)
            pushdownMul(ls, lazy_mul[x]);
        if (rs)
            pushdownMul(rs, lazy_mul[x]);
        lazy_mul[x] = 1;
    }
}
void pushup(int x) {
    // 更新状态 (maintain)
    sum[x] = (sum[ls] + sum[rs] + val[x]) % mod;
}
int st[maxn];
void rotate(int x) {
    // splay 旋转操作
    int y = fa[x], z = fa[y], chk = getch(x), w = ch[x][chk ^ 1];
    if (!isRoot(y))
        ch[z][getch(y)] = x;
    ch[x][chk ^ 1] = y;
    ch[y][chk] = w;
    if (w)
        fa[w] = y;
    fa[y] = x, fa[x] = z;
    pushup(y);
}
void splay(int x) {
    // 将目前结点旋转到所在 splay 的根
    int top = 0, y = x;
    st[++top] = y;
    while (!isRoot(y)) {
        y = fa[y];
        st[++top] = y;
    }
    while (top)
        pushdown(st[top--]);
    while (!isRoot(x)) {
        y = fa[x];
        if (!isRoot(y))
            rotate(getch(x) == getch(y) ? y : x);
        rotate(x);
    }
    pushup(x);
}
void access(int x) {
    // 开辟一条只含有原树的根到 x 的路径结点的实链
    for (int y = 0; x; x = fa[y = x]) {
        splay(x);
        rs = y;
        pushup(x);
    }
}
void makeRoot(int x) {
    // 让 x 称为原树的根
    access(x);
    splay(x);
    pushdownRev(x);
}
void split(int x, int y) {
    // 开辟一条只含有 x 到 y 路径结点的实链，y 为 splay 的根
    makeRoot(x);
    access(y);
    splay(y);
}
void link(int x, int y) {
    // 连接两个部分
    makeRoot(x);
    fa[x] = y;
}
// LCT 部分结束

struct Player {
    /*
        队员类。
        day: 成为正式队员的时刻
        fa : 前一名队员对应编号
    */
    int day, fa;
    Player(int _d = 0, int _f = 0) { day = _d, fa = _f; }
} player[maxn];
vector<int> ranklist[maxn]; // 存储队员编号
int cur, cur_rank, tot;
void insertPlayer(int day, ll v) {
    // 加入新队员
    ++tot;
    // 对原树进行操作
    player[tot] = Player(day, cur);
    ++cur_rank;
    ranklist[cur_rank].push_back(tot);
    // 对辅助树进行操作
    val[tot] = sum[tot] = v;
    lazy_mul[tot] = 1;
    lazy_rev[tot] = 0;
    // 如果目前队伍有人，则加入队伍
    if (cur)
        link(tot, cur);
    cur = tot;
}
int findPlayer(int day, int rk) {
    // 查找在第 day 天排名 rk 的队员编号
    int l = 0, r = ranklist[rk].size() - 1, mid, ans = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (player[ranklist[rk][mid]].day <= day) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ranklist[rk][ans];
}

int main() {
    scanf("%d%lld%d", &m, &mod, &T);
    int opt, s, l, r, x, y, A = 0;
    for (int day = 1; day <= m; ++day) {
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d", &x);
            if (T == 1)
                x ^= A;
            if (x == 0) {
                // 删除队员
                cur = player[cur].fa;
                --cur_rank;
            } else {
                // 加入新队员
                insertPlayer(day, x);
            }
        } else if (opt == 2) {
            scanf("%d%d%d%d", &s, &l, &r, &y);
            if (T == 1)
                y ^= A;
            l = findPlayer(s, l);
            r = findPlayer(s, r);
            // 找到 l 到 r 的实链，标记乘以 y
            split(l, r);
            pushdownMul(r, y);
        } else {
            scanf("%d%d%d", &s, &l, &r);
            l = findPlayer(s, l);
            r = findPlayer(s, r);
            // 找到 l 到 r 的实链，求和即可
            split(l, r);
            A = sum[r];
            printf("%d\n", A);
        }
    }
    return 0;
}

评论