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

题目大意：

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

题目思路：

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

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

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

#include<bits/stdc++.h>

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 val<rhs.val;

    }

};

priority_queue<node>pq;

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]]<rk){

            rk-=cnt[ch[u][now^1]];

            u=ch[u][now];

        }

        else{

            rep|=(1LL<<i);

            u=ch[u][now^1];

        }

    }

    return rep;

}

int main(){

    scanf("%d%d",&n,&k);

    insert(0,rt[0],0,31);

    for(int i=1;i<=n;i++){

        kth[i]=1;

        scanf("%lld",&a[i]);

        sum[i]=sum[i-1]^a[i];

        insert(rt[i-1],rt[i],sum[i],31);

        pq.push(node(query(rt[i-1],sum[i],kth[i]),i));

    }

    while(k--){

        node u=pq.top();pq.pop();

        ++kth[u.id];

        ans+=u.val;

        pq.push(node(query(rt[u.id-1],sum[u.id],kth[u.id]),u.id));

    }

    printf("%lld\n",ans);

    return 0;

}