A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4260 Codechef Rebxor
发表于: | 分类: Oi | 评论:0 | 阅读:50

题目大意 :给定了一个序列$a{i}$,求下面这个式子的最大值
$$A(l_1)\quad xor A(l_1+1) \quad xor ... xor \quad A(r_1) + A(l_2)\quad xor A(l_2+1) \quad xor ... xor \quad (Ar_2) $$
$xor$是按位异或,上面的式子中$1\le l_1 \le r_1 < l_2 \le r_2 \le n$

这玩意还是挺简单的
我们可以维护这么几个东西,首先维护出一个可持久化的$Trie$,把这些数插进去
然后维护一个一定把这个当为区间右端点最大值,再维护一个一定把这个值作为区间左端点的最大值
这玩意扫一遍就能求出来了
然后显然对于一个左端点,我需要找到一个严格小于的右端点,这个右端点才是合法的
所以我们把右端点的得到的值插到一个树状数组里面求一个前缀的最大值就行了
每次直接查询即可 ,明明就是一个$O(nlog^2(n))$的算法,不知道为什么慢的像*一样

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 400000+5;
const int Maxm = N * 40;
#define lowbit(x) ((x)&(-x))
using namespace std;

int tr[Maxm],ch[Maxm][2],root[N],sz;

void change(int x,int y,int val)
{
    for(int i=30;~i;--i)
    {
        int tmp = (1<<i) & val ? 1 : 0;
        ch[y][0] = ch[x][0], ch[y][1] = ch[x][1] , tr[y] = tr[x] + 1;
        x = ch[x][tmp], y = (ch[y][tmp] = ++sz);
    }
    tr[y] =tr[x] + 1;
}

int ask(int L,int R,int val)
{
    int ans = 0;
    for(int i=30;~i;--i)
    {
        int tmp = (1<<i) & val ? 0 : 1;
        if(tr[ch[R][tmp]] - tr[ch[L][tmp]]) ans += (1<<i);
        else tmp ^= 1; R = ch[R][tmp], L = ch[L][tmp];
    }
    return ans;
}

int be[N],ed[N];
int a[N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int tmp[N];

void updata(int x,int val)
{
    while(x < N)
    {
        tmp[x] = max(tmp[x],val);
        x += lowbit(x);
    }
}

int ask(int x)
{
    int ans = 0;
    while(x)
    {
        ans = max(ans,tmp[x]);
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    int n= read();
    for(int i=1;i<=n;++i) a[i] = read() ^ a[i-1];
    for(int i=1;i<=n;++i) change(root[i-1],root[i] = ++sz,a[i]);
    int tmp = root[n]; 
    change(tmp,root[n] = ++sz,0);
    for(int i=1;i<=n;++i)
    {
        be[i] = ask(root[0],root[i],a[i]);
        be[i] = max(be[i],a[i]);
        ed[i] = ask(root[i-1],root[n],a[i-1]);
    }
    for(int i=1;i<=n;++i) updata(i,be[i]);
    int ans = 0;
    for(int i=n;i>1;--i)  
        ans = max(ans,ed[i]+ask(i-1));
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP