CF482B Interesting Array Solution-CSDN博客

本文链接：https://blog.csdn.net/sblsf/article/details/148027728

Description

给定 $m$ 个三元组 $(l, r, v)$ .
判断是否存在序列 $a=(a_1,a_2,\cdots,a_n)$ ，满足：

对每个三元组 $(l, r, v)$ ，都有 $\mathop{\operatorname{and}}\limits_{i=l}^r a_i=v$ .

若存在，则给出任意一种方案.

Limitations

$1\le n,m\le 10^5$
$1\le l\le r\le n$
$0\le v<2^{30}$

Solution

位运算对每位独立，可以拆位.
考虑 $v$ 的第 $i$ 位，有：

若该位为 $1$ ，则 $a_l\sim a_r$ 的第 $i$ 位都为 $1$ .
若该位为 $0$ ，则 $a_l\sim a_r$ 的第 $i$ 位中至少有一个为 $0$ .

第二个条件不好构造，我们可以只考虑第一个条件，构造完后逐个进行验证.
显然将 $a_l\sim a_r$ 第 $i$ 位赋值为 $1$ 相当于 $a_l\sim a_r$ 都 $\operatorname{or}$ 上 $2^i$ .
那么实现时不用拆位，直接用线段树维护 $a$ ，支持区间 $\operatorname{or}$ 上 $x$ ，求区间 $\operatorname{and}$ 和即可.

Code

$2.60\text{KB},0.27\text{s},700\text{KB}\;\texttt{(C++20, gcc 13, 64 bit)}$

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

constexpr int V = (1 << 30) - 1;
namespace seg_tree {
	struct Node {
		int l, r, andd, tag;
	};
	
	inline int ls(int u) { return 2 * u + 1; }
	inline int rs(int u) { return 2 * u + 2; }
	
	struct SegTree {
		vector<Node> tr;
		
		inline SegTree() {}
		inline SegTree(int _n) : tr(_n << 1) { build(0, 0, _n - 1); }
		
		inline void pushup(int u, int mid) {
			tr[u].andd = tr[ls(mid)].andd & tr[rs(mid)].andd;
		}
		
		inline void apply(int u, int tag) {
			tr[u].andd |= tag;
			tr[u].tag |= tag;
		}
		
		inline void pushdown(int u, int mid) {
			if (tr[u].tag) {
				apply(ls(mid), tr[u].tag);
				apply(rs(mid), tr[u].tag);
				tr[u].tag = 0;
			}
		}
		
		void build(int u, int l, int r) {
			tr[u].l = l, tr[u].r = r;
			if (l == r) return;
			const int mid = (l + r) >> 1;
			build(ls(mid), l, mid), build(rs(mid), mid + 1, r);
		}
		
		void update(int u, int l, int r, int k) {
			if (l <= tr[u].l && tr[u].r <= r) return apply(u, k);
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (l <= mid) update(ls(mid), l, r, k);
			if (r > mid) update(rs(mid), l, r, k);
			pushup(u, mid);
		}
		
		int query(int u, int l, int r) {
			if (l <= tr[u].l && tr[u].r <= r) return tr[u].andd;
			const int mid = (tr[u].l + tr[u].r) >> 1;
			int res = V;
			pushdown(u, mid);
			if (l <= mid) res &= query(ls(mid), l, r);
			if (r > mid) res &= query(rs(mid), l, r);
			return res;
		}
		
		inline void range_or(int l, int r, int k) { update(0, l, r, k); }
		inline int range_andsum(int l, int r) { return query(0, l, r); }
	};
}
using seg_tree::SegTree;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	SegTree sgt(n);
	vector<int> l(m), r(m), x(m);
	for (int i = 0; i < m; i++) {
		cin >> l[i] >> r[i] >> x[i];
		l[i]--, r[i]--;
		sgt.range_or(l[i], r[i], x[i]);
	}
	
	for (int i = 0; i < m; i++)
	    if (sgt.range_andsum(l[i], r[i]) != x[i]) {
	    	cout << "NO\n";
	    	return 0;
	    }
	
	cout << "YES\n";
	for (int i = 0; i < n; i++) cout << sgt.range_andsum(i, i) << ' ';
	
	return 0;
}