mydcwfy's Blog

Luogu P8861 线段

Posted on
Symbols count in article: 9.5k Reading time ≈ 21 mins.

题意：给定一些区间的集合，最开始为空。给出 $q$ 次操作，会给出 $op, l, r$：

  1. $op = 1$：向集合插入一个新的元素 $[l, r]$。
  2. $op = 2$：对于集合的每一个元素，如果其与 $[l, r]$ 有交，就改为其与 $[l, r]$ 的交。
  3. $op = 3$：查询集合中每一个元素与 $[l, r]$ 交的长度的和。

$[l, r]$ 的长度定义为 $r - l$。部分测试点强制在线。假设 $op = 1, 2, 3$ 的操作次数分别为 $k_1, k_2, k_3$，则有 $k_1, k_2\leq 10 ^ 5, k_3\leq 3\times 10 ^ 5$，$1\leq l\leq r\leq 2\times 10 ^ 5$。

记权值范围为 $m = 2\times 10 ^ 5$。

Tests 13 - 17

首先注意到中间的一些测试点（$13\sim 17$）是 $1\leq l\leq 10 ^ 5\leq r\leq 2\times 10 ^ 5$，这个启示我们在 $10 ^ 5$ 处给出一个分界线，然后左右分别 chkmin/chkmax，维护信息。

具体来说，我们维护两个数据结构，插入平凡，修改相当于是对于全局左端点 chkmax，右端点 chkmin。

直接使用 jls 线段树即可（当然全局 chkmin/chkmax 有其他做法）。现在问题是我们怎么维护区间交的长度和。

首先考虑我们直接使用 $\min(r_1, r_2) - \max(l_1, l_2)$ 计算所有答案，这个是好计算的，我们使用权值线段树 / 树状数组维护值域区间内个数以及值域区间内和就可以 $O(\log n)$ 查询。

然后考虑如果 $l_1 > r_2$，本身应该是 0，但是我们会得到 $r_2 - l_1$，所以我们加回来的话需要计算 $> r_2$ 的所有 $l$ 的个数和和。另一边同理。

据上我们可以得到一个 $O(\log m)$ 修改查询的做法。注意到这个做法只和 $l$ 集合，$r$ 集合相关，和他们如何配对的无关。这个对我们下面的推导是有一定作用的。

AC 做法

上面的启示性很强，我们马上可以得到一个做法：使用类似猫树的二区间分治结构，对每个区间都使用这个做法。但是和上面不同的是我们还需要考虑另外一些情况。

假设插入的是 $[l’, r’]$，我们在一个满足 $l\leq l’\leq mid < r’\leq r$ 的分治区间 $[l, r]$ 插入这个区间。容易发现这个分治区间是确定并且唯一的。插入由于需要动态维护权值树状数组，是 $O(\log m)$ 的。

考虑如何修改。直接在分治区间上修改，如果 $r’ > mid$，我们需要向右区间递归，当前分治区间所有满足 $r\geq l’$ 的都会被修改成 $[l’, \min(r, r’)]$。得到这个区间我们直接向右区间插入这个区间，注意到这个暴力的均摊复杂度是正确的（每个区间最多向下 $O(\log m)$ 次），所以我们直接在线段树上找出所有右端点 $\geq l’$ 的区间，一个一个修改即可。

如果当前分治区间满足 $l \leq l’\leq mid < r’\leq r$，那么可以发现和上面的情况类似，我们直接 jls 线段树即可。注意到此时我们不能直接返回，因为他对 $[l, mid]$ 和 $[mid + 1, r]$ 等分治区间还有贡献。由于完全覆盖是不存在贡献的，所以类似线段树的复杂度分析，最多只会访问 $O(\log m)$ 个节点。单次修改均摊是 $O(\log m)$ 的，因为我们需要更新树状数组。

分析以上复杂度：我们一共有 $O(k_1\log m)$ 次修改，单次修改是 $O(\log m)$ 的，jls 线段树上共有 $O(k_2 \log m)$ 次操作，均摊单次是 $O(\log n + \log m)$ 的。单次查询是 $O(\log m)$ 的。

