扫描线

扫描线

把题目给的的区间想象成平面直角坐标系上的点. 再想象一条直线, 按顺序扫描获取信息, 维护信息

求出矩形面积并 :

把一个矩形看出两条平行于纵轴的边, 一条表示加入, 一条表示删除, 有很多区间的信息是一样的, 用乘法处理, 扫描线上的信息最多变动 \(2n\) 次

考虑用线段树维护, 考虑到区间的最小值 \(\ge 0\) 所以只需要维护一个区间最小值出现次数

例题 洛谷P5490

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

struct Tr{
  int l, r, minx, cnt, lazy;
}t[N * 4];

struct Node{
  int x, y, y2, c;
}a[N];

long long ans;
int n, x[N], y[N], x2[N], y2[N], tot;
vector<int>e;

void renew(int p){
  t[p].minx = min(t[p * 2].minx, t[p * 2 + 1].minx);
  t[p].cnt = (t[p].minx == t[p * 2].minx) * t[p * 2].cnt + (t[p].minx == t[p * 2 + 1].minx) * t[p * 2 + 1].cnt;
}

void tog(int p, int L){
  t[p].lazy += L;
  t[p].minx += L;
}

void Lazy(int p){
  tog(p * 2, t[p].lazy);
  tog(p * 2 + 1, t[p].lazy);
  t[p].lazy = 0;
}

void build(int p, int l, int r){
  t[p].l = l, t[p].r = r;
  if(l == r){
    t[p].minx = 0, t[p].cnt = e[l] - e[l - 1];
    return;
  }
  int mid = (l + r) >> 1;
  build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
  renew(p);
}

void updata(int p, int l, int r, int L){
  if(t[p].l >= l && t[p].r <= r){
    tog(p, L);
    return;
  }
  Lazy(p);
  int mid = (t[p].l + t[p].r) >> 1;
  if(l <= mid){
    updata(p * 2, l, r, L);
  }
  if(r > mid){
    updata(p * 2 + 1, l, r, L);
  }
  renew(p);
}

int getsum(int p, int l, int r){
  if(t[p].l >= l && t[p].r <= r){
    return (t[p].minx == 0 ? t[p].cnt : 0);
  }
  Lazy(p);
  int mid = (t[p].l + t[p].r) >> 1, sum = 0;
  if(l <= mid){
    sum += getsum(p * 2, l, r);
  }
  if(r > mid){
    sum += getsum(p * 2 + 1, l, r);
  }
  return sum;
}

int main(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> x[i] >> y[i] >> x2[i] >> y2[i];
    e.push_back(y[i]);
    e.push_back(y2[i]);
  }
  sort(e.begin(), e.end());
  for(int i = 1; i <= n; ++i){
    y[i] = lower_bound(e.begin(), e.end(), y[i]) - e.begin() + 1;
    y2[i] = lower_bound(e.begin(), e.end(), y2[i]) - e.begin();
    a[++tot] = {x[i], y[i], y2[i], 1}, a[++tot] = {x2[i], y[i], y2[i], -1};
  }
  build(1, 1, e.size() - 1);
  sort(a + 1, a + tot + 1, [](const Node &i, const Node &j){  return i.x < j.x;});
  for(int i = 1; i <= tot; ++i){
    ans += 1ll * (e.back() - e[0] - getsum(1, 1, e.size() - 1)) * (a[i].x - a[i - 1].x);
    updata(1, a[i].y, a[i].y2, a[i].c);
  }
  cout << ans;
  return 0;
}

时间复杂度 \(O(n \log n)\)

空间复杂度 \(O(n)\)

矩形周长并 :

思路 + 代码