• 欢迎光临~

# Codeforces Round #815 (Div. 2) D2 Xor-Subsequence (hard version)

(A>B)，总是有二进制下从高到低的前(k)位相等，第(k+1)(A)(1)(B)(0)

(a_ioplus j)(a_joplus i)的前(k)位相等，等价于(a_ioplus i)(a_joplus j)的前(k)位相等

``````#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef unsigned long long ULL;

const int INF = 0X3f3f3f3f, N = 3e5 + 10, MOD = 1e9 + 7;
const double eps = 1e-7, pi = acos(-1);

int idx;
int a[N];
int tr[N * 40][2], dp[N * 40][2];

void insert(int x, int y) {
int p = 0;
rrep (i, 30, 0) {
int u = x >> i & 1, v = y >> i & 1;
if (!tr[p][u ^ v]) tr[p][u ^ v] = ++idx;
p = tr[p][u ^ v];
}
}

int query(int x, int y) {
int p = 0, q = 0, mx = 0;
rrep (i, 30, 0) {
int u = x >> i & 1, v = y >> i & 1;
q = tr[p][!(u ^ v)], p = tr[p][u ^ v];
if (q) mx = max(mx, dp[q][v]);
if (!p) break;
}
return mx + 1;
}

void update(int x, int y, int mx) {
int p = 0;
rrep (i, 30, 0) {
int u = x >> i & 1, v = y >> i & 1;
p = tr[p][u ^ v];
dp[p][u] = max(dp[p][u], mx);
}
}

void work() {
int n;
cin >> n;
rep (i, 0, n - 1) cin >> a[i];

int res = 0;
rep (i, 0, n - 1) {
int mx = query(a[i], i);
res = max(res, mx);
insert(a[i], i);
update(a[i], i, mx);
}

cout << res << endl;

rep (i, 0, idx) tr[i][0] = tr[i][1] = dp[i][0] = dp[i][1] = 0;
idx = 0;
}

signed main() {
IO

int test = 1;
cin >> test;

while (test--) {
work();
}

return 0;
}
``````