或

Posted on Edited on In

题目大意：有一天，xyz1048576 想到了一个模型：一个长度为 n 的非负整数序列 x，满足 m 个条件：第 i 个条件为 x[li] or x[li+1] or … or x[ri]=pi。他想知道是否存在一个序列满足条件，如果存在，他还要构造出一个这样的序列

考虑或的条件：有一为真即为真

也就是说，这么多数二进制拆分之后，每一位都为零的话，最后的那个p的那个位置才是零，只要有一位不是零，最后的p一定不是零

观察发现，如果p在二进制下有这一位的话，那么这期间所有数字只有一个为1即可，这启发我们对零来操作

差分？

然后就不太透彻了，等待_plxer大佬来补坑…

补坑：

用f数组来维护零的个数，sum数组来维护一的个数

在读入的时候，我们把p按照二进制位拆分，其中\(f[i][j]​\)表示第j位出现的零的个数

如果为零也就意味着这一位没有零，也就是说，对应到原序列里面这一位是有数的，所以num数组统计上他这一位的贡献

考虑不合法的判断：这个区间内出现了多于\(p_{二进制}\)的一的个数，或者少了

总之就是\(sum[r[i]-sum[l[i] - 1]\)不为零

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#define int long long
using namespace std;

const int N = 1e5 + 66;

int n, m;
int l[N], r[N], p[N], num[N]; 
int f[N][66], sum[N][66];

signed main()
{
    n = read(), m = read();

    for (int i = 1; i <= m; ++ i)
    {
        l[i] = read(), r[i] = read(), p[i] = read();
        for (int j = 0; j <= 30; ++ j)
        {
            if (! ((p[i] >> j) & 1))
            {
                ++ f[l[i]][j];
                -- f[r[i] + 1][j];
            }
        }
    }

    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 0; j <= 30; ++ j)
        {
            f[i][j] += f[i - 1][j];
            if (f[i][j] == 0) sum[i][j] += 1, num[i] += (1 << j);
            sum[i][j] += sum[i - 1][j];
        }
    }

    for (int i = 1; i <= m; ++ i)
        for (int j = 0; j <= 30; ++ j)
            if ((p[i] >> j) & 1)
                if (sum[r[i]][j] - sum[l[i] - 1][j] != 0) return puts("No"), 0;

    puts("Yes");
    for (int i = 1; i <= n; ++ i) put(num[i]);
    return 0;
}