BZOJ2741 FOTILE模拟赛L（分块+可持久化trie）

时间：2023-03-09 16:44:31
BZOJ2741 FOTILE模拟赛L（分块+可持久化trie）

　　显然做个前缀和之后变成询问区间内两个数异或最大值。

　　一种暴力做法是建好可持久化trie后直接枚举其中一个数查询，复杂度O(nmlogv)。

　　观察到数据范围很微妙。考虑瞎分块。

　　设f[i][j]为第i个块中的数和第j个数的异或最大值。显然建一棵可持久化trie就可以以O(n√nlogv)的复杂度搞出来。

　　有了这个后考虑怎么查询。对于完整的块内的数，给f再搞一个st表就可以了。而其他部分暴力枚举每个数，在可持久化trie上查询即可。

　　常数巨大。块大小改成√nlogn后在darkbzoj上差10ms就T了，bzoj上自然过不了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 12010

#define BLOCK 120

#define u(x,p) x>>p&1^1

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N],f[BLOCK][N][],root[N],L[BLOCK],R[BLOCK],pos[N],lg2[N],cnt=,lastans,block;

struct data{int ch[],s;

}tree[N<<];

void ins(int &k,int x,int p)

{

    tree[++cnt]=tree[k];k=cnt;tree[k].s++;

    if (p<) return;

    ins(tree[k].ch[x>>p&],x,p-);

}

int query(int l,int r,int x,int p)

{

    if (p<) return ;

    if (tree[tree[r].ch[u(x,p)]].s>tree[tree[l].ch[u(x,p)]].s)

    return query(tree[l].ch[u(x,p)],tree[r].ch[u(x,p)],x,p-)+(<<p);

    else query(tree[l].ch[x>>p&],tree[r].ch[x>>p&],x,p-);

}

void build()

{

    for (int i=;i<=n;i++)

    {

        root[i]=root[i-];

        ins(root[i],a[i],);

    }

}

int query(int i,int x,int y)

{

    return max(f[i][x][lg2[y-x+]],f[i][y-(<<lg2[y-x+])+][lg2[y-x+]]);

}

void divide()

{

    lg2[]=;

    for (int i=;i<=n;i++)

    {

        lg2[i]=lg2[i-];

        if ((<<lg2[i])<=i) lg2[i]++;

    }

    block=sqrt(n*lg2[n]);block=min(max(block,),n);

    for (int i=;i<=n/block;i++) L[i]=(i-)*block+,R[i]=i*block;

    if (n%block) L[n/block+]=(n/block)*block+,R[n/block+]=n,block=n/block+;

    else block=n/block;

    for (int i=;i<=block;i++)

        for (int j=L[i];j<=R[i];j++)

        pos[j]=i;

    for (int i=;i<=n;i++)

        for (int j=;j<=block;j++)

        f[j][i][]=query(root[L[j]-],root[R[j]],a[i],);

    for (int i=;i<=block;i++)

        for (int j=;j<;j++)

            for (int k=;k<=n;k++)

            f[i][k][j]=max(f[i][k][j-],f[i][min(n,k+(<<j-))][j-]);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2741.in","r",stdin);

    freopen("bzoj2741.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read()+,m=read();

    for (int i=;i<=n;i++) a[i]=a[i-]^read();

    build();

    divide();

    for (int i=;i<=m;i++)

    {

        int x=((unsigned int)read()+lastans)%(n-)+,y=((unsigned int)read()+lastans)%(n-)+;

        if (x>y) swap(x,y);y++;

        lastans=;

        for (int j=pos[x]+;j<pos[y];j++)

        lastans=max(lastans,query(j,x,y));

        if (pos[x]==pos[y])

        {

            for (int j=x;j<=y;j++)

            lastans=max(lastans,query(root[x-],root[y],a[j],));

        }

        else

        {

            for (int j=x;j<L[pos[x]+];j++)

            lastans=max(lastans,query(root[x-],root[y],a[j],));

            for (int j=y;j>R[pos[y]-];j--)

            lastans=max(lastans,query(root[x-],root[y],a[j],));

        }

        printf("%d\n",lastans);

    }

    return ;

}

相关文章