bzoj4103 [Thu Summer Camp 2015]异或运算（可持久化trie）

内存限制：512 MiB 时间限制：1000 ms

题目描述

给定长度为n的数列X={x1,x2,...,xn}和长度为m的数列Y={y1,y2,...,ym}，令矩阵A中第i行第j列的值Aij=xi xor yj，每次询问给定矩形区域i∈[u,d],j∈[l,r]，找出第k大的Aij。

输入格式

第一行包含两个正整数n,m，分别表示两个数列的长度

第二行包含n个非负整数xi

第三行包含m个非负整数yj

第四行包含一个正整数p，表示询问次数

随后p行，每行均包含5个正整数，用来描述一次询问，每行包含五个正整数u,d,l,r,k，含义如题意所述。

输出格式

共p行，每行包含一个非负整数，表示此次询问的答案。

样例

样例输入

样例输出

数据范围与提示

对于100%的数据，0<=Xi,Yj<2^31,

1<=u<=d<=n<=1000,

1<=l<=r<=m<=300000,

1<=k<=(d-u+1)*(r-l+1),

1<=p<=500

区间有关异或的问题，都可以用trie树解决

本题的$m$，显然用可持久化trie维护

对于每个询问，考虑枚举$[u,d]$，在区间$[l,r]$上的trie中查询。

每次从答案的最高位开始，判断区间内该位为$1$的A_{i,j}的个数，如果$>=k$则答案的该位则为$1$。

对每个枚举的$i(u<=i<=d)$，维护$L,R$两个指针表示当前询问的区间，每次判断完更新

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int read(){

    char c=getchar(); int x=;

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') x=x*+c-,c=getchar();

    return x;

}

#define N 1005

#define M 300005

int n,m,a[N],L[N],R[N];

int u,rt[M],nx[M*][],sum[M*];

void ins(int o,int p,int d,int v){

    int k=(v>>d)&;

    nx[o][!k]=nx[p][!k];

    sum[nx[o][k]=++u]=sum[nx[p][k]]+;

    if(d) ins(nx[o][k],nx[p][k],d-,v);

}

int ask(int l,int r,int k,int d){

    if(d<) return ;

    int tt=,b=<<d;

    for(int i=l;i<=r;++i){

        if(a[i]&b) tt+=sum[nx[R[i]][]]-sum[nx[L[i]][]];

        else tt+=sum[nx[R[i]][]]-sum[nx[L[i]][]];

    }

    if(tt>=k){//该位为1的个数>=k，说明答案的该位为1

        for(int i=l;i<=r;++i){

            if(a[i]&b) L[i]=nx[L[i]][],R[i]=nx[R[i]][];

            else L[i]=nx[L[i]][],R[i]=nx[R[i]][];

        }

        return ask(l,r,k,d-)|b;

    }else{

        for(int i=l;i<=r;++i){

            if(a[i]&b) L[i]=nx[L[i]][],R[i]=nx[R[i]][];

            else L[i]=nx[L[i]][],R[i]=nx[R[i]][];

        }

        return ask(l,r,k-tt,d-);

    }

}

int main(){

    n=read(); m=read();

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

    for(int i=;i<=m;++i) rt[i]=++u,ins(rt[i],rt[i-],,read());

    for(int Q=read(),l1,l2,r1,r2,k;Q;--Q){

        l1=read(),l2=read(),r1=read(),r2=read(),k=read();

        for(int i=l1;i<=l2;++i) L[i]=rt[r1-],R[i]=rt[r2];

        printf("%d\n",ask(l1,l2,k,));

    }return ;

}

Trie