您的位置: 首页  >  IT文章  >  CF878D题解

CF878D题解

分类: IT文章 • 2022-05-14 10:44:14

听说 WC2021 的 T2 和这题解法类似，于是就来做一发。

题意简述

初始有 (k) 个生物，编号分别为 (1,2,ldots,k) ，每个生物有 (n) 个属性，第 (i) 个生物的第 (j) 个属性为 (a_{i,j}) 。

现在有 (q) 次操作，形式如下：

  • 1 x y 表示将第 (x) 号生物的 (n) 个属性与第 (y) 号生物的 (n) 个属性分别取 (max) ，作为一个新生物的 (n) 个属性
  • 2 x y 表示将第 (x) 号生物的 (n) 个属性与第 (y) 号生物的 (n) 个属性分别取 (min) ，作为一个新生物的 (n) 个属性
  • 3 x y 表示询问第 (x) 号生物的第 (y) 个属性值是多少

新生物的编号依次顺延，即第 (t) 个 1/2 操作得到的新生物编号为 (t+k) 。

你需要对每一个 3 操作回答询问。

(1le n,qle 10^5,1le kle 12,1le a_{i,j}le 10^9) 。

算法分析

如果直接暴力做复杂度是 (mathcal O(nq)) 的，无法接受。

本题 (k) 很小，是本题的突破点。不难发现对于每一种属性，我们最后的答案一定来自于初始的 (k) 个生物的该属性的值，因此考虑枚举答案。 (min,max) 本身代表一种偏序关系，与其具体值无关，所有可能的情况共有 (2^k) 个。这说明 (n) 种属性中最多有 (2^k) 个本质不同的属性，考虑维护这 (2^k) 种状态。

我们定义一个状态 (S) 如下：若 (S) 的第 (i) 位为 (1) ，表示当前状态下 (a_ige 对应的答案)，否则 (a_i< 对应的答案)，此时当前节点的真实答案是否 (ge) 当前状态对应的答案。

那么我们不难发现 (1,2) 操作分别对应取 (mathrm{or}) 和取 (mathrm{and}) 。初始条件对于生物 (i) ，(f_i(S)=1 当且仅当 S_i=1) 。

对于一个查询，我们从大到小枚举所有的可能答案，不难求出这个答案对应的状态 (S) 。根据上述定义，当我们枚举到第一个状态对应值为 (1) 的答案时，此时答案即为真实答案。

发现可以用 bitset 优化，最终时间复杂度为 (mathcal Oleft(frac{q2^k+qk^2}{omega} ight)) 。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define LL long long
#define mod 1000000007
#define local
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
template <typename Tp> void read(Tp &x){
	int fh=1;char c=getchar();x=0;
	while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c&15);c=getchar();}x*=fh;
}
int n,m,mm,q;
int a[13][maxn];
bitset<4100>f[maxn];
int tmp[20],ttt;
void solve(int x,int y){
	ttt=0;
	for(int i=1;i<=m;++i)tmp[++ttt]=a[i][y];
	sort(tmp+1,tmp+ttt+1);
	ttt=unique(tmp+1,tmp+ttt+1)-tmp-1;// 这里做了离散化，在最优化问题中（即本题）不一定有必要
	int S;                            // 但在计数问题中（WC2021T2）必须离散化
	for(int i=ttt;i;--i){
		int xx=tmp[i];S=0;// 枚举答案xx，求出对应状态S
		for(int j=1;j<=m;++j){
			if(a[j][y]>=xx)S|=(1<<(j-1));
		}
		if(f[x][S]){//第一个值为1的状态对应答案即为真实答案
			printf("%d
",xx);
			break;
		}
	}
}
signed main(){
	read(n);read(m);read(q);
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			read(a[i][j]);
		}
		for(int S=0;S<(1<<m);++S){//初始状态求解
			if((S>>(i-1))&1)f[i][S]=1;
			else f[i][S]=0;
		}
	}
	mm=m;
	for(int i=1,op,x,y;i<=q;++i){
		read(op);read(x);read(y);
		if(op==1){//操作1对应 or
			++mm;
			f[mm]=(f[x]|f[y]);
		}
		if(op==2){//操作2对应 and
			++mm;
			f[mm]=(f[x]&f[y]);
		}
		if(op==3){
			solve(x,y);
		}
	}
	return 0;
}

相关推荐