# CF1625D.Binary Spiders(CF1625D. Binary Spiders)-其他

## CF1625D.Binary Spiders(CF1625D. Binary Spiders)

### $$\text{Code}$$

#include <cstdio>
#include <iostream>
#include <algorithm>
#define RE register
#define IN inline
using namespace std;
typedef long long LL;

const int N = 3e5 + 5;
int n, m, f[N], g[N], Len, size, rt;
struct node{int v, id;}a[N];
IN bool cmp(node a, node b){return a.v < b.v;}

int seg[N * 31], ls[N * 31], rs[N * 31];
void Modify(int &p, int l, int r, int x, int v)
{
if (!p) p = ++size;
if (l == r) return seg[p] = v, void();
int mid = l + r >> 1;
if (x <= mid) Modify(ls[p], l, mid, x, v);
else Modify(rs[p], mid + 1, r, x, v);
if (f[seg[ls[p]]] > f[seg[rs[p]]]) seg[p] = seg[ls[p]];
else seg[p] = seg[rs[p]];
}
int Query(int p, int l, int r, int x, int y)
{
if (x > r || y < l) return 0;
if (x <= l && r <= y) return seg[p];
int mid = l + r >> 1, L = 0, R = 0;
if (ls[p] && x <= mid) L = Query(ls[p], l, mid, x, y);
if (rs[p] && y > mid)
{
R = Query(rs[p], mid + 1, r, x, y);
if (!L) L = R;
else{
if (f[L] > f[R]) return L;
return R;
}
}
return L;
}

int main()
{
scanf("%d%d", &n, &m);
for(RE int i = 1; i <= n; i++) scanf("%d", &a[i].v), a[i].id = i;
sort(a + 1, a + n + 1, cmp), Len = a[n].v;
int ans = 1, pos = 0, pre, cur;
for(RE int i = 1; i <= n; i++)
{
f[i] = 1, pre = 0;
for(RE int j = 30; j >= 0; j--)
{
if ((m >> j) & 1){if (!((a[i].v >> j) & 1)) pre |= (1 << j);}
else{
if ((a[i].v >> j) & 1)
{
cur = Query(rt, 0, Len, pre, pre + (1 << j) - 1), pre |= (1 << j);
if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
}
else{
cur = Query(rt, 0, Len, pre + (1 << j), (LL)pre + (1LL << j + 1) - 1);
if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
}
}
if (!j)
{
cur = Query(rt, 0, Len, pre, pre);
if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
}
}
if (ans < f[i]) ans = f[i], pos = i;
if (i < n) Modify(rt, 0, Len, a[i].v, i);
}
printf("%d\n", (ans == 1) ? -1 : ans);
if (ans > 1) while (pos) printf("%d ", a[pos].id), pos = g[pos];
}
————————

### $$\text{Problem}$$

Give the number of \ (n \) and \ (m \), and select the maximum number so that the pairwise XOR value is greater than or equal to \ (m \)
Output scheme

### $$\text{Solution}$$

At first, the idea was very complicated
In fact, it’s good to use a conclusion
For an ascending sequence, the XOR minimum between them is the XOR minimum of adjacent numbers
So you can sort first and then \ (DP \)
Set \ (f_i \) to indicate the maximum number that can be selected by forcing \ (I \) to the \ (I \) bit
Then \ (f_i = f_ {J} + 1 (1 \ Le J & lt; I, a_j \ oplus a_i \ Ge m) \)
Therefore, the \ (DP \) of this \ (O (n ^ 2) \) can be optimized
This is a very simple thing
Consider the selection of \ (J \)
If \ (a_i \ oplus a_j & gt; m \), the XOR value is equal to \ (m \) from high to low, and then greater than \ (m \) in some bit
Then we enumerate the number of bits from high to low, consider that it is equal to \ (m \) before this bit, and count the contribution of this bit greater than \ (m \)
The \ (0 / 1 \) values of \ (m \) and \ (a_i \) are discussed. It is found that the feasible value interval is continuous, and the weight segment tree can be used
Finally, deal with the contribution of \ (a_i \ oplus a_j = m \)

### $$\text{Code}$$

#include <cstdio>
#include <iostream>
#include <algorithm>
#define RE register
#define IN inline
using namespace std;
typedef long long LL;

const int N = 3e5 + 5;
int n, m, f[N], g[N], Len, size, rt;
struct node{int v, id;}a[N];
IN bool cmp(node a, node b){return a.v < b.v;}

int seg[N * 31], ls[N * 31], rs[N * 31];
void Modify(int &p, int l, int r, int x, int v)
{
if (!p) p = ++size;
if (l == r) return seg[p] = v, void();
int mid = l + r >> 1;
if (x <= mid) Modify(ls[p], l, mid, x, v);
else Modify(rs[p], mid + 1, r, x, v);
if (f[seg[ls[p]]] > f[seg[rs[p]]]) seg[p] = seg[ls[p]];
else seg[p] = seg[rs[p]];
}
int Query(int p, int l, int r, int x, int y)
{
if (x > r || y < l) return 0;
if (x <= l && r <= y) return seg[p];
int mid = l + r >> 1, L = 0, R = 0;
if (ls[p] && x <= mid) L = Query(ls[p], l, mid, x, y);
if (rs[p] && y > mid)
{
R = Query(rs[p], mid + 1, r, x, y);
if (!L) L = R;
else{
if (f[L] > f[R]) return L;
return R;
}
}
return L;
}

int main()
{
scanf("%d%d", &n, &m);
for(RE int i = 1; i <= n; i++) scanf("%d", &a[i].v), a[i].id = i;
sort(a + 1, a + n + 1, cmp), Len = a[n].v;
int ans = 1, pos = 0, pre, cur;
for(RE int i = 1; i <= n; i++)
{
f[i] = 1, pre = 0;
for(RE int j = 30; j >= 0; j--)
{
if ((m >> j) & 1){if (!((a[i].v >> j) & 1)) pre |= (1 << j);}
else{
if ((a[i].v >> j) & 1)
{
cur = Query(rt, 0, Len, pre, pre + (1 << j) - 1), pre |= (1 << j);
if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
}
else{
cur = Query(rt, 0, Len, pre + (1 << j), (LL)pre + (1LL << j + 1) - 1);
if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
}
}
if (!j)
{
cur = Query(rt, 0, Len, pre, pre);
if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
}
}
if (ans < f[i]) ans = f[i], pos = i;
if (i < n) Modify(rt, 0, Len, a[i].v, i);
}
printf("%d\n", (ans == 1) ? -1 : ans);
if (ans > 1) while (pos) printf("%d ", a[pos].id), pos = g[pos];
}