Codeforces 796F

发表于 |

题目

有一个长度为N的数列，每个数不超过$10^9$，顺序给出$M$个操作以及对应操作的结果。要求还原出那个数列，若有多个数列满足条件，输出每个数按位或的值最大的那个数列。原数列可能不存在。

操作有2种：
第一种：$l,r,x$。代表原数列下标在$[l,r]$范围内的最大的数为$x$。题目保证每个$x$都不相同。
第二种：$k,d$。代表将原数列中第$k$个数改为$d$。

数据范围

$1 \leq N, M, \leq 3 \times 10^5 \quad 0 \leq x \leq 10^9$

做法

对于此题，我们似乎做不了别的，只能求出满足条件的原数列中的每个数的最大值。（这可以用线段树在$O(M\times log_2N)O(M\times log_2N)$的时间内求出。）

将此数列当作原数列，对其进行$M$个操作。我们发现，若第$i$次操作的结果比所给结果小，那么原数列不存在，因为原数列中的数已经不可能更大了。若操作结果比所给结果大，那么原数列也不存在（此时是操作之间有矛盾）。

现在只要最大化此数列的或的结果。

若有大于等于$2$个自由（不被操作1所约束）的数，那么令一个等于$2^{29}$，另一个等于$2^{29}-1$，那么或的结果就最大了。

若自由数的个数小于$2$。先不考虑自由的数。对于每个至少出现$2$次的数，我们将其一个减少，方法为：将其二进制表示下的最左边的$2$反转，右边全变为$1$。如果有自由数的话，再贪心地将其二进制高位置$1$，并保证不超过$10^9$。

代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 5;
const int MAX_M = 3e5 + 5;
const int INF = 0x3f3f3f3f;
int N, M;
int T[MAX_M], L[MAX_M], R[MAX_M], X[MAX_M], K[MAX_M], D[MAX_M];
int max_num[MAX_N];
map<int, int> max_num_occur;
struct SegmentTree
{
  int dat[MAX_N << 2];
  void build()
  {
    memset(dat, 0x3f, sizeof dat);
  }
  void update(int a, int b, int c, int l, int r, int k)
  {
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      dat[k] = min(dat[k], c);
      return;
    }
    if (dat[k] != INF) {
      dat[2 * k + 1] = min(dat[2 * k + 1], dat[k]);
      dat[2 * k + 2] = min(dat[2 * k + 2], dat[k]);
      dat[k] = INF;
    }
    update(a, b, c, l, (l + r) / 2, 2 * k + 1);
    update(a, b, c, (l + r) / 2, r, 2 * k + 2);
  }
  int query(int x, int l, int r, int k)
  {
    if (r - l == 1) return dat[k];
    if (dat[k] != INF) {
      dat[2 * k + 1] = min(dat[2 * k + 1], dat[k]);
      dat[2 * k + 2] = min(dat[2 * k + 2], dat[k]);
      dat[k] = INF;
    }
    int mid = (l + r) / 2;
    if (x < mid) return query(x, l, (l + r) / 2, 2 * k + 1);
    else return query(x, (l + r) / 2, r, 2 * k + 2);
  }
} st1;
struct SegmentTree2
{
  int dat[MAX_N << 2];
  int *src;
  void build(int l, int r, int k)
  {
    if (r - l == 1) {
      dat[k] = src[l];
      return;
    }
    build(l, (l + r) / 2, 2 * k + 1);
    build((l + r) / 2, r, 2 * k + 2);
    dat[k] = max(dat[2 * k + 1], dat[2 * k + 2]);
  }
  void update(int x, int v, int l, int r, int k)
  {
    if (r - l == 1) {
      dat[k] = v;
      return;
    }
    int mid = (l + r) / 2;
    if (x < mid) update(x, v, l, (l + r) / 2, 2 * k + 1);
    else update(x, v, (l + r) / 2, r, 2 * k + 2);
    dat[k] = max(dat[2 * k + 1], dat[2 * k + 2]);
  }
  int query(int a, int b, int l, int r, int k)
  {
    if (b <= l || r <= a) return INT_MIN;
    if (a <= l && r <= b) {
      return dat[k];
    }
    int vl = query(a, b, l, (l + r) / 2, 2 * k + 1);
    int vr = query(a, b, (l + r) / 2, r, 2 * k + 2);
    return max(vl, vr);
  }
} st2;
int main()
{
  cin >> N >> M;
  memset(max_num, -1, sizeof max_num);
  st1.build();
  for (int i = 0; i < M; ++i) {
    scanf("%d", &T[i]);
    if (T[i] == 1) {
      scanf("%d%d%d", &L[i], &R[i], &X[i]); --L[i];
      st1.update(L[i], R[i], X[i], 0, N, 0);
    } else {
      scanf("%d%d", &K[i], &D[i]); --K[i];
      if (max_num[K[i]] == -1) {
        max_num[K[i]] = st1.query(K[i], 0, N, 0);
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    if (max_num[i] == -1) {
      max_num[i] = st1.query(i, 0, N, 0);
    }
  }
  st2.src = max_num;
  st2.build(0, N, 0);
  bool exist_ans = true;
  for (int i = 0; i < M; ++i) {
    if (T[i] == 1) {
      if (st2.query(L[i], R[i], 0, N, 0) != X[i]) {
        exist_ans = 0;
        break;
      }
    } else {
      st2.update(K[i], D[i], 0, N, 0);
    }
  }
  if (!exist_ans) {
    printf("NO\n");
  } else {
    printf("YES\n");
    for (int i = 0; i < N; ++i) {
      max_num_occur[max_num[i]]++;
    }
    if (max_num_occur[INF] >= 2) {
      for (int i = 0; i < N; ++i) {
        if (max_num[i] == INF) {
          max_num[i] = (1 << 29);
          if (--max_num_occur[INF] == 0) {
            max_num[i] = (1 << 29) - 1;
          }
        }
      }
      for (int i = 0; i < N; ++i) {
        printf("%d ", max_num[i]);
      }
    } else {
      int res = 0;
      for (int i = 0; i < N; ++i) {
        if (max_num[i] == 0 || max_num[i] == INF) continue;
        if (--max_num_occur[max_num[i]] > 0) {
          int log2x = 31 - __builtin_clz(max_num[i]);
          max_num[i] = (1 << log2x) - 1;
        }
        res |= max_num[i];
      }
      int free_num = 0;
      for (int i = 29; i >= 0; --i) {
        if (res >> i & 1) continue;
        if (free_num + (1 << i) > (int)(1e9)) continue;
        free_num |= (1 << i);
      }
      for (int i = 0; i < N; ++i) {
        if (max_num[i] == INF) {
          printf("%d ", free_num);
        } else {
          printf("%d ", max_num[i]);
        }
      }
    }
  }
  return 0;
}