JZTXT

CF482B Interesting Array Solution

发布时间 2023-05-27 15:11:40作者: zhengxy

构造一个数组，给出了 \(m\) 条限制，要求 \([l, r]\) 内的数按位与的值为 \(x\)。

按位考虑，对于 \(x\) 的每个位，\([l, r]\) 的数在这一个位下都应该是 \(1\)， 否则就无法满足它们的与的值为 \(x\)。

构造出来的数组并不一定是满足条件的。所以在所有的操作完后还要验证构造的数组是否满足了条件，需要求一个区间的数的按位与。如果满足条件就直接输出，否则就只能输出 NO 了。

于是就可以线段树了，修改是 \([l, r]\) 的数全部都或一个 \(x\)，询问就是 \([l, r]\) 的数的按位与。

// Code by 落花月朦胧. 
#include <bits/stdc++.h>

using i64 = long long;
constexpr int iinf = 1E9;
constexpr i64 linf = 1E18;

// 克鲁鲁 克鲁鲁 克鲁鲁 克鲁鲁 克鲁鲁 克鲁鲁 克鲁鲁 克鲁鲁

constexpr int N = 1E5 + 10;
constexpr int P = 998244353;

i64 power(i64 a, i64 b, i64 p) {
    i64 res = 1;
    for (; b; b >>= 1, a = (a * a) % p)
        if (b & 1) res = (res * a) % p;
    return res % p;
}

struct node {
    int l, r;
    int add, val;
} t[N << 2];

#define l(x) t[x].l
#define r(x) t[x].r
#define val(x) t[x].val
#define add(x) t[x].add

void build(int l, int r, int p) {
    l(p) = l;
    r(p) = r;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1 | 1);
}

void pushup(int p) {
    val(p) = val(p << 1) & val(p << 1 | 1);
}

void pushdown(int p) {
    if (add(p)) {
        add(p << 1) |= add(p);
        add(p << 1 | 1) |= add(p);
        val(p << 1) |= add(p);
        val(p << 1 | 1) |= add(p);

        add(p) = 0;
    }
}

void update(int L, int R, int x, int p) {
    if (l(p) >= L && r(p) <= R) {
        val(p) |= x;
        add(p) |= x;
        return;
    }
    pushdown(p);
    int mid = (l(p) + r(p)) / 2;
    if (mid >= L) {
        update(L, R, x, p << 1);
    }
    if (mid < R) {
        update(L, R, x, p << 1 | 1);
    }
    pushup(p);
}

int ask(int L, int R, int p) {
    if (l(p) >= L && r(p) <= R) {
        return val(p);
    }
    pushdown(p);
    int mid = (l(p) + r(p)) / 2;
    int ans = (1 << 30) - 1;
    if (mid >= L) {
        ans &= ask(L, R, p << 1);
    }
    if (mid < R) {
        ans &= ask(L, R, p << 1 | 1);
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    build(1, n, 1);
    std::vector<int> L(m), R(m), x(m);
    for (int i = 0; i < m; i++) {
        std::cin >> L[i] >> R[i] >> x[i];

        update(L[i], R[i], x[i], 1);
    }
    for (int i = 0; i < m; i++) {
        if (ask(L[i], R[i], 1) != x[i]) {
            std::cout << "NO\n";
            return 0;
        }
    }

    std::cout << "YES\n";
    for (int i = 1; i <= n; i++) {
        std::cout << ask(i, i, 1) << ' ';
    }

    return 0;
}