可持久化trie做法,全WA求调,有注释
查看原帖
可持久化trie做法,全WA求调,有注释
421265
eastcloud楼主2022/7/28 18:50
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
struct Node{
	ll l,r,pl,val,rp;//l,r是区间的左右端点,pl是取到答案的点,val是答案,rp是对应的右边那个点
};
bool operator <(Node x,Node y){
	return x.val<y.val;
}
priority_queue<Node> t;
ll tr[40000004][2];
ll lat[40000004],rt[500005];
ll sum[500005];
ll tot,rt_tot,pl,val;
void insert(ll x){//可持久化trie插入操作,循环的写法
	rt[++rt_tot]=++tot;
	ll q=rt[rt_tot-1],p=rt[rt_tot];//p是现在的根,q是原先的根
	for(ll i=34;i>=0;i--){
		ll num=(x>>i)&1;
		if(q) tr[p][num^1]=tr[q][num^1];
		tr[p][num]=++tot;
		p=tr[p][num];
		q=tr[q][num];
		lat[p]=rt_tot;//lat表示此位置目前最晚的出现时间(第r个版本)
	}
}
void pre(){//插入一个权值为0的数,就是预处理,我不会两个合起来写...与插入操作相同
	rt[0]=++tot;
	ll q=0,p=rt[0];
	for(ll i=34;i>=0;i--){
		ll num=0;
		if(q) tr[p][num^1]=tr[q][num^1];
		tr[p][num]=++tot;
		p=tr[p][num];
		q=tr[q][num];
		lat[p]=rt_tot;
	}
}
void query(ll l,ll r,ll x){//查询操作,ans存储的是要查询的前缀和,p是当前下标
	ll p=rt[r],ans=0;
	for(ll i=34;i>=0;i--){
		ll num=(x>>1)&1;
		if(tr[p][num^1] && lat[tr[p][num^1]]>=l){
			p=tr[p][num^1];
			ans+=((num^1)?(1<<i):0);
		}
		else{
			p=tr[p][num];
			ans+=(num?(1<<i):0);
		}
	}
	val=ans;
	pl=lat[p];//pl表示查询到的数是第几个
}
int main(){
	ll n,k,tmp;
	sum[0]=0;
	cin>>n>>k;
	pre();
	for(ll i=1;i<=n;i++){
		cin>>tmp;
		sum[i]=tmp^sum[i-1];
		insert(sum[i]);
		query(0,i-1,sum[i]);
		t.push((Node){0,i-1,pl,val^sum[i],i});
	}
	ll ans=0;
	for(ll i=1;i<=k;i++){
		Node tp=t.top();
		ans+=tp.val;
		if(tp.pl-1>=tp.l){//对不越界的区间分裂然后求值插到大根堆里,分成(tp.l,tp.pl-1),(tp.pl+1,tp.r),两个区间,lat数组可以保证查出的数最晚出现的位置一定>=l
			query(tp.l,tp.pl-1,sum[tp.rp]);
			t.push((Node){tp.l,tp.pl-1,pl,(sum[tp.rp]^val),tp.rp});
		}
		if(tp.pl+1<=tp.r){
			query(tp.pl+1,tp.r,sum[tp.rp]);
			t.push((Node){tp.pl+1,tp.r,pl,(sum[tp.rp]^val),tp.rp});
		}
	}
	cout<<ans;
}
2022/7/28 18:50
加载中...