于是总复杂度是 $O(k_1 \log ^ 2 m + k_2 \log m(\log n + \log m) + k_3\log m)$ 的，可以通过。

注意几个细节：

  1. 其实没人写 jls 线段树的罢，因为这个是好用 dsu / 堆 维护的，只是我 vp 的时候只想到了这里 /kk。但是由于线段树的强大，这个题有没有可能扩展到编号过后区间修改呢？
  2. 线段树大小是不固定的，这里我是用的类似 std::vector 的扩容办法，满了就增加一倍的空间。
  3. 注意插入时 $l’ = r’$ 需要特判一下，不然可能 RE/WA。
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
struct SegTree1 {
    struct Node {
        int l, r;
        int mn, sec, cnt, lt;
    };
    std::vector<Node> tr;
    int mid, L;

    void pushup(int x) {
        auto &nl = tr[x << 1], &nr = tr[x << 1 | 1], &rt = tr[x];
        if (nl.mn < nr.mn)
            rt.mn = nl.mn, rt.cnt = nl.cnt, rt.sec = std::min(nl.sec, nr.mn);
        else if (nl.mn > nr.mn)
            rt.mn = nr.mn, rt.cnt = nr.cnt, rt.sec = std::min(nr.sec, nl.mn);
        else
            rt.mn = nl.mn, rt.cnt = nl.cnt + nr.cnt, rt.sec = std::min(nl.sec, nr.sec);
    }

    void build(int x, int l, int r, int *a)
    {
        tr[x] = {l, r};
        if (l == r) {
            tr[x].mn = a[l], tr[x].sec = INF, tr[x].cnt = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(x << 1, l, mid, a), build(x << 1 | 1, mid + 1, r, a);
        pushup(x);
    }

    void update(int x, int c) { tr[x].mn += c, tr[x].lt += c; }

    void pushdown(int x) {
        if (!tr[x].lt) return;
        int mnl = tr[x << 1].mn, mnr = tr[x << 1 | 1].mn;
        if (mnl <= mnr) update(x << 1, tr[x].lt);
        if (mnl >= mnr) update(x << 1 | 1, tr[x].lt);
        tr[x].lt = 0;
    }

    void change(int x, int pos, int c)
    {
        if (tr[x].l == tr[x].r) {
            if (c <= mid) T1[0].add(c, 1), T1[1].add(c, c);
            return tr[x].mn = c, void();
        }
        pushdown(x);
        change(x << 1 | (pos * 2 > tr[x].l + tr[x].r), pos, c);
        pushup(x);
    }

    void modify(int x, int l, int r, int c) {
        if (tr[x].l > r || tr[x].r < l || tr[x].mn >= c) return;
        if (tr[x].l >= l && tr[x].r <= r && tr[x].sec > c) {
            T1[0].add(tr[x].mn, -tr[x].cnt), T1[1].add(tr[x].mn, (LL) -tr[x].cnt * tr[x].mn);
            T1[0].add(c, tr[x].cnt), T1[1].add(c, (LL) tr[x].cnt * c);
            return update(x, c - tr[x].mn);
        }
        pushdown(x);
        modify(x << 1, l, r, c), modify(x << 1 | 1, l, r, c);
        pushup(x);
    }

    void dfs(int x, std::vector<int> &vec, int lim)
    {
        if (tr[x].mn > lim) return;
        if (tr[x].l == tr[x].r) return vec.push_back(tr[x].l);
        pushdown(x);
        dfs(x << 1, vec, lim), dfs(x << 1 | 1, vec, lim);
    }

    int ask(int x, int pos) {
        if (tr[x].l == tr[x].r) return tr[x].mn;
        pushdown(x);
        return ask(x << 1 | (pos * 2 > tr[x].l + tr[x].r), pos);
    }

    void rebuild(std::vector<int> a, int _l, int _m)
    {
        mid = _m, L = _l;
        tr.resize(a.size() * 4);
        build(1, 0, a.size() - 1, a.data());
    }
    SegTree1() : tr(2, {0, 0, INF}), mid(0), L(0) {}
};

struct SegTree2 {
    struct Node {
        int l, r;
        int mx, sec, cnt, lt;
    };
    std::vector<Node> tr;
    int mid, R;

