题解 CF878D 【Magic Breeding】

AzusaCat · 2021-02-05 20:08:05 · 题解

给定 k 个长为 n 的数组，有 q 次操作，分别是新建一个数组，每一个元素为某两个已有数组的 \max/\min，或者查询某个数组上某个数是多少。k\leqslant 12，n,q\leqslant 10^5。

本题最有意思也是最难理解的是如何压缩状态量。首先显然每一个位置上的数是独立的，但是我们又不能直接独立考虑：因为这样你至少需要做 n 次，我们承受不了这个复杂度。我们发现由于一开始只有 k 个数组，那么最后的答案一定在这 k 个数组的元素中间，我们考虑定义一个和这 k 个数具体是什么无关的状态，这样就能起到压缩信息的作用。

我们把视角放到某一位上，这样每一次都生成的是一个元素 a_i，定义 f(i,s) 表示对于元素 i，无论 a_1\sim a_k 的值是多少，是否一定满足 a_i\geqslant \min_{j\in s}(a_j)。那么对于 i\in [1,k]，显然 f(i,s)=1 当且仅当 i\in s。

接下来我们考虑 \min/\max 操作，由于 \max(a_x,a_y)\geqslant \min_{j\in s}(a_j) 等价于 a_x\geqslant \min_{j\in s}(a_j)\lor a_y\geqslant \min_{j\in s}(a_j) ，所以如果是 \max 操作，有 f(i,s)=f(x,s)\lor f(y,s)。类似地我们也可以把取 \min 操作和 and 操作建立联系。

现在我们考虑询问，我们先给出流程，然后再证明它的正确性：我们把 a_1\sim a_k 从大到小排序，每一次向 s 中加入对应的下标 i，如果 f(x,s)=1，就输出 a_i。

下面来证明这样为什么是对的：

• 首先如果 f(x,s)=1 即无论 a 怎么取都成立，那么对于 a 给定的特殊情况也一定成立，也就是 ans\geqslant a_i。
• 如果 ans>a_i，也就是说对于我们加入过程的某个前缀 a_{b_k}\rightarrow a_{b_t}，假设该前缀对应的集合是 s'，则 f(x,s')=0，但是在这组 a 的情况下有 a_x\geqslant \min_{j\in s'}(a_j)=a_t。
  我们注意到如果存在一组 a' 使得 a'_x< \min_{j\in s'}(a'_j)，那展开 a'_x 的生成过程，一定有一步 \min 操作使得两个元素一个属于 s'，另一个不属于 s'，之后的操作都只在 s' 的补集中进行，而在当前的 a 下，s' 中的 a 是整个序列最大的一部分，所以这个 \min 操作也会使得 a_x 对应的下标变为 s' 补集中的元素，与条件不符。
  感性理解就是由于我们是从大到小枚举的，那么这个限制已经是所有限制中最紧的那个，如果最紧的限制满足，则其它的也一定满足。

所以这样一定有 ans=a_i。至于实现，我们发现取 \max/\min 可以使用 bitset 加速，所以总复杂度 O\left((k+\dfrac{n}{w})2^k\right) （n,q 同阶）。

代码：

#include<bits/stdc++.h>
using namespace std;
bitset<4096>f[100020];
int a[13][100005],b[100005][13],now;
bool cmp(int x,int y){return a[x][now]==a[y][now]?x>y:a[x][now]>a[y][now];}
int main()
{
    int n,q,k,cnt,op,x,y;
    scanf("%d%d%d",&n,&k,&q);cnt=k;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]),b[j][i]=i;
    for(int i=1;i<=n;i++)now=i,sort(b[i]+1,b[i]+k+1,cmp);
    for(int i=1;i<=k;i++)
        for(int j=0;j<(1<<k);j++)
            if(j&(1<<(i-1)))f[i][j]=1;
    while(q--)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)cnt++,f[cnt]=f[x]|f[y];
        else if(op==2)cnt++,f[cnt]=f[x]&f[y];
        else
            for(int i=1,t=0;i<=k;i++)
            {
                t|=(1<<(b[y][i]-1));
                if(f[x][t]){printf("%d\n",a[b[y][i]][y]);break;}
            }
    }
    return 0;
}