并不对劲的loj3048:p5283:[十二省联考]异或粽子

题目大意

有\(n\)(\(n\leq5\times10^5\))个数\(a_1,a_2,...a_n\)(\(a_i\leq 2^{32}-1\))

求区间异或和前\(k(k\leq2\times10^5)\)大之和

题解

考虑二分，找出第\(k\)大异或和是多少

将每个位置上的数变成前缀异或和\(s_i\)后，建出可持久化trie树，第\(i\)个版本由\(0,s_1,s_2,..,s_i\)组成，trie树上每个点维护这个点的子树中有几个数

二分\(x\)，判断是否有不超过\(k\)个异或和

发现这样时间复杂度为\(\Theta(n\times log^2 a)\)，略多

发现一般情况下在线段树上二分时都不是先二分出一个值再查询，而是在线段树上边走边计算

同理，本题就可以维护\(n\)个位置，即当前走到的第\(i（i\in[1,n]）\)个版本的trie树的位置

每次判断当前位放1会不会使大于等于当前值的异或和数量少于\(k\)，会就走\(a_i\)当前位异或0的方向，反之就走\(a_i\)当前位异或1的方向

算出第\(k\)大异或和后，直接在trie树中dfs找出大于（注意，不能找等于它的，不然会找多）它的异或和，计入答案，顺便记一共加了几个数

\((k-上一步加的数的个数)\)就是等于第\(k\)大异或和的异或和的个数，把这个计入答案

以上两步中走到的点只有大于第\(k\)大异或和的点和它们的父亲，只有\(\Theta(k\times log\space a)\)

总时间复杂度\(\Theta((n+k)\times log\space a)\)

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];~k;k=nxt[k])

#define maxn 500003

#define maxnd (maxn*33)

#define LL long long

#define int LL

using namespace std;

int read()

{

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)&&ch!='-')ch=getchar();

	if(ch=='-')f=-1,ch=getchar();

	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x*f;

}

void write(LL x)

{

	if(x==0){putchar('0'),putchar('\n');return;}

	int f=0;char ch[20];

	if(x<0)putchar('-'),x=-x;

	while(x)ch[++f]=x%10+'0',x/=10;

	while(f)putchar(ch[f--]);

	putchar('\n');

	return;

}

LL ans,a[maxn],num;;

const int len=31;

int n,k,ch[maxnd][2],val[maxnd],rt[maxn],cntnd,now[maxn],nownum;

void ext(int i)

{

	int u,nu=++cntnd;rt[i]=cntnd;

	if(i)u=rt[i-1];

	else u=0;

	dwn(j,len,0)

	{

		int d=(a[i]&(1ll<<j))>>j;

		if(u)val[nu]=val[u]+1,ch[nu][d^1]=ch[u][d^1],u=ch[u][d];

		else val[nu]=1;

		ch[nu][d]=++cntnd,nu=cntnd;

	}

	if(u)val[nu]=val[u]+1;

	else val[nu]=1;

}

void getans(int u,LL ai,LL xi)

{

	if(!ch[u][0]&&!ch[u][1]){if(((LL)ai^(LL)xi)>(LL)num){nownum+=val[u],ans=ans+(LL)((LL)ai^(LL)xi)*val[u];}return;}

	if(ch[u][0])getans(ch[u][0],ai,xi<<1);

	if(ch[u][1])getans(ch[u][1],ai,xi<<1|1);

	return;

}

#define dd(x,y) ((x&(1ll<<y))>>y)

signed main()

{

	n=read(),k=read();

	rep(i,1,n)a[i]=read()^a[i-1];

	rep(i,0,n)ext(i),now[i]=rt[i];

	dwn(i,len,0)

	{

		int tmp=0;

		rep(j,1,n)if(now[j]){tmp+=val[ch[now[j]][dd(a[j],i)^1ll]];}

		if(tmp+nownum>=k){rep(j,1,n)if(now[j])now[j]=ch[now[j]][dd(a[j],i)^1ll];num=num<<(1ll)|(1ll);}

		if(tmp+nownum<k){rep(j,1,n)if(now[j])now[j]=ch[now[j]][dd(a[j],i)];nownum+=tmp;num=num<<(1ll);}

	}

	nownum=0;

	rep(i,1,n)

	{

		int u=rt[i],vv=0;

		dwn(j,len,0)

		{

			int d=dd(a[i],j),e=dd(num,j);

			if(!e&&ch[u][d^1]){getans(ch[u][d^1],a[i],vv<<1|(d^1));}

			if(!ch[u][d^e])break;

			u=ch[u][d^e],vv=vv<<1|(d^e);

		}

	}

	ans+=(LL)num*(k-nownum);

	write(ans);

	return 0;

}

/*

3 2

1 2 3

*/

一些感想

sb猎人公会nmsl

巴特西

并不对劲的loj3048:p5283:[十二省联考]异或粽子

题目大意

题解

代码

一些感想

最新文章

热门文章