    void pushup(int x) {
        auto &nl = tr[x << 1], &nr = tr[x << 1 | 1], &rt = tr[x];
        if (nl.mx > nr.mx)
            rt.mx = nl.mx, rt.cnt = nl.cnt, rt.sec = std::max(nl.sec, nr.mx);
        else if (nl.mx < nr.mx)
            rt.mx = nr.mx, rt.cnt = nr.cnt, rt.sec = std::max(nr.sec, nl.mx);
        else
            rt.mx = nl.mx, rt.cnt = nl.cnt + nr.cnt, rt.sec = std::max(nl.sec, nr.sec);
    }

    void build(int x, int l, int r, int *a)
    {
        tr[x] = {l, r};
        if (l == r) {
            tr[x].mx = a[l], tr[x].sec = -INF, tr[x].cnt = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(x << 1, l, mid, a), build(x << 1 | 1, mid + 1, r, a);
        pushup(x);
    }

    void update(int x, int c) { tr[x].mx += c, tr[x].lt += c; }

    void pushdown(int x) {
        if (!tr[x].lt) return;
        int mxl = tr[x << 1].mx, mxr = tr[x << 1 | 1].mx;
        if (mxl >= mxr) update(x << 1, tr[x].lt);
        if (mxl <= mxr) update(x << 1 | 1, tr[x].lt);
        tr[x].lt = 0;
    }

    void change(int x, int pos, int c)
    {
        if (tr[x].l == tr[x].r) {
            if (c > mid) T2[0].add(c, 1), T2[1].add(c, c);
            return tr[x].mx = c, void();
        }
        pushdown(x);
        change(x << 1 | (pos * 2 > tr[x].l + tr[x].r), pos, c);
        pushup(x);
    }

    void modify(int x, int l, int r, int c) {
        if (tr[x].l > r || tr[x].r < l || tr[x].mx <= c) return;
        if (tr[x].l >= l && tr[x].r <= r && tr[x].sec < c) {
            T2[0].add(tr[x].mx, -tr[x].cnt), T2[1].add(tr[x].mx, (LL) -tr[x].cnt * tr[x].mx);
            T2[0].add(c, tr[x].cnt), T2[1].add(c, (LL) tr[x].cnt * c);
            return update(x, c - tr[x].mx);
        }
        pushdown(x);
        modify(x << 1, l, r, c), modify(x << 1 | 1, l, r, c);
        pushup(x);
    }

    void dfs(int x, std::vector<int> &vec, int lim)
    {
        if (tr[x].mx < lim) return;
        if (tr[x].l == tr[x].r) return vec.push_back(tr[x].l);
        pushdown(x);
        dfs(x << 1, vec, lim), dfs(x << 1 | 1, vec, lim);
    }

    int ask(int x, int pos) {
        if (tr[x].l == tr[x].r) return tr[x].mx;
        pushdown(x);
        return ask(x << 1 | (pos * 2 > tr[x].l + tr[x].r), pos);
    }

    void rebuild(std::vector<int> a, int _m, int _r)
    {
        mid = _m, R = _r;
        tr.resize(a.size() * 4);
        build(1, 0, a.size() - 1, a.data());
    }
    SegTree2() : tr(2, {0, 0, -INF}), mid(0), R(0) {}
};

struct Node {
    int l, r, sz;
    SegTree1 T1;
    SegTree2 T2;
} tr[N << 2];

void build(int x, int l, int r)
{
    tr[x] = {l, r, 0, SegTree1(), SegTree2()};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
}

void insert(int x, int l, int r)
{
    if (tr[x].l == tr[x].r) {
        T1[0].add(l, 1), T1[1].add(l, l), T2[0].add(l, 1), T2[1].add(l, l);
        return;
    }
    // if (l == r) std::cout << "Insert " << l << ' ' << r << '\n', exit(0);
    int mid = (tr[x].l + tr[x].r) >> 1;
    // std::cout << "Insert " << x << ' ' << l << ' ' << r << ' ' << tr[x].l << ' ' << tr[x].r << std::endl;
    if (r <= mid) return insert(x << 1, l, r);
    if (l > mid) return insert(x << 1 | 1, l, r);
    if (tr[x].sz & (tr[x].sz - 1)) {
        tr[x].T1.change(1, tr[x].sz, l), tr[x].T2.change(1, tr[x].sz, r);
        tr[x].sz ++;
        return;
    }
    std::vector<int> vl(tr[x].sz), vr(tr[x].sz);
    for (int i = 0; i < tr[x].sz; ++ i)
        vl[i] = tr[x].T1.ask(1, i), vr[i] = tr[x].T2.ask(1, i);
    vl.push_back(l), vr.push_back(r);
    int bit = 0;
    while ((1 << bit) <= tr[x].sz) bit ++;
    vl.resize(1 << bit, INF), vr.resize(1 << bit, -INF);
    tr[x].T1.rebuild(vl, tr[x].l, mid), tr[x].T2.rebuild(vr, mid, tr[x].r);
    tr[x].sz ++, T1[0].add(l, 1), T1[1].add(l, l), T2[0].add(r, 1), T2[1].add(r, r);
}

void modify(int x, int l, int r)
{
    if (tr[x].l >= l && tr[x].r <= r) return;
    // std::cout << "Modify " << x << ' ' << l << ' ' << r << ' ' << tr[x].l << ' ' << tr[x].r << std::endl;
    int mid = (tr[x].l + tr[x].r) >> 1;
    if (r <= mid) {
        std::vector<int> vec;
        tr[x].T1.dfs(1, vec, r);
        for (int id : vec) {
            int cl = tr[x].T1.ask(1, id), cr = tr[x].T2.ask(1, id);
            tr[x].T1.change(1, id, INF), tr[x].T2.change(1, id, -INF);
            insert(x << 1, std::max(l, cl), r);
            T1[0].add(cl, -1), T1[1].add(cl, -cl), T2[0].add(cr, -1), T2[1].add(cr, -cr);
        }
        return modify(x << 1, l, r);
    }
    if (l > mid) {
        std::vector<int> vec;
        tr[x].T2.dfs(1, vec, l);
        for (int id : vec) {
            // std::cout << "Check " << id << std::endl;
            int cl = tr[x].T1.ask(1, id), cr = tr[x].T2.ask(1, id);
            // std::cout << cl << ' ' << cr << std::endl;
            tr[x].T1.change(1, id, INF), tr[x].T2.change(1, id, -INF);
            insert(x << 1 | 1, l, std::min(r, cr));
            T1[0].add(cl, -1), T1[1].add(cl, -cl), T2[0].add(cr, -1), T2[1].add(cr, -cr);
        }
        return modify(x << 1 | 1, l, r);
    }
    tr[x].T1.modify(1, 0, tr[x].sz - 1, l), tr[x].T2.modify(1, 0, tr[x].sz - 1, r);
    modify(x << 1, l, r), modify(x << 1 | 1, l, r);
}

LL query(int l, int r)
{
    LL res = T1[0].ask(l) * l + T1[1].ask(M) - T1[1].ask(l);
    res = res * -1 + (T2[0].ask(M) - T2[0].ask(r)) * r + T2[1].ask(r);
    res += l * T2[0].ask(l) - T2[1].ask(l);
    res += T1[1].ask(M) - T1[1].ask(r) - r * (T1[0].ask(M) - T1[0].ask(r));
    return res;
}

int main()
{
    int m, op, l, r, typ;
    LL ls = 0;
    read(m, typ);
    build(1, 0, M);
    while (m --)
    {
        read(op, l, r);
        l = (l + ls * typ) % (M + 1), r = (r + ls * typ) % (M + 1);
        if (op == 1) insert(1, l, r);
        else if (op == 2) modify(1, l, r);
        else printf("%lld\n", ls = query(l, r));
        // printf("%lld\n", query(1, M));
    }
    return 0;
}