P5795 [THUSC2015] 异或运算

题目描述

给定长度为 \(n\) 的数列 \(X={x_1,x_2,...,x_n}\) 和长度为 \(m\) 的数列 \(Y={y_1,y_2,...,y_m}\)，令矩阵 \(A\) 中第 \(i\) 行第 \(j\) 列的值 \(A_{i,j}=x_i\ \operatorname{xor}\ y_j\)，每次询问给定矩形区域 \(i∈[u,d],j∈[l,r]\)，找出第 \(k\) 大的 \(A_{i,j}\)。

对于 \(100\%\) 的数据

• \(0\leq X_i,Y_j<2^{31}\),
• \(1\leq u\leq d\leq n\leq 1000\),
• \(1\leq l\leq r\leq m\leq 300000\),
• \(1\leq k\leq (d-u+1)\times (r-l+1)\), \(1\leq p\leq 500\)。

Solution：

我们发现数据范围十分的有意思，n,m及其的不对称，并且我们唯一能接受的多项式复杂度是 $ O(n \cdot q \cdot logm) $

我们维护一个可持久化 0/1 Trie，用来存每个b的值。然后对于每个查询，从31位开始往0位扫，在这个矩形中统计一下当前位 \(ig\) 为1的有多少，而统计的方式自然就是遍历 \(i \in [u,d]\) 查询对于每个 \(x_i\) ,假设它的第 \(ig\) 位是 \(now\)。我们需要统计在 $ -t[l-1]+t[r]$ 这颗树上，第 \(ig\) 位是 \(!now\) 的节点数

如果$ cnt \ge k$，说明这位必须取1，且将所有的主席树节点访问到 \(!now\) 如果不取的话那么排名至少为 \(cnt+1\) 。

如果 $cnt < k $,说明这位不能取1,但是在当前位 \(ig\) 有 \(cnt\) 个比 \(ans\) 大的数，所以在我们的主席树进入 \(now\) 统计答案之前要先将 \(k-=cnt\)

然后这题就做完了

Code：

#include<bits/stdc++.h>
const int N=3e5+5;
using namespace std;
int a[N],b[N];
struct Trie{
    int cnt;
    int rt[N],L[N],R[N];
    struct Tree{
        int ch[2],cnt;
    }t[N*50];
    inline void insert(int &x,int y,int val,int len)
    {
        t[x=++cnt]=t[y];
        t[x].cnt++;
        if(len<0)return ;
        int now=(val>>len)&1;
        insert(t[x].ch[now],t[y].ch[now],val,len-1);
    }
    int query(int x,int y,int l,int r,int k)
    {
        int res=0;
        for(int i=x;i<=y;i++)
        {
            L[i]=rt[l-1];
            R[i]=rt[r];
        }
        for(int ig=31;ig>=0;ig--)
        {
            int cnt=0;
            for(int i=x;i<=y;i++)
            {
                int now=(a[i]>>ig)&1;
                cnt+= -t[t[L[i]].ch[!now]].cnt+t[t[R[i]].ch[!now]].cnt;
            }
            if(cnt>=k)//这一位取1至少有 k 个 （这一位如果不取1，排名至少是cnt+1）
            {
                res|=(1<<ig);//这位要取1
                for(int i=x;i<=y;i++)
                {
                    int now=(a[i]>>ig)&1;
                    L[i]=t[L[i]].ch[!now];
                    R[i]=t[R[i]].ch[!now];
                }
            }
            else //这位不取1
            {
                k-=cnt;
                for(int i=x;i<=y;i++)
                {
                    int now=(a[i]>>ig)&1;
                    L[i]=t[L[i]].ch[now];
                    R[i]=t[R[i]].ch[now];
                }
            }
        }
        return res;
    }

}T;
int n,m,q;
void work()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        T.insert(T.rt[i],T.rt[i-1],b[i],31);
    }
    cin>>q;
    for(int i=1,x,y,l,r,k;i<=q;i++)
    {
        scanf("%d%d%d%d%d",&x,&y,&l,&r,&k);
        int ans=T.query(x,y,l,r,k);
        printf("%d\n",ans);
    }
}
int main()
{
    //freopen("P5795_1.in","r",stdin);freopen("P5795.out","w",stdout);
    work();
    return 0;
}