43| 贴海报

一、核心思路大坐标 → 离散化压缩 → 暴力覆盖 → 去重统计离散化因为墙很长1e7不能开数组所以只收集所有海报的端点旁边点把巨大坐标压缩成小编号。暴力覆盖按顺序贴海报后贴的覆盖先贴的每个位置只保留最后一张海报编号。统计答案 遍历所有位置按海报编号去重出现过的海报就是可见的。二、注意事项离散化必须存L, L1, R, R1为什么防止两个区间共用端点导致块切错、答案错误。三、代码实现#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; }