同问。
感觉这道题根本就不是最小点覆盖。
这里附上本蒟蒻的代码(用线段树维护零区间的覆盖)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int sum[2 * MAXN], lazy[2 * MAXN], ls[2 * MAXN], rs[2 * MAXN], n, m, k, cnt, root, lbq[MAXN], rbq[MAXN], bs;
int build (int lb, int rb) {
int cur = ++cnt;
if (lb != rb) {
int mid = (lb + rb) >> 1;
ls[cur] = build (lb, mid);
rs[cur] = build (mid + 1, rb);
}
sum[cur] = rb - lb + 1;
return cur;
}
void pushdown (int cur) {
if (lazy[cur]) {
lazy[ls[cur]] = lazy[rs[cur]] = 1;
sum[ls[cur]] = sum[rs[cur]] = 0;
lazy[cur] = 0;
}
}
void modify (int cur, int ml, int mr, int tl, int tr) {
if (ml <= tl && tr <= mr) {
sum[cur] = 0;
lazy[cur] = 1;
}
else {
pushdown (cur);
int mid = (tl + tr) >> 1;
if (ml <= mid) modify (ls[cur], ml, mr, tl, mid);
if (mr > mid) modify (rs[cur], ml, mr, mid + 1, tr);
sum[cur] = sum[ls[cur]] + sum[rs[cur]];
}
}
int query (int cur, int ql, int qr, int tl, int tr) {
if (ql <= tl && tr <= qr) return sum[cur];
else {
pushdown (cur);
int mid = (tl + tr) >> 1;
int ans = 0;
if (ql <= mid) ans += query (ls[cur], ql, qr, tl, mid);
if (qr > mid) ans += query (rs[cur], ql, qr, mid + 1, tr);
return ans;
}
}
int find (int cur, int ql, int qr, int tl, int tr) {
if (sum[cur] == 0) return 0;
else if (tl == tr) {
return tl;
}
else {
pushdown (cur);
int mid = (tl + tr) >> 1;
int ans = 0;
if (ql <= mid) ans ^= find (ls[cur], ql, qr, tl, mid);
if (qr > mid) ans ^= find (rs[cur], ql, qr, mid + 1, tr);
return ans;
}
}
int main () {
cin >> n >> k >> m;
root = build (1, n);
int a, b, c;
for (int i = 1;i <= m;i++) {
cin >> a >> b >> c;
if (c) {
lbq[++bs] = a;
rbq[bs] = b;
}
else modify (root, a, b, 1, n);
}
set<int> ans;
for (int i = 1;i <= bs;i++) {
if (query(root, lbq[i], rbq[i], 1, n) == 1) ans.insert(find(root, lbq[i], rbq[i], 1, n));
}
if (query (root, 1, n, 1, n) == k) for (int i = 1;i <= n;i++) {
if (query(root, i, i, 1, n) == 1) ans.insert(i);
}
if (ans.size() == 0) cout << -1;
else {
for (int p: ans) cout << p << endl;
}
return 0;
}
```
by M1ndeveloped @ 2023-03-01 13:35:19