43| 贴海报
一、核心思路
大坐标 → 离散化压缩 → 暴力覆盖 → 去重统计
离散化：因为墙很长（1e7），不能开数组，所以只收集所有海报的端点+旁边点，把巨大坐标压缩成小编号。
暴力覆盖：按顺序贴海报，后贴的覆盖先贴的，每个位置只保留最后一张海报编号。
统计答案 ：遍历所有位置，按海报编号去重，出现过的海报就是可见的。
二、注意事项
离散化必须存：L, L+1, R, R+1为什么？
防止两个区间共用端点，导致块切错、答案错误。
三、代码实现
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e7 + 10; int a[N], b[N], disc[N * 4], n, m, pos; unordered_map <int, int> id; // <原始数，离散后的下标> int w[N * 4]; bool st[N * 4]; signed main() { cin >> n >> m; // 离散化数组 for(int i = 1; i <= m; i++) { cin >> a[i] >> b[i]; disc[++pos] = a[i]; disc[++pos] = a[i] + 1; disc[++pos] = b[i]; disc[++pos] = b[i] + 1; } // 排序 sort (disc + 1, disc + 1 + pos); // 去重 pos = unique(disc + 1, disc + 1 + pos) - (disc + 1); for(int i = 1; i <= pos; i++) id[disc[i]] = i; // 模拟贴海报的过程 for(int i = 1; i <= m; i++) { int l = id[a[i]], r = id[b[i]]; for(int j = l; j <= r; j++) { w[j] = i; } } // 统计 int ret = 0; for (int i = 1; i <= pos; i++) { int now = w[i]; if(st[now] || !now) continue; else { st[now] = 1; ret++; } } cout << ret << endl; return 0; }