Codeforces Round 737 D.Ezzat and Grid
有 $n$ 个长度为 $10^9$ 的01串, 一个排在一行. 需要删去一些01串(行), 使得相邻两行中, 至少存在一列, 这一位上两个都是1.
01串由 m 个区间的形式给出, 三元组 $(i, l, r)$ 表示第 $i$ 个01串中, $[l,r]$ 区间上都是1.
求一个删除次数最少的方案.
$1 \le n, m \le 3 \cdot 10^5$
显然dp. 印象里早年在洛谷某次月赛做到过相似的题, 也是一行一行dp, 但是我忘记了, 有空回去补补.
设 $dp(i)$ 表示前 $i$ 行, 选第 $i$ 行, 能够留下来的最多多少行. 转移显然从能够相邻的前面的状态转移.
问题就在于, 如何快速知道, 哪些行可以和这一行相邻. 注意到第 $i$ 行的1是若干段连续的区间, 如果某一行和这些区间有交集, 那么就可以转移. 也就是说, 我们需要一个区间查询的操作. 这里就上线段树, 开一个大小为 $10^9$ 的线段树, 记录哪些点存在哪些行之类的信息. 做完一行时如果我们把当前行上1的区间加上当前行, 这样区间查询一下, 就知道可以从哪里转移了. 由于我们需要取最大值, 那么更小的点永远不会是决策点, 所以可以在点中记录 $dp(j)$ 的最大值, 同时记录决策点(因为需要方案), 然后区间查询最大值, 可以很方便地转移.
答案也在做完所有转移后, 查询整个区间得到最大的 $dp(i)$.
然后 $10^9$ 直接开是开不下的, 可以动态开点或者离散化. 注意离散后点最多有 $2m$, 线段树要再开大一倍.
线段树区间查询, 区间修改复杂度$O(\log m)$, 查询和修改的次数为 $O(m)$, 所以总复杂度 $O(n \log m + m \log m)$
struct Node { // 线段节点
int l, r, mid;
PII mx, tag; // val为线段和的值, tag为标记值
} t[MAXN << 3]; // 线段节点要开4倍数据点的大小
/* 更新一条完整的线段 */
void updateNode(int u, PII d) {
t[u].mx = max(t[u].mx, d);
t[u].tag = max(t[u].tag, d); //打上标记, 不再往下
}
/* 将标记下放 */
void pushDown(int u) {
updateNode(LCH(u), t[u].tag);
updateNode(RCH(u), t[u].tag);
t[u].tag = {0, 0}; //取消标记
}
/* 由左右儿子线段合并更新当前线段 */
void pushUp(int u) {
t[u].mx = max(t[LCH(u)].mx, t[RCH(u)].mx);
}
/* 递归建树 */
void build(int l, int r, int u) {
t[u] = Node{l, r, (l+r)>>1, {0, 0}, {0, 0}};
if (l == r) return; //该线段只有一个点
else { //分成左右两边递归求和
build(l, t[u].mid, LCH(u));
build(t[u].mid+1, t[u].r, RCH(u));
pushUp(u);
}
}
/* 初始化一棵线段树 */
void init(int _n) {
build(1, _n, 1);
}
/* 区间修改 */
void update(int l, int r, PII d, int u = 1) {
if (t[u].l == l && t[u].r == r)
updateNode(u, d); // 找到对应线段更新
else {
pushDown(u); // 访问u的儿子线段, 需要先下放标记更新
if (l > t[u].mid)
update(l, r, d, RCH(u)); //更新的线段全在该区间右边
else if (r <= t[u].mid)
update(l, r, d, LCH(u)); // 全在左边
else { // 跨越了左右两边
update(l, t[u].mid, d, LCH(u));
update(t[u].mid+1, r, d, RCH(u));
}
pushUp(u); // 由儿子线段的更新后的值计算当前线段值
}
}
/* 区间查询 */
PII query(int l, int r, int u = 1) {
if (t[u].l == l && t[u].r == r) return t[u].mx;
pushDown(u);
if (l > t[u].mid) return query(l, r, RCH(u));
if (r <= t[u].mid) return query(l, r, LCH(u));
else return max(query(l, t[u].mid, LCH(u)),
query(t[u].mid+1, r, RCH(u)));
}
int n, m, dp[MAXN], path[MAXN];
vector<PII> ones[MAXN];
VI b;
bool remain[MAXN];
int getID(int x) {
return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int id, l, r;
scanf("%d%d%d", &id, &l, &r);
b.push_back(l), b.push_back(r);
ones[id].emplace_back(l, r);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; i++)
for (int j = 0; j < ones[i].size(); j++) {
auto[l, r] = ones[i][j];
ones[i][j] = make_pair(getID(l), getID(r));
}
init(b.size());
for (int i = 1; i <= n; i++) {
PII k = {0, 0};
for (auto[l, r] : ones[i])
k = max(k, query(l, r));
auto[mx, id] = k;
dp[i] = mx + 1, path[i] = id;
for (auto[l, r] : ones[i])
update(l, r, make_pair(dp[i], i));
}
auto[ans, last] = query(1, b.size());
ans = n - ans;
while (last) {
remain[last] = 1;
last = path[last];
}
printf("%d\n", ans);
for (int i = 1; i <= n; i++)
if (!remain[i])
printf("%d%c", i, "\n "[--ans>0]);
return 0;
}