Loading...

洛谷P4735 最大异或和

check评论:0 条 remove_red_eye浏览量:277 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-04-05

题目很简单qaq,因为异或有可减性,所以
$⨁\limits_{i=l}^r a_i=⨁\limits_{i=1}^ra_i\ xor⨁\limits_{i=1}^{l-1}a_i$

所以我们统计一个异或前缀和,问题就转化为了给定一个数,求一个区间内的另外一个数和它异或的最大值

显然可持久化$trie$就可以了

要注意的是,$[l,r]$区间的前缀在$[l-1,r-1]$,又因为要差分,所以查询的时候是$[l-2,r-1]$,这样要特判很麻烦,我们考虑下标整体向后一位即可

#include <bits/stdc++.h>
using namespace std;
#define maxn 600010
int ch[maxn<<5][2],siz[maxn<<5],t[maxn],n,m,p[maxn],cnt;
void ins(int &rt,int pre,int x)
{
    rt=++cnt;
    int prt=rt;
    siz[prt]=siz[pre]+1;
    for(int i=24;i>=0;i--)
    {
        int qaq=(x>>i)&1;
        ch[prt][qaq]=++cnt,ch[prt][qaq^1]=ch[pre][qaq^1];
        prt=ch[prt][qaq],pre=ch[pre][qaq];
        siz[prt]=siz[pre]+1;
    }
}
int query(int lf,int rg,int x)
{
    int ans=0;
    for(int i=24;i>=0;i--)
    {
        int qaq=(x>>i)&1;
        if(siz[ch[rg][qaq^1]]-siz[ch[lf][qaq^1]])
        {
            ans|=(1<<i),rg=ch[rg][qaq^1],lf=ch[lf][qaq^1];
        }
        else
        {
            rg=ch[rg][qaq],lf=ch[lf][qaq];
        }
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    n++;
    ins(t[1],t[0],0); 
    for(int i=2;i<=n+1;i++)
    {
        int x;
        scanf("%d",&x);
        p[i]=p[i-1]^x;
        ins(t[i],t[i-1],p[i]);
    }
    char opt[5];
    for(int i=1,l,r,x;i<=m;i++)
    {
        scanf("%s%d",opt,&l);
        if(opt[0]=='A')
        {
            n++;
            p[n]=p[n-1]^l;
            ins(t[n],t[n-1],p[n]);
        }
        else
        {
            scanf("%d%d",&r,&x);
            if(l==0)
            {
                printf("%d\n",query(0,t[r],x^p[n]));
                continue;
            }
            printf("%d\n",query(t[l-1],t[r],x^p[n]));
        }
    }
}

SCOI 2019 游记 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名