洛谷 - P5490 扫描线

传送门：洛谷 - P5490

思路分析

区间修改的时候跟普通线段树不一样

样例输入

2
100 100 200 200
150 150 250 255

样例输出

18000

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

struct node {
    int l,r,mid,cover;
    ll len;
} tree[N<<2];

struct Line {
    ll x,y1,y2,pos;
    bool operator < (Line a) {
        return x<a.x;
    }
} line[N<<1];

ll v[N];

void build(int x,int l,int r) {
    tree[x].l=l;
    tree[x].r=r;
    tree[x].mid=l+r>>1;
    if(r-l<=1) {
        return ;
    }
    int mid=tree[x].mid;
    build(ls,l,mid);
    build(rs,mid,r);
}

void pp(int x) {
    if(tree[x].cover) tree[x].len=v[tree[x].r]-v[tree[x].l];
    else tree[x].len=tree[ls].len+tree[rs].len;
}

void modify(int x,int l,int r,int k) {
    if(l<=v[tree[x].l] && v[tree[x].r]<=r) {
        tree[x].cover+=k;
        pp(x);
        return ;
    }
    if(l<v[tree[ls].r]) modify(ls,l,r,k);
    if(r>v[tree[rs].l]) modify(rs,l,r,k);
    pp(x);
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        v[i]=b,v[n+i]=d;
        line[i]= {a,b,d,1};
        line[n+i]= {c,b,d,-1};
    }
    n<<=1;
    sort(v+1,v+1+n);
    sort(line+1,line+1+n);
    int tot=unique(v+1,v+1+n)-v-1;
    build(1,1,tot);
    ll ans=0;
    for(int i=1; i<=n; i++) {
        ans+=tree[1].len*(line[i].x-line[i-1].x);
        modify(1,line[i].y1,line[i].y2,line[i].pos);
    }
    cout<<ans<<endl;




    return 0;
}