简要题意
对于一个数组 \(a\)，给定 \(Q\) 个限制条件，每个条件给出 \(i,j,x\) 使得 \(a_i|a_j=x\)。
构造数组使其字典序最小。
Solution
以下 \(ans_i\) 表示最后我们构造出来的答案数组。
考虑一个最宽松的限制条件，我们有一个 \(b\) 数组，在最开始，\(b\) 在二进制意义下全是 \(1\)。
对于每个条件，我们令 \(b_i=b_i\&x,b_j=b_j\&x\)。
显然，\(b\) 数组是答案最宽松的条件，即 \(ans_i\subseteq b_i\)。
也就是说，若一定存在解，则 \(b_i\) 必然是一组合法解。
现在要求字典序最小，我们从前往后构造答案。
考虑当前构造位 \(i\)。
为了让字典序最小，对于一个限制 \(\{a_i|a_j=x,(i<j)\}\)，我们应尽可能的让 \(ans_j\) 完成要求，\(ans_j\) 能完成的部分即为 \(x\&b_j\)。
剩余的部分，即 \((x\) \(^\) \((x\&b_j))\)，则不得不让 \(ans_i\) 来完成，于是 \(ans_i\) 必须或上这一部分。
但是注意，\(ans_j\) 并不是一定要完成 \(x\&b_j\)。
因为 \(ans_i\) 也有可能在其他条件的迫害下不得不完成了一部分 \(x\)。
于是我们对于 \(\{a_i|a_j=x,(i>j)\}\)，再让 \(ans_i|=(x\&ans_i)\) 来完成剩余的限制即可。
由于每一步都是必要的，所以他是最小的。
至于 \(\{a_i|a_j=x,(i=j)\}\)，则 \(ans_i=x\) 是必然的。
复杂度 \(O(n+q)\)。
#include<bits/stdc++.h>
#include<vector>
const int N=200010;
int a[N],b[N],ans[N];
struct node{
int to,val;
};
std::vector<node>p[N];
signed main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)a[i]=(1<<30)-1;
int x,y,z;
for(int i=1;i<=q;i++){
scanf("%d%d%d",&x,&y,&z);
a[x]=z&a[x],a[y]=z&a[y];
p[x].push_back(node{y,z}),p[y].push_back(node{x,z});
}
for(int i=1;i<=n;i++){
for(node j:p[i]){
if(i==j.to)ans[i]|=j.val;
else if(j.to>=i){
ans[i]|=((j.val^(j.val&a[j.to]))&a[i]);
}
else {
ans[i]|=((j.val^(j.val&ans[j.to]))&a[i]);
}
}
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}