codeforces：B. Interesting Array【bitmask + 差分数组 + 前缀和记录是否含有1】

分析

注意差分数组[l, r]的话
一定是要去到r + 1的
所以一般开n + 1也是这个道理
这道题要让[l,r]区间的and都为q
那么对于q而言，如果它某一位是1，[l,r]所有数这一位必定是1
如果它某一位是0，[l,r]所有数这一位至少有一个0
那其实我们可以逐位考虑
对于每一位有1的q我们记录一个差分数组，简单+1，来表示l到r需要来一个1
然后根据差分数组，我们可以还原真实的值realNum（这个长度刚好n）
然后为了快速判断l到r至少有一个0 等价于 是否全都是1 我们考虑用前缀和
这个前缀和要开n + 1，还是用l 到 r + 1的形式
然后的话，如果realNum的某一位大于0，我们就记录下来ans[j] |= mask
否则我们就让preSum + 1，这就意味着，如果realNum某一位取了1的话前缀和其实是没变的
因此我们对于那些在这一位取0的q，我们如何判断它是否可以在[l, r]内存活呢，即最少有一个0呢，那他的前缀和必须变化
否则的话如果preSum[l] == preSum[r + 1]表示全1，直接G

Ac code

import sys
input = sys.stdin.readline

def solve():
    n, m = list(map(int,input().split()))
    intervals = []
    for _ in range(m):
        l, r, q = list(map(int,input().split()))
        intervals.append([l, r, q])


    ans = [0] * n

    # consider each bit
    for i in range(30):
        mask = 1 << i
        # diff array record which need to add
        diff = [0] * (n + 1)
        for l, r, q in intervals:
            # q is 1 on this bit
            #print(q, mask, q & mask)
            if q & mask == mask:
                diff[l - 1] += 1
                diff[r] -= 1
        #print(diff)
        realNum = [0] * n
        for j in range(n):
            realNum[j] = realNum[j - 1] + diff[j] if j >= 1 else diff[0]
        #print(realNum)

        # use preSum to judge if [l, r] contains all one
        preSum = [0] * (n + 1)
        cur = 0
        # update ans
        for j, v in enumerate(realNum):
            preSum[j + 1] = preSum[j]
            if v > 0:
                ans[j] |= mask
            else:
                # record 0
                preSum[j + 1] += 1
        #print(preSum)

        # if [l, r] has no 0, preSum[l] == preSum[r]
        for l, r, q in intervals:
            # conflict: all 1 but 0
            if q & mask == 0 and preSum[l - 1] == preSum[r]:
                print('NO')
                return

    print('YES')
    print(*ans)





if __name__ == '__main__':
    solve()
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59

总结

注意什么时候开n什么时候开n + 1
注意l和r + 1