bzoj 2741持続性trie

まず、siを前のi個数のxor和とすると、質問区間[i,j]のxor和は、si-1^sjに相当し、この問題の質問に対しては処理処siを処理することができ、その後、質問[l,r]に対して、区間[l-1,r]の中で2つの数を探してこの2つの数のxor値を最大にすることを表すことができる.区間の中で1つの数を探してxorの1つの既知の数の値が最大になるように私たちは持続可能なtrieで完成することができます(疑問があればステップを移動してくださいhttp://www.cnblogs.com/BLADEVIL/p/3669219.html)は、質問query(l,r,x)がxと区間[l,r]の数を表すxor値の最大値とする.では、このn個の数をsqrt(n)個のブロックに分けることができ、head[i]をi番目のブロックの最初の要素とし、w[i][j]をi番目のブロックの最初の要素からj番目の数までの区間で、任意に2個の数を探すxor値が最大とすると、遷移方程式w[i][j]=max(w[i][j],w[i][j-1]+query(head[i],j-1,a[j])が得られやすい.この時間的複雑さはo(sqrt(n)*n*logn)であり,次いで質問[l,r]に対してlの後の最初のブロックをxブロックとし,ans=max(w[x][r],max(l,r,a[j]),j∈[l,head[x]−1]とする.
備考:最初はa[i]が32767を超えないと思っていましたが、後に2147483647のように見えました.それからtrieの深さを変えた後、いつもREを発見しました.私が書いたtrieはまず空の木を建ててからノードを挿入したので、31階の満二叉木はもちろん建てられませんでした.それでは直接挿入に変更しましたが、発見はWAで、前回の答えは2147483647より少し小さいかもしれませんが、今回の質問の値を加えるとintを超えるので、まず強制的にlong longに変えてから%nにすればいいです.
最初はREがメモリの問題だと思っていたので、ずいぶん大きくなって、直すのがおっくうだったので、そうしましょう.

/**************************************************************

    Problem: 2741

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:8148 ms

    Memory:41680 kb

****************************************************************/

 

//By BLADEVIL

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 20000

#define maxm 400

 

using namespace std;

 

struct tree {

    int son[2];

    int cnt;

    tree() {

        memset(son,0,sizeof son);

        cnt=0;

    }

}t[40*maxn];

 

struct rec {

    int key,num,rot;

    rec() {

        key=num=rot=0;

    }

}a[maxn];

 

int n,m,len,sum,tot;

int w[maxm][maxn],head[maxm];

 

void insert(int &x,int rot,int y,int dep) {

    if (!x) x=++tot;

    if (dep==-1) {

        t[x].cnt=t[rot].cnt+1;

        return ;

    }

    if (y&(1<<dep)) {

        insert(t[x].son[1],t[rot].son[1],y,dep-1); 

        t[x].son[0]=t[rot].son[0];

    } else {

        insert(t[x].son[0],t[rot].son[0],y,dep-1);

        t[x].son[1]=t[rot].son[1];

    }

    t[x].cnt=t[rot].cnt+1;

}

 

int query(int lx,int rx,int y,int dep) {

    if (dep==-1) return 0;

    if (y&(1<<dep)) {

        if (t[t[rx].son[0]].cnt-t[t[lx].son[0]].cnt) 

            return (1<<dep)+query(t[lx].son[0],t[rx].son[0],y,dep-1); else

            return query(t[lx].son[1],t[rx].son[1],y,dep-1);

    } else {

        if (t[t[rx].son[1]].cnt-t[t[lx].son[1]].cnt)

            return (1<<dep)+query(t[lx].son[1],t[rx].son[1],y,dep-1); else

            return query(t[lx].son[0],t[rx].son[0],y,dep-1);

    }

}

 

int main() {

    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++) scanf("%d",&a[i].key);

    for (int i=1;i<=n;i++) a[i].key^=a[i-1].key;

    sum=len=sqrt(n); if (len*len<n) len++,sum=(n+len-1)/len;

    //printf("%d %d
",len,sum);

    for (int i=1;i<=n;i++) if (!head[a[i].num=(i+len-1)/len]) head[a[i].num]=i; head[sum+1]=n+1;

    //for (int i=1;i<=n;i++) printf("%d ",a[i].key); printf("
");

    //for (int i=1;i<=sum;i++) printf("%d ",head[i]);

    for (int i=1;i<=n;i++) insert(a[i].rot,a[i-1].rot,a[i].key,30);

    for (int i=1;i<=sum;i++)

        for (int j=head[i];j<=n;j++) 

            w[i][j]=max(w[i][j-1],query(a[head[i]-1].rot,a[j].rot,a[j].key,30));

    /*

    for (int i=1;i<=sum;i++) {

        for (int j=1;j<=n;j++) printf("%d ",w[i][j]);

        printf("
");

    }

    */

    int ans=0;

    while (m--) {

        int l,r; scanf("%d%d",&l,&r); int x,y;

        x=((long long)l+ans)%n+1; y=((long long)r+ans)%n+1;

        l=min(x,y); r=max(x,y); ans=0; l--;

        if (a[l].num==a[r].num) {

            for (int i=l;i<=r;i++) ans=max(ans,query(a[l-1].rot,a[r].rot,a[i].key,30));

        } else {

            ans=w[a[l].num+1][r]; //printf("%d %d %d
",ans,a[l].num+1,r); 

            for (int i=l;i<=head[a[l].num+1]-1;i++) ans=max(ans,query(a[l-1].rot,a[r].rot,a[i].key,30));

        }

        printf("%d
",ans);

    }

    return 0;

}