题解 P3875 【[TJOI2010]被污染的河流】

· · 题解

emm这题就是个矩形面积并qwq

但是

现在的某些人， 一看到扫描线， 就想到线段树， 更有甚者， 认为扫描线就是线段树的一种实现形式罢了。

实际上， 分块也是可以做扫描线问题的 （线段树也是一种分块你这不是废话吗

小蒟蒻这里就发一篇分块扫描线的题解qwq

具体做法就是先保存一下每个矩形的左右边， 然后按从左到右排序（横坐标)， 循环从左到右枚举每一条边， 先计算出上一条边到这条边一共有多少面积的贡献， 即（当前边的位置-上条边的位置）* 上次修改后的序列上有多少个被覆盖次数非0的点（纵坐标）

然后再根据这条边是一个矩形开始的边还是结束的边来判断是在分块上区间加还是区间减就行啦qwq

这里提一下分块的维护区间非零个数的方法：

维护一下一个块内 被散块覆盖所覆盖的（不计算整块修改） 次数非零的点的个数， 和整块覆盖的次数（非负）

统计的时候判断一下整块覆盖的次数是否为0， 如果为0的答案就加上被散块所覆盖的覆盖次数非零的点的个数， 否则就直接加上块长久好了qwq（改块被整体覆盖了）

然后就没什么啦。 没怎么调参跑得还挺快， 当然还有能优化的地方， 小蒟蒻比较懒就没有写， 但是还是提一下吧， 应该还是可以减少一定常数的qwq

改进： 在统计和修改的时候顺便维护一下 被覆盖的最上面的和最下面的点， 这样就能缩小查询的范围啦qwqwq

那么代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, z, xx, yy, cnt;
int sq;
int a[maxn], b[maxn], tag[maxn], ans[maxn];

struct hz {
    int pos;
    int st;
    int ed;
    int bl; //0为开始1为结束 
    bool operator < (const hz &o)const{
        if(pos == o.pos) 
          return bl < o.bl;
        return pos < o.pos;
    }
}h[maxn];

inline void in(re int &x){
    x=0;int bl = 1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c == '-')
          bl = -1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x *= bl;
}

void out(re int a){
    if(a < 0) {
        putchar('-');
        a = -a;
    }
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

int query() {
    int res = 0;
    FOR(i, 1, b[100002]) { //第一个和最后一个块不可能打标记 
        if(tag[i])
          res += sq;
        else
          res += ans[i]; 
    }
    return res;
}

void changeup(int x, int y) {
    FOR(i, x, min(y, b[x]*sq)) {
        ++a[i]; 
        if(a[i] == 1)  
          ++ans[b[x]];
    }
    if(b[x] != b[y])
      FOR(i, (b[y]-1)*sq+1, y) {
          ++a[i];
          if(a[i] == 1)
            ++ans[b[y]];
      }
    FOR(i, b[x]+1, b[y]-1)
      ++tag[i];
} 

void changedown(int x, int y) {
    FOR(i, x, min(y, b[x]*sq)) {
        --a[i]; 
        if(a[i] == 0)  
          --ans[b[x]];
    }
    if(b[x] != b[y])
      FOR(i, (b[y]-1)*sq+1, y) {
          --a[i];
          if(a[i] == 0)
            --ans[b[y]];
      }
    FOR(i, b[x]+1, b[y]-1)
      --tag[i];
}

int main() {
    in(n);
    sq = sqrt(100002);
    FOR(i, 1, 100002)
      b[i] = (i-1)/sq+1;
    FOR(i, 1, n) {
        in(x), in(y), in(xx), in(yy);
        if(y == yy) {
            if(x > xx)
              swap(x, xx);
            h[++cnt].bl = 0;
            h[cnt].st = y;
            h[cnt].ed = y+1;
            h[cnt].pos = x+1;

            h[++cnt].bl = 1;
            h[cnt].st = y;
            h[cnt].ed = y+1;
            h[cnt].pos = xx;
        }
        else {
            if(y > yy)
              swap(y, yy);
            h[++cnt].bl = 0;
            h[cnt].st = y+1;
            h[cnt].ed = yy;
            h[cnt].pos = x;

            h[++cnt].bl = 1;
            h[cnt].st = y+1;
            h[cnt].ed = yy;
            h[cnt].pos = x+1;
        }
    }
    sort(h+1, h+cnt+1);
    int pre = 0;
    int res = 0;
    int now = 0;
    FOR(i, 1, cnt) {
        if(h[i].bl == 1) {
            now = h[i].pos;
            res += (now-pre+1)*query();
            pre = now+1;
            changedown(h[i].st, h[i].ed);
        }
        else {
            now = h[i].pos;
            res += (now-pre)*query();
            pre = now;
            changeup(h[i].st, h[i].ed);
        }
    }
    out(res);
    putchar(10);
}