题解 P5490 【【模板】扫描线】

为啥要离散化啊。。多麻烦。。。 这里提供一种偷懒的做法： 动态开点线段树+标记永久化， 就可省略掉离散化啦！ 大概的思路和其他的题解差不多， 这里就不赘述了， 下面提供做法的实现， 主要在注释中说明。 ```cpp #include <bits/stdc++.h> using namespace std; #define ge getchar() #define Re read() inline int read() { int x = 0, ch; while(!isdigit(ch = ge)) ; while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge; return x; } const int MAXN = 200100; struct Node { int l, r, p; Node() {} Node(int l, int r, int p):l(l), r(r), p(p) {} friend bool operator < (Node a, Node b) { return a.p < b.p; } }Ins[MAXN + 1], Del[MAXN + 1]; struct Segment_Tree { // 下面是线段树 #define ls T[x].r #define rs T[x].l struct Node { int l, r, sum, tg; } T[MAXN << 6]; // 每一次修改最多修改的点数有log级别， 所以动态开点要乘log（最好再乘2） int ct; inline void pushup(int x, int l, int r) { if(T[x].tg) T[x].sum = r - l + 1; // 如果这个点上有标记， 那么就说明被线段覆盖了， 长度就是 r-l+1 else T[x].sum = T[ls].sum + T[rs].sum; // 没有标记就从线段树上的两个儿子节点继承 } // 没有pushdown 标记永久化节省空间 inline void Modify(int&x, int l, int r, int L, int R, int v) { if(!x) x = ++ct; // 动态开点 if(L <= l && r <= R) { T[x].tg += v; // 更新标记 pushup(x, l, r); // 更新节点值 return ; } int mid = (l + r) >> 1; if(L <= mid) Modify(ls, l, mid, L, R, v); if(mid < R) Modify(rs, mid + 1, r, L, R, v); pushup(x, l, r); // 别忘了更新 } inline int Query() { return T[1].sum; } // 询问沿y轴截线段的长度和， 相当于是线段树的1号节点存的长度和。 #undef ls #undef rs }seg; // 上面是线段树 int main() { int n = Re, mi = 1e9, mx = 0; for(int i = 1; i <= n; i++) { int lx = Re, ly = Re, rx = Re, ry = Re; Ins[i] = Node(ly, ry, lx); Del[i] = Node(ly, ry, rx); mi = min(mi, ly); mx = max(mx, ry); } int rt = 0; long long res = 0; sort(Ins + 1, Ins + 1 + n); Ins[n + 1] = Node(0, 0, 2e9); sort(Del + 1, Del + 1 + n); Del[n + 1] = Node(0, 0, 2e9); for(int i = 1, a = 1, b = 1, N = n << 1, las = 0; i <= N; i++) { int x = min(Ins[a].p, Del[b].p); res += 1LL * (x - las) * seg.Query(), las = x; // 求出上次询问的横坐标差 * 当前扫描线上的沿y轴的截线段长度和。 if(Ins[a].p == x) seg.Modify(rt, mi, mx, Ins[a].l, Ins[a].r - 1, 1), ++a; // 如果当前这个x坐标需要插入一条线段， 那么就+1 else seg.Modify(rt, mi, mx, Del[b].l, Del[b].r - 1, -1), ++b; // 如果删除就-1 //这一段为啥要将r-1呢？ 因为线段树里头的线段默认计算的长度为 r-l+1， 这个时候我们把r-1之后才符合计算面积的公式， 而且所有插入的线段的r都减了1之后计算并集并不会影响。 } printf("%lld\n", res); return 0; // 完结撒花 } // 没有离散化真清爽啊（雾） ```