BZOJ3261 最大异或和

题面

给定一个非负整数序列$a$,初始长度为$n$。

有 $m$ 个操作,有以下两种操作类型:

  1. A x:添加操作,表示在序列末尾添加一个数 $x$,序列的长度 $n+1$。
  2. Q l r x:询问操作,你需要找到一个位置 $p$,满足$l \leq p \leq r$,使得: $a[p] \oplus a[p+1] \oplus \ldots \oplus a[N] \oplus x$ 最大,输出最大是多少。

思路

小清新可持久化trie树题。

考虑维护后缀和然后再用可持久化trie树查询,发现1操作不大好做,因为会影响前面所有的后缀和。那么考虑异或性质,对2操作进行变形。设$sum[N]=a[1] \oplus a[2] \oplus \ldots \oplus a[N]$我们发现$a[p] \oplus a[p+1] \oplus \ldots \oplus a[N] \oplus x$=$sum[N]\oplus sum[N]\oplus a[p] \oplus a[p+1] \oplus \ldots \oplus a[N] \oplus x$发现后面$p+1$到$N$那一段$a$全被异或掉了,就可以变形为$sum[p-1]$,那么式子变化为$sum[p-1]\oplus sum[N] \oplus x$,注意询问时$l-1$,$r-1$然后考虑下边界特判就好了。

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x)
{
	int f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
void print(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9){print(x/10);}
    putchar(x%10+'0');
}
int N,M,sum=0,rt[4*300005],cnt=0;
struct trie{int ls,rs,size;}tree[80*300005]; 
inline void insert(int pre,int &root,int i,int x)
{
	root=++cnt;
	tree[root]=tree[pre];
	tree[root].size++;
	if (i<0) return;
	if ((x>>i)&1) insert(tree[pre].rs,tree[root].rs,i-1,x);
	else insert(tree[pre].ls,tree[root].ls,i-1,x);
}
inline int query(int pre,int root,int i,int x)
{	
	if (pre==root) return x;
	if (i<0) return 0;
	if ((x>>i)&1)
	{
		if (tree[tree[root].ls].size-tree[tree[pre].ls].size>=1) return query(tree[pre].ls,tree[root].ls,i-1,x)+(1<<i);
		else return query(tree[pre].rs,tree[root].rs,i-1,x);
	}
	else 
	{
		if (tree[tree[root].rs].size-tree[tree[pre].rs].size>=1) return query(tree[pre].rs,tree[root].rs,i-1,x)+(1<<i);
		else return query(tree[pre].ls,tree[root].ls,i-1,x);
	}
}
int main()
{
	read(N),read(M);
	for (int a,i=1;i<=N;i++) read(a),sum^=a,insert(rt[i-1],rt[i],30,sum);
	for (int l,r,x,i=1;i<=M;i++)
	{
		char s[10];
		scanf("%s",s+1);
		if (s[1]=='A') read(l),sum^=l,insert(rt[N],rt[N+1],30,sum),N++;
		else
		{
			read(l),read(r),read(x);
			l--,r--;
			print(query(rt[max(l-1,0)],rt[r],30,x^sum));
			putchar('\n');
		}
	}
	return 0;	
}  
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