CF1100F Ivan and Burgers

CF1100F Ivan and Burgers

靜態區間，選取任意個數使得它們的異或和最大

\(n,\ m\leq5\times10^5,\ a_i\in[0,\ 10^6]\)

lxl ST表，線性基

---

如果暴力維護線性基，線段樹時間復雜度為 \(O(n\log^2n)-O(\log^3n)\)

由于重復元素對答案沒有影響，于是可以用 ST表 維護，時間復雜度為 \(O(n\log^3n)-O(\log^2n)\)

兩種做法都無法通過本題。

如果沿用這個思路，瓶頸顯然在線性基合并的 \(O(\log^2n)\) 上，無法再加優化

線段樹做法顯然無法再加拓展（和 lxl ST表時間復雜度一樣的貓樹空間復雜度多一只 \(\log\) ），于是考慮拓展 ST表 做法

常見的 RMQ 有 ST表 的 \(O(n\log n)-O(1)\) 的做法，但 \(O(n)-O(1)\) 的標準RMQ很難寫、常數較大，且無法解決本題，于是可以考慮在隨機數據下期望 \(O(n)-O(1)\) 的 lxl ST表

分塊，大小設為 \(x\)

預處理每個塊兩端到塊內每個點的前綴 \(\max\) 和后綴 \(\max\)

預處理塊間ST表

若查詢 \([l,\ r]\) ，且 \(l,\ r\) 分別在塊 \(a,\ b\) 中

比如說我查l，r，這兩個分別在塊a，b中

則查塊 \(a,\ b\) 之間的 RMQ ，以及 \(l\) 在 \(a\) 塊的后綴 \(\max\) 和 \(r\) 在 \(b\) 塊的前綴 \(\max\)

當 \(l,\ r\) 在同一塊中時，暴力求解

可以取 \(x=\log n\) ，當 \(l,\ r\) 不在同一塊中時，這個算法是 \(O(1)\) 的

摘自 P3793 由乃救爺爺

如上維護，預處理塊中前綴后綴線性基 \(O(n\log n)\) ，塊間ST表線性基 \(O(\frac{n}{x}\log n\log^2n)=O(n\log^2n)\)

若 \(l,\ r\) 在同一塊中，將 \([l,\ r]\) 中的元素暴力插入線性基， \(O(x\log n)=O(\log^2n)\) ；若 \(l,\ r\) 不在同一塊中，合并前綴后綴塊間三個線性基 \(O(\log^2n)\)

綜上所述，時間復雜度 \(O(n\log^2n)\) ，空間復雜度 \(O(n\log n)\) 可能還需要卡卡常

代碼

#include <bits/stdc++.h>
using namespace std;const int maxn = 5e5 + 10, maxm = 7850, base = 63;
int n, m, tot, lg[maxm], a[maxn];#define get(x) (((x) + base) >> 6)struct linear_base {int a[20];inline void clr() {memset(a, 0, sizeof a);}inline void ins(int x, int lim = 19) {for (int i = lim; ~i; --i) {if (x >> i & 1) {if (!a[i]) { a[i] = x; return; }x ^= a[i];}}}inline int query() {int res = 0;for (int i = 19; ~i; --i) {if ((res ^ a[i]) > res) res ^= a[i];}return res;}
} null, lef[maxn], rig[maxn], val[13][maxm];inline linear_base operator + (linear_base A, const linear_base &B) {for (int i = 19; ~i; --i) {if (B.a[i]) A.ins(B.a[i], i);}return A;
}const int maxn_r = maxn * 23, maxn_w = maxn * 8;
char buf_r[maxn_r], *now_r = buf_r;
char buf_w[maxn_w], *now_w = buf_w;inline int read() {int x = 0;while (*now_r < 48) ++now_r;while (*now_r > 47) x = (x << 3) + (x << 1) + (*now_r ^ 48), ++now_r;return x;
}inline void write(int x) {static char *tp, st[7];if (!x) *now_w = 48, ++now_w;for (tp = st; x; *++tp = x % 10 | 48, x /= 10);while (tp != st) *now_w = *tp, ++now_w, --tp;*now_w = 10, ++now_w;
}inline linear_base query(const int &l, const int &r) {if (l > r) return null;const int k = lg[r - l + 1];return val[k][l] + val[k][r - (1 << k) + 1];
}int main() {fread(buf_r, 1, maxn_r, stdin);n = read(), tot = get(n);for (int i = 1; i <= n; ++i) {a[i] = read();val[0][get(i)].ins(a[i]);}for (int i = 2; i <= tot; ++i) {lg[i] = lg[i >> 1] + 1;}linear_base lst;lst.clr();for (int i = 1; i <= n; ++i) {lst.ins(a[i]), lef[i] = lst;if (!(i & base)) lst.clr();}lst.clr();for (int i = n; i; --i) {if (!(i & base)) lst.clr();lst.ins(a[i]), rig[i] = lst;}for (int i = 1; i <= lg[tot]; ++i) {for (int j = 1; j + (1 << i) - 1 <= tot; ++j) {val[i][j] = val[i - 1][j] + val[i - 1][j + (1 << (i - 1))];}}m = read();register linear_base ans;for (int q = 1; q <= m; ++q) {const int l = read(), r = read();const int L = get(l), R = get(r);ans.clr();if (L == R) {for (register int i = l; i <= r; ++i) {ans.ins(a[i]);}} else {ans = rig[l] + lef[r] + query(L + 1, R - 1);}write(ans.query());}fwrite(buf_w, 1, now_w - buf_w, stdout);return 0;
}