DDOSvoid's Blog

2021牛客多校7 xay loves monotonicity

发表于 更新于 分类于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11258/B

简要题意：给定两个序列 $a,b$ 和 $m$ 次操作，其中 $b$ 是 $01$ 序列，操作有三种，单点修改 $a$，$b$ 区间异或 $1$，查询给定区间 $[l,r]$ 的前缀最大值组成的序列的相邻两个的 $b$​ 的异或和​

$n,m\le 2\times 10^5$

Solution

首先如果我们不考虑 $b$ 的修改，那么这题完全就是楼房重建

现在我们考虑 $b$ 的修改，首先我们把 $b$ 差分一下，用树状数组维护，这样我们区间修改的时候只需要改两个点即可

然后我们继续套用楼房重建的做法，在需要查询 $b$ 的时候，我们直接用树状数组查询，这样看起来是 $O(n\log ^3n)$ 的

但实际上对于每一次 $calc(i,l,r,p)$​，我们只会在 $l=r$ 的最底层查询一次 $b$，所以时间复杂度还是 $O(n\log ^2n)$ 的

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
#include <iostream>
#include <algorithm>
#define maxn 200010
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m, a[maxn], b[maxn];

int Bit[maxn];
void add(int i, int v) { while (i <= n) Bit[i] ^= v, i += lowbit(i); }

int query(int i) {
    int s = 0;
    while (i) s ^= Bit[i], i -= lowbit(i); 
    return s; 
}

#define lc (i << 1)
#define rc (i << 1 | 1)
struct Seg {
    int p;
    pair<int, int> v;
} T[maxn * 4];
pair<int, int> calc(int i, int l, int r, int p) {
    if (a[T[i].p] < a[p]) return { 0, p };
    if (l == r) return make_pair(query(l) ^ query(p), l);
    int m = l + r >> 1; 
    if (a[T[lc].p] >= a[p]) {
        pair<int, int> t = calc(lc, l, m, p);
        return make_pair(t.first + T[i].v.first, T[i].v.second);
    }
    else return calc(rc, m + 1, r, p); 
}

inline void maintain(int i, int l, int r) {
    T[i].p = a[T[rc].p] >= a[T[lc].p] ? T[rc].p : T[lc].p;
    int m = l + r >> 1; 
    T[i].v = calc(rc, m + 1, r, T[lc].p); 
}

void build(int i, int l, int r) {
    if (l == r) return T[i].p = l, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i, l, r);
}

void update(int i, int l, int r, int k) {
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k);
    else update(rc, m + 1, r, k);
    maintain(i, l, r);
}

int last;
int query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0; 
    if (L <= l && r <= R) {
        pair<int, int> tmp = calc(i, l, r, last);
        last = tmp.second; return tmp.first;
    } int m = l + r >> 1; 
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R); 
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    a[x] = y; update(1, 1, n, x); 
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    add(x, 1); add(y + 1, 1);
    update(1, 1, n, x); if (y < n) update(1, 1, n, y + 1); 
}

inline void solve_3() {
    int x, y; cin >> x >> y;
    last = x; cout << query(1, 1, n, x + 1, y) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    for (int i = 1; i <= n; ++i) cin >> b[i], add(i, b[i] ^ b[i - 1]); 
    build(1, 1, n); cin >> m; 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break; 
        case 3 : solve_3(); break;
        }
    }
    return 0;
}