可持久化trie+优先队列做法,RE on 9-12and17-20, 求助
查看原帖
可持久化trie+优先队列做法,RE on 9-12and17-20, 求助
498330
『朔月·尘封』楼主2022/8/31 15:43
#include<bits/stdc++.h>
#define fr(i,a,b,k) for(int i=a;i<=b;i+=k)
#define fo(i,a,b,k) for(int i=a;i>=b;i-=k)
#define int long long
#define N 500005+10
using namespace std;
struct node{
	int st;
	int l,r;
	int pos;
	int sum;
};
bool operator<(node a, node b) {
    return a.sum < b.sum;
} 
int n,k;
long long a[N];
long long s[N]; 
long long ans;
priority_queue <node> q;
int trie[N*100][4];
int vis[N*100];
int rt[N];
int tot;

inline long long read(){
    register int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48); 
        c=getchar();
    }
    return x*f;
}

void insert(int p,int q,int val,int k){
	vis[p]=k;
	fo(i,32,0,1){
		int x=(val>>i)&1;
		trie[p][x]=++tot;
		trie[p][x^1]=trie[q][x^1];
		p=trie[p][x];
		q=trie[q][x];
		vis[p]=k;
	}
	
}
int query(int l,int p,int val){
	fo(i,32,0,1){
		int x=(val>>i)&1;
		if(vis[trie[p][x^1]]>=l){
			p=trie[p][x^1];
		}else{
			p=trie[p][x];
		}
	}
	return vis[p];
}
signed main(){
	n=read();
	k=read();
	vis[0]=-1;
	fr(i,1,n,1){
		a[i]=read();
		s[i]=s[i-1]^a[i];
		rt[i]=++tot;
		insert(rt[i],rt[i-1],s[i],i);
	}
	fr(i,1,n,1){
		int t=query(i,rt[n],s[i-1]);
		q.push((node){i,i,n,t,s[i-1]^s[t]});
	}
	while(k--){
		node e=q.top();
		q.pop();
		ans+=e.sum;
		if(e.l<e.pos){
		int t=query(e.l,rt[e.pos-1],s[e.st-1]);
		q.push((node){e.st,e.l,e.pos-1,t,s[e.st-1]^s[t]});
		}
//		e.st e.l     e.pos-1 
//		e.st e.pos+1 e.r
		if(e.pos<e.r){
		int t=query(e.pos+1,rt[e.r],s[e.st-1]);
		q.push((node){e.st,e.pos+1,e.r,t,s[e.st-1]^s[t]});
		}
	}
	cout<<ans<<endl;
	return 0;
}
2022/8/31 15:43
加载中...