yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P5607 [Ynoi2013] 无力回天 NOI2017

发表于 分类于

P5607 [Ynoi2013] 无力回天 NOI2017

题面

题目链接

解法

首先我们有一个错误的想法，像普通的区间修改区间和线段树一样给线性基维护懒标记。但是仔细想想发现无法区间修改线性基。

所以我们希望能将区间修改转化成若干的单点修改。一般来说，这种情况需要使用差分。设数组 $b$ 为 $a$ 的差分数组。

注意到 $al, a{l+1}, \cdots, ar$ 的线性基就等于 $a_l, b{l+1}, \cdots, br$ 的线性基。所以求出 $b{l+1 \cdots r}$ 的线性基后插入 $a_l$，再在其中查询 $\oplus v$ 的最大值即可。

时间复杂度为 $O(n \log^2 m)$，难得不需要卡常。

AC代码

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
/**
 * @file:           P5607.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P5607
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false; char ch = getchar(); double tmp = 1;
    for (; !isdigit(ch); ch = getchar()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar((x % 10) ^ 48);
}
bool m_be;
using ll = long long;
const int MAXN = 5e4 + 10;
const int MAXK = 31;
const int INF = 0x3f3f3f3f;
int n, q, a[MAXN], c[MAXN];
struct LinearBase {
    int bs[MAXK];
    LinearBase() { memset(bs, 0, sizeof(bs)); }
    void clear() { memset(bs, 0, sizeof(bs)); }
    void insert(int x) {
        for (int i = MAXK - 1; ~i; --i) {
            if (!((x >> i) & 1)) continue;
            if (!bs[i]) return void(bs[i] = x);
            x ^= bs[i];
        }
    }
    int query(int x) const {
        for (int i = MAXK - 1; ~i; --i)
            if ((x ^ bs[i]) > x) x ^= bs[i];
        return x;
    }
    LinearBase operator^(const LinearBase& o) const {
        LinearBase ret;
        for (int i = 0; i < MAXK; ++i) {
            if (bs[i]) ret.insert(bs[i]);
            if (o.bs[i]) ret.insert(o.bs[i]);
        }
        return ret;
    }
};
struct SegmentTree {
    #define li (i << 1)
    #define ri (i << 1 | 1)
    #define lson li, l, mid
    #define rson ri, mid + 1, r
    LinearBase sum[MAXN * 4];
    void pushup(int i) { sum[i] = sum[li] ^ sum[ri]; }
    void build(int i, int l, int r) {
        if (l == r) return sum[i].insert(a[l]);
        int mid = (l + r) >> 1; build(lson), build(rson), pushup(i);
    }
    void update(int i, int l, int r, int q, int v) {
        if (l == r) {
            for (int j = 0; j < MAXK; ++j)
                if (sum[i].bs[j]) return void(sum[i].bs[j] ^= v);
            return sum[i].insert(v);
        }
        int mid = (l + r) >> 1;
        q <= mid ? update(lson, q, v) : update(rson, q, v), pushup(i);
    }
    LinearBase query(int i, int l, int r, int ql, int qr) {
        if (ql > qr) return LinearBase();
        if (ql <= l && r <= qr) return sum[i];
        int mid = (l + r) >> 1, ret = 0;
        if (qr <= mid) return query(lson, ql, qr);
        if (ql > mid) return query(rson, ql, qr);
        return query(lson, ql, qr) ^ query(rson, ql, qr);
    }
} sgt;
inline void add(int i, int v) { for (; i <= n; i += (i & -i)) c[i] ^= v; }
inline int sum(int i) { int s = 0; for (; i; i -= (i & -i)) s ^= c[i]; return s; }
bool m_ed;
signed main() {
    // debug("Mem %.5lfMB.", fabs(&m_ed - &m_be) / 1024 / 1024);
    read(n), read(q);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = n; i >= 1; --i) a[i] ^= a[i - 1];
    for (int i = 1; i <= n; ++i) add(i, a[i]);
    sgt.build(1, 1, n);
    while (q--) {
        int op, l, r, v;
        read(op), read(l), read(r), read(v);
        if (op == 1) {
            sgt.update(1, 1, n, l, v), add(l, v);
            if (r != n) sgt.update(1, 1, n, r + 1, v), add(r + 1, v);
        } else {
            LinearBase lb = sgt.query(1, 1, n, l + 1, r);
            lb.insert(sum(l));
            write(lb.query(v)), putchar('\n');
        }
    }
    return 0;
}