Luogu P5283 / LOJ3048 【[十二省联考2019]异或粽子】

联考Day1T1...一个考场上蠢了只想到\(O(n^2)\)复杂度的数据结构题

题目大意：

求前\(k\)大区间异或和的和

题目思路：

真的就是个sb数据结构题，可持久化01Trie能过(开O2)。

对于区间异或和，显然可以处理成两个前缀异或和的异或和，然后做法就非常蠢，把所有前缀异或和插入到可持久化01Trie里面，然后求以每个位置为右端点的最大区间前缀和，放入大根堆维护。然后从堆中取\(k\)次最大，每次取完把对应位置的相对当前的次大插入堆中。复杂度\(O(开O2能过)\)qwq。众所周知01Trie非常短而且好写不容易错，刚写了一遍直接就过了(忽略没开O2被卡一个点的那次提交)。

当时真是蠢了，没想到用01Trie真的是sb。

#include

using namespace std;

const int N=5e5+5;

int n,k,rt[N],ch[N*40][2],cnt[N*40],cntnode,kth[N];

long long a[N],sum[N],ans;

struct node{
    long long val;int id;
    node(long long rv=0,int ri=0){
        val=rv;id=ri;
    }
    bool operator<(const node&rhs)const{
        return valpq;

void insert(int lr,int &u,long long v,int dep){
    u=++cntnode;
    ch[u][0]=ch[lr][0];ch[u][1]=ch[lr][1];cnt[u]=cnt[lr];
    ++cnt[u];
    if(~dep){
        int now=(v>>dep)&1;
        insert(ch[lr][now],ch[u][now],v,dep-1);
    }
}

long long query(int u,long long v,int rk){
    long long rep=0;int now;
    for(int i=31;~i;i--){
        now=(v>>i)&1;
        if(cnt[ch[u][now^1]]