https://codeforces.com/contest/2064/problem/D
题目大意
给出一个 $n$ 长的数组 $a$，和 $q$ 个独立询问（每次询问结束恢复 $a$）。对于某个询问，给出 $x$，然后如果 $x$ 不小于 $a$ 最后的元素 $a_{last}$ 则把 $x$ 变为 $x \ xor a_{last}$ 并删掉 $a_{last}$，问这个操作能进行几次。
$1 \le n, q \le 2 \times 10^5$。$1 \le a_i, x_i \le 2 ^ {30}$。
简要题解
观察：
- $x$ 一定会"吃掉"其左侧相邻的所有最高位比它小的元素。因为吃掉这些数不改变最高位，且总有最高位比这些吃掉的数大。
- 当 $x$ 遇到最高位更大的数时一定结束。
- 当 $x$ 遇到最高位相等的数时，要么不能吃，要么最高位会变小。也就是说整个流程最高位是单调不增的。
有了这些观察我们可以预处理前缀异或，以及类似于倍增的预处理每个位置左侧最近的一个最高位 $\ge j$ 的位置，然后询问时只要从最右侧依次一段一段的处理就可以了。
复杂度
$T$：$O((n + q) \log C)$：$C$ 为 $a_i, x_i$ 的最大值。
$S$：$O(n \log C)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int M = 2e5 + 5;
const int MB = 30;
int lft[M][MB];
int sum[M];
inline int highbit(int x) { return 31 - __builtin_clz(x); }
void solve() {
int n, q; cin >> n >> q;
vector<int> a(n);
for (int& i : a) cin >> i;
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] ^ a[i];
int hb = highbit(a[i]);
for (int j = 0; j < MB; j++) {
lft[i + 1][j] = (j <= hb ? (i + 1) : lft[i][j]);
}
}
int x;
for (int i = 0; i < q; i++) {
cin >> x;
int l = n;
while (l > 0 && x > 0) {
int hb = highbit(x);
int nl = lft[l][hb];
// cerr << x << ' ' << nl << endl;
if (nl < l) {
x ^= (sum[l] ^ sum[nl]);
}
// cerr << " x " << x << endl;
l = nl;
if (l == 0 || x < a[l - 1]) break;
x ^= a[l - 1];
l--;
}
cout << (n - l) << (" \n"[i == q - 1]);
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Remove the Ends - Codeforces Round 1005 (Div. 2)