【bzoj4103】[Thu Summer Camp 2015]异或运算

2015.06.11 13:00 Thu | 24次阅读 | 旧日oi | 固定链接 | 源码

Description

给定长度为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<=1000,m<=300000

题解

考场上写的是可持久化trie+二分答案,时间复杂度31^2np,貌似会T,听AK的大爷说可以少一个log,一直想不懂,昨天看了大爷的代码,回家想了好久,今天来终于搞明白了,A掉了……
考虑询问是u=d的情况,此时我们的做法就是从高到低考虑每一位,如果用[l,r]这段区间的数异或上x这位上有不少于k个为1的,那么这位一定是1,接下来去找下一层,否则的话说明这位肯定是0,用k减去为1的个数,接着找下一层。
而多个数的方法和一个的其实一样,1000个数一起跑上述过程就行了。或许看代码更好理解一点。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 300005
int n,m,l,r,u,d,K,q,tot;
int x[1005],y[N],root[N];
int sum[N*50],ls[N*50],rs[N*50];
int s1[N],s2[N],s3[N],top;
void build(int &x,int t,int num,int d)
{
    sum[x=++tot]=sum[t]+1;
    if(d==0) return;d--;
    if(num&(1<<d)) ls[x]=ls[t],build(rs[x],rs[t],num,d);
    else rs[x]=rs[t],build(ls[x],ls[t],num,d);
}
int get_ans(int k,int d)
{
    if(d==0) return 0;d--;
    int ret=0;
    for(int tmp,i=1;i<=top;i++) 
    {
        tmp=(s3[i]&(1<<d))?1:0;
        ret+=tmp?sum[ls[s1[i]]]:sum[rs[s1[i]]];
        ret-=tmp?sum[ls[s2[i]]]:sum[rs[s2[i]]];
    }
    if(ret>=k)
    {
        for(int tmp,i=1;i<=top;i++) 
        {
            tmp=(s3[i]&(1<<d))?1:0;
            s1[i]=tmp?ls[s1[i]]:rs[s1[i]];
            s2[i]=tmp?ls[s2[i]]:rs[s2[i]];
        }
        return (1<<d)|get_ans(k,d);
    }
    else
    {
        for(int tmp,i=1;i<=top;i++) 
        {
            tmp=(s3[i]&(1<<d))?0:1;
            s1[i]=tmp?ls[s1[i]]:rs[s1[i]];
            s2[i]=tmp?ls[s2[i]]:rs[s2[i]];
        }
        return get_ans(k-ret,d);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);
    for(int i=1;i<=m;i++) 
    {
        scanf("%d",&y[i]);
        build(root[i],root[i-1],y[i],31);
    }
    cin>>q;
    while(q--)
    {
        scanf("%d%d%d%d%d",&u,&d,&l,&r,&K);
        top=0;
        for(int i=u;i<=d;i++)
        {
            s1[++top]=root[r];
            s2[top]=root[l-1];
            s3[top]=x[i];
        }
        printf("%d\n",get_ans(K,31));
    }
}```