最大异或和(xor)
2024-08-29 12:03:56
最大异或和(xor)
题目描述
给定一个非负整数序列{a},初始长度为N。
有M个操作,有以下两种操作类型:
1、A x:添加操作,表示在序列末尾添加一个数x,序列的长度N+1。
2、Q l r x:询问操作,你需要找到一个位置p,满足l<=p<=r,使得:
a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。
输入
第一行包含两个整数N,M,含义如问题描述所示。
第二行包含N个非负整数,表示初始的序列A。
接下来M行,每行描述一个操作,格式如题面所述。
输出
假设询问操作有T个,则输出应该有T行,每行一个整数表示询问的答案。
样例输入
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
样例输出
4
5
6
提示
本题共有10个测试点,每个测试点10分。
对于测试点1-2,N,M<=5。
对于测试点3-7,N,M<=80000。
对于测试点8-10,N,M<=300000。
其中测试点1, 3, 5, 7, 9保证没有修改操作。
对于100%的数据,0<=a[i]<=10^7。
solution
考虑异或满足前缀相减。
答案=1~an~x的异或和异或1~i的异或和
前一部分是定值。
后一部分,我们对于每一个前缀都加进trie树,在trie上贪心即可。
建议写递归写法,注意边界。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,rt[],now,cnt;
struct trie{
int ch[],v;
}tr[*];
void ins(int k,int la,int v){
for(int i=;i>=;i--){
tr[k].v=tr[la].v+;
bool t=((v&(<<i))>);
tr[k].ch[!t]=tr[la].ch[!t];
tr[k].ch[t]=++cnt;
k=tr[k].ch[t],la=tr[la].ch[t];
}
tr[k].v=tr[la].v+;
}
int ask(int k,int la,int v){
int ans=;
for(int i=;i>=;i--){
bool t=((v&(<<i))>);t=(!t);
int s1=tr[k].ch[t],s2=tr[la].ch[t];
if(tr[s1].v>tr[s2].v){
ans+=(<<i);k=s1;la=s2;
}
else{
k=tr[k].ch[!t],la=tr[la].ch[!t];
}
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=,t;i<=n;i++){
scanf("%d",&t);
rt[i]=++cnt;
now^=t;ins(rt[i],rt[i-],now);
}
int rn=n;
for(int i=,t,a,b;i<=m;i++){
char c;scanf(" %c",&c);
if(c=='A'){
scanf("%d",&t);rn++;rt[rn]=++cnt;
now^=t;ins(rt[rn],rt[rn-],now);
}
else {
scanf("%d%d%d",&a,&b,&t);t^=now;
if(b==)printf("%d\n",t);
else {
//cout<<rt[b-1]<<' '<<rt[a-2]<<endl;
printf("%d\n",ask(rt[b-],a->?rt[a-]:,t));
}
}
}
return ;
}
最新文章
- 浅谈WEB跨域的实现(前端向)
- IntelliJ工程导入
- NOIP200806 火柴棒等式【B005】
- 1627. Join
- python多线程之semaphore(信号量)
- xcode7 打开工程错误 This Document requires xcode8.0 or later.
- [2015hdu多校联赛补题]hdu5303 Delicious Apples
- NSArray和NSMutableArray
- 【bzoj1053】反素数
- ASP.NET MVC4 学习系统三(控制器Controller)
- intelliJ IDEA中项目以jar包的形式导出
- IOS 从系统图库中获取 图片 并设置为头像
- RT-Thread学习笔记(1)
- shell脚本学习积累笔记(第一篇)
- C程序设计语言练习题1-3
- org.apache.ibatis.builder.BuilderException: Error parsing Mapper XML.问题思路
- Windows Server 2016-查询FSMO角色信息的三种方法
- java8 日期时间解析与转换
- Scala中的Implicit详解
- Get shell By Powershell