2023.4.13 更新了代码, 修复了错误的离散化长度, 已在代码中注出.
大致题意
有n个人依次贴海报, 第i个海报的范围是[li, ri]. 后面贴的海报会覆盖掉之前贴的海报.
问: 最终还能看到多少张海报.
解题思路
本题属于线段树维护区间染色类别的题目. 本题考察线段树的区间修改, 根节点查询.
这类题目的一大特点就是: 线段树内维护当前整个区间的值, 相当于当前区间维护的值是一个懒标记, 其子节点的值也都为当前节点的值, 若当前区间内部的子区间值不统一, 则需要递归分别给每个子区间赋值, 此时认为当前节点认为没有值即可, 这样在查询的时候, 如果访问到一整个区间都是相同值, 则直接返回即可, 反之需要递归处理.
特别的, 本题的实际数据范围推荐为1E5, 题目中的1E4会报RE
AC代码
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
bool vis[N]; //标记是否已经出现过第i张海报
struct node {
int l, r;
int id; //id表示lazy标签, 也表示当前节点值.
}t[N << 2];
vector<int> v; vector<pair<int, int> > area; //v为离散化数组, area存放海报区间
int find(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }
void pushdown(node& op, int id) { op.id = id; }
void pushdown(int x) {
if (!t[x].id) return;
pushdown(t[x << 1], t[x].id), pushdown(t[x << 1 | 1], t[x].id);
t[x].id = 0;
}
//因为线段树内部不维护任何数值, 所以也可以省去pushup这一操作.
void build(int l, int r, int x = 1) {
t[x] = { l, r, 0 }; //id: 特别的, 如果0也是染色的点, 那么应初始化为-1
if (l == r) return;
int mid = l + r >> 1;
build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
}
void modify(int l, int r, int c, int x = 1) {
if (l <= t[x].l && r >= t[x].r) { pushdown(t[x], c); return; }
pushdown(x);
int mid = t[x].l + t[x].r >> 1;
if (l <= mid) modify(l, r, c, x << 1);
if (r > mid) modify(l, r, c, x << 1 | 1);
}
int ask(int x = 1) {
if (t[x].id) { //当前子树均为同一值, 没必要再递归下去了
if (vis[t[x].id]) return 0;
return vis[t[x].id] = 1;
}
if (t[x].l == t[x].r) return 0; //到叶子结点一定要结束递归
return ask(x << 1) + ask(x << 1 | 1);
}
int main()
{
int T; cin >> T;
while (T--) {
v.clear(); v.push_back(-0x3f3f3f3f); //这里是为了离散化下标从1开始
area.clear();
int n; scanf("%d", &n);
rep(i, n) {
vis[i] = 0; //顺带初始化vis
int l, r; scanf("%d %d", &l, &r);
v.push_back(l), v.push_back(r);
area.push_back({ l, r });
}
/* 离散化部分 */
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
/* 2023.4.13更新代码 BEGIN */
int vlen = v.size();
rep(i, vlen - 1) if (v[i] - v[i - 1] != 1) v.push_back(v[i] - 1); //记为*
// 下面这行是之前错误的代码, 我们的离散化判别应扫描整个vector, 而不是只判断到n
// rep(i, n) if (v[i] - v[i - 1] != 1) v.push_back(v[i] - 1); //记为*
/* 2023.4.13更新代码 END */
sort(v.begin(), v.end());
build(1, v.size() - 1); //因为我的v数组有个-INF, 所以实际的建树大小应为v.size()-1
for (int i = 0; i < n; ++i) {
int l = area[i].first, r = area[i].second;
l = find(l), r = find(r);
modify(l, r, i + 1); //个人习惯编号从1开始
}
printf("%d\n", ask());
}
return 0;
}
这里关于*部分加以解释: 这里是为了防止离散化之前区间不连续, 而错误的离散化导致离散化后区间连续的情况. 网上已经有很多大佬用大篇文章及样例说明过了, 这里就不再多赘述啦, 毕竟我也是刚学过来的. 向前辈们学习致敬!
END
