Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

可持久化01trie

类似主席树,在已有的基础上修改,空间O(nlog_2n)

Thu Summer Camp 2015异或运算

考虑到m比较大,对m建可持久化01trie然后最多同时查询n次(同一棵01trie)。

#pragma GCC optimize(2)
#include <cstdio>
using namespace std;
typedef long long LL;

const int Maxn=300005;

int ch[Maxn*35][2],sz[Maxn*35],Rt[Maxn],Cnt,Qx;
struct Node{int L,R,x;}Qr[1005];

void ins(int &Node,int pre,int L,int R,int x){
    Node=++Cnt,sz[Node]=sz[pre]+1;
    ch[Node][0]=ch[pre][0],ch[Node][1]=ch[pre][1];
    if(L>=R)return ;int Mid=L+(R-L)/2;
    if(x<=Mid)ins(ch[Node][0],ch[pre][0],L,Mid,x);
    else ins(ch[Node][1],ch[pre][1],Mid+1,R,x);
}

int Query(int dep,int k){
    if(dep<0)return 0;
    int tot=0;
    for(int i=1;i<=Qx;i++){
        int t=((Qr[i].x>>dep)&1)^1;
        tot+=sz[ch[Qr[i].R][t]]-sz[ch[Qr[i].L][t]];
    }
    if(tot>=k){
        for(int i=1;i<=Qx;i++){
            int t=((Qr[i].x>>dep)&1)^1;
            Qr[i].L=ch[Qr[i].L][t];
            Qr[i].R=ch[Qr[i].R][t];
        }return Query(dep-1,k)+(1<<dep);
    }
    else{
        for(int i=1;i<=Qx;i++){
            int t=(Qr[i].x>>dep)&1;
            Qr[i].L=ch[Qr[i].L][t];
            Qr[i].R=ch[Qr[i].R][t];
        }return Query(dep-1,k-tot);
    }
}
int N,M,A[1005],x,Q,al,ar,bl,br,k;
int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)scanf("%d",&A[i]);
    for(int i=1;i<=M;i++)scanf("%d",&x),ins(Rt[i],Rt[i-1],0,2147483647,x);
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++){
        scanf("%d%d%d%d%d",&al,&ar,&bl,&br,&k),Qx=0;
        for(int j=al;j<=ar;j++)Qr[++Qx]=(Node){Rt[bl-1],Rt[br],A[j]};
        printf("%d\n",Query(30,k));
    }
}

BZOJ3261最大异或和

板子题不多说。询问看起来很奇怪,我们将其转化为前缀异或和发现……

Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*