[题解]LuoGu5283：[十二省联考2019]异或粽子

原题传送门
Unbelievable!我也能自己a省选题了？

前几天刚刚做过一道题：BZOJ3689异或之
先讲讲这道题

【BZOJ3689】异或之

Description

给定n个非负整数A[1], A[2], ……, A[n]。
对于每对(i, j)满足1 <= i < j <= n，得到一个新的数A[i] xor A[j]，这样共有n*(n-1)/2个新的数。求这些数（不包含A[i]）中前k小的数。
注：xor对应于pascal中的“xor”，C++中的“^”。

Input

第一行2个正整数 n,k，如题所述。
以下n行，每行一个非负整数表示A[i]。

Output

共一行k个数，表示前k小的数。

Sample Input

4 5
1
1
3
4

Sample Output

0 2 2 5 5

HINT

【样例解释】

1 xor 1 = 0 (A[1] xor A[2])
1 xor 3 = 2 (A[1] xor A[3])
1 xor 4 = 5 (A[1] xor A[4])
1 xor 3 = 2 (A[2] xor A[3])
1 xor 4 = 5 (A[2] xor A[4])
3 xor 4 = 7 (A[3] xor A[4])
前5小的数：0 2 2 5 5

【数据范围】

对于100%的数据，2 <= n <= 100000； 1 <= k <= min{250000, n*(n-1)/2}；
0 <= A[i] < 2^31

solution

其实trie也可以实现异或第k大的
可以通过类似平衡树求kth的方法，开个size的桶
把每个数与其他数异或的第k大求出来
然后用优先队列，开个小根堆，当用好一个数与其他数的异或第k大时，把第k+1大加入堆
会有重复，会出现算好x ^ y，然后来y ^ x的情况，所以每两个只能用一个
具体见代码：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
struct node{
    int ans, a, id;
    bool operator < (const node & x) const{
        return ans > x.ans;
    }
};
priority_queue <node> q;
int n, m, size[maxn * 30], ch[maxn * 30][3], sz, a[maxn];
  
inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}
  
void insert(int x){
    int u = 0;
    for (int i = 30; i >= 0; --i){
        int c = (x & (1 << i)) != 0;
        u = ch[u][c] ? ch[u][c] : ch[u][c] = ++sz;
        ++size[u];
    }
}
  
int query(int x, int k){
    int u = 0, ans = 0;
    for (int i = 30; i >= 0; --i){
        int c = (x & (1 << i)) != 0;
        if (size[ch[u][c]] >= k) u = ch[u][c]; else ans += (1 << i), k -= size[ch[u][c]], u = ch[u][c ^ 1];
        //如果有k以上个数当前数位与x一样，当然选择异或，因为这样数位上就变0了，否则，得与当前数位上与自己不一样的数异或
    }
    return ans;
}
  
int main(){
    n = read(), m = read();
    for (int i = 1; i <= n; ++i){
        a[i] = read(); insert(a[i]);
    }
    for (int i = 1; i <= n; ++i){
        node tmp;
        tmp.ans = query(a[i], 2);
        //取第2小是因为最小的是自己异或自己，不算
        tmp.a = a[i], tmp.id = 2;
        q.push(tmp);
    }
    for (int i = 1; i <= (m << 1); ++i){
        node tmp = q.top(); q.pop();
        if (i & 1) printf("%d", tmp.ans);//每两个只能用一个
        if (i & 1 && i < (m << 1) - 1) printf(" ");//行末不能有空格
        if (++tmp.id >= n) continue;//id++
        tmp.ans = query(tmp.a, tmp.id);
        q.push(tmp);
    }
    printf("\n");
    return 0;
}

然后开始讲这道异或粽子

solution

刚看完题就感觉跟异或之非常像，不过看到区间异或和就失望了，因为我知道上一题的trie是两个数异或起来，然而这一题是处理一堆数异或起来
唉，好像这个区间必须连续，想到什么？前缀和！
预处理前缀异或和，[l,r]的异或和就是[1,r] ^ [1,l-1]
那么每一段区间的异或和都可以表示为两个前缀异或和的异或和（l=1的情况时，让[1,r]与0异或）

但是上一题是处理前k小，这一题求前k大，没关系，前k大就是倒数k小 ^ - ^
化归到上一题
另外，不要忘了long long

Code：

#include <bits/stdc++.h>
#define maxn 500010
#define int long long
using namespace std;
struct node{
	int a, ans, id;
	bool operator < (const node & x) const{
		return ans < x.ans;
	}
};
priority_queue <node> q;
int a[maxn], n, m, size[maxn * 31], sz, ch[maxn * 31][2];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void insert(int x){
	int u = 0;
	for (int i = 31; i >= 0; --i){
		int c = (x & (1 << i)) != 0;
		++size[u = ch[u][c] ? ch[u][c] : ch[u][c] = ++sz];
	}
}

int query(int x, int k){
	int u = 0, ans = 0;
	for (int i = 31; i >= 0; --i){
		int c = (x & (1 << i)) != 0;
		if (size[ch[u][c]] >= k) u = ch[u][c]; else k -= size[ch[u][c]], ans += (1LL << i), u = ch[u][c ^ 1];
	}
	return ans;
}
//跟上一题一样的套路

signed main(){
	n = read(), m = read();
	a[0] = 0; insert(0);
	for (int i = 1; i <= n; ++i){
		int x = read();
		insert(a[i] = a[i - 1] ^ x);//前缀异或和
	}
	for (int i = 0; i <= n; ++i){
		node tmp;
		tmp.ans = query(a[i], n + 1);//因为0也参与，所以总共有n+1个数参与，所以取第n+1小个
		tmp.a = a[i], tmp.id = n + 1;
		q.push(tmp);
	}
	int ans = 0;
	for (int i = 1; i <= (m << 1); ++i){
		node tmp = q.top(); q.pop();
		if (i & 1) ans += tmp.ans;
		--tmp.id;
		if (tmp.id == 1) continue;
		tmp.ans = query(tmp.a, tmp.id);
		q.push(tmp);
	}
	printf("%lld\n", ans);
	return 0;
}