线段树(区间修改,区间查询)+离散化
题意
有$n$个人依次贴海报, 第$i$个海报的范围是$[l_i, r_i]$. 后面贴的海报会覆盖掉之前贴的海报.
问: 最终还能看到多少张海报.
分析
由于题目区间范围过大,所以首先要进行离散化,在离散化的时候需要进行一步特殊处理,避免发生两个本不相邻的区间而相邻。(本题关键)
正常离散化后:
此时发现,原来的三张海报现在只剩两张,解决的方法就是在对所有点排序后,对于两个相邻且大小差距超过1的点,在这两个点之间插入一个点,这样就可以空出中间的区间。
特殊处理离散化后:
考虑如何处理覆盖,对于一个区间如果完全被一张海报覆盖,那么它的懒标记就记为该海报的编号,一旦该区间的一部分被其他海报覆盖,就将该懒标记向下传递。
最后询问时,直接从根节点出发向下递归,询问当前区间的懒标记是否非零(非零说明当前区间被某张海报完全覆盖),一旦懒标记非零,就直接记录并且return(向下递归无意义,已经被完全覆盖),否则继续乡下递归直至叶节点。
#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10; // 每个区间有两个端点,以及特殊处理会插入额外的点,因此额外开4倍的空间
struct SEG{
#define lc u << 1
#define rc u << 1 | 1
struct Node{
int l, r;
int add;
}tr[N * 4];
set<int> S;
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if (l == r) return;
int mid = l + r >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
}
void pushdown(int u)
{
Node &root = tr[u], &left = tr[lc], &right = tr[rc];
if (root.add)
{
int &x = root.add;
left.add = x;
right.add = x;
x = 0;
}
}
void modify (int u, int l, int r, int x)
{
if (tr[u].l >= l && tr[u].r <= r) tr[u].add = x;
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(lc, l, r, x);
if (r > mid) modify(rc, l, r, x);
}
}
void query(int u)
{
if (tr[u].add) {S.insert(tr[u].add); return; }
if (tr[u].l == tr[u].r) return;
query(lc), query(rc);
}
}seg;
void solve()
{
seg.S.clear();
int n;
cin >> n;
int m = n * 2;
vector<PII> q;
vector<int> alls;
for (int i = 0; i < n ;i++)
{
int l, r;
cin >> l >> r;
alls.push_back(l), alls.push_back(r);
q.push_back(make_pair(l, r));
}
/ * 特殊处理 * /
for (int i = 1; i < m; i++)
if (alls[i] - alls[i - 1] > 1)
alls.push_back(alls[i] - 1);
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
seg.build(1, 1, alls.size());
for (int i = 0; i < n; i++)
{
int l = lower_bound(alls.begin(), alls.end(), q[i].x) - alls.begin() + 1;
int r = lower_bound(alls.begin(), alls.end(), q[i].y) - alls.begin() + 1;
seg.modify(1, l, r, i + 1);
}
seg.query(1);
cout << seg.S.size() << endl;
}
int main()
{
ios::sync_with_stdio(0);
int T = 1;
cin >> T;
for(int turn = 1 ; turn <= T ; turn++)
solve();
}
POJ的评测是真垃圾,各种CE
真就一题做一天,明明不难W_W
按道理说在找到叶子节点之前一定会碰到 标记不为0返回了,就算到叶子了,叶子的add一定不为0.。
应该是这样的。。。
可是我没加这句 wa了好多发。。。。。。
啊。。我懂了。,,,,,不一定铺满1到n,,,,,,
加油~
提个问题 在query时这句话的意义
if (tr[u].l == tr[u].r) return;