代码源扫描线权值线段树板子-蒲公英云

矩形面积并（存档）

矩形面积并 - 题目 - Daimayuan Online Judge

题意：

Code（存档，还没写完）：

#include <bits/stdc++.h>
#define y1 Y1
#define int long long
using namespace std;
const int mxn=2e5+10;
const int mxe=2e5+10;
const int mod=1e9+7;
struct info{
    int minv,mincnt;
};
info operator+(const info &l,const info &r){
    info res;
    res.minv=min(l.minv,r.minv);
    if(l.minv==r.minv) res.mincnt=l.mincnt+r.mincnt;
    else if(l.minv<r.minv) res.mincnt=l.mincnt;
    else res.mincnt=r.mincnt;
    return res;
}
struct Segtree{
    int t;
    info val;
}tree[mxe<<4];
vector<int> Vx;
vector<array<int,4> > V;
int N;
int x1,x2,y1,y2;
void pushup(int rt){
    tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
}
void build(int rt,int l,int r){
    if(l==r){
        tree[rt]={0,Vx[r]-Vx[r-1]};
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void settag(int rt,int tag){
    tree[rt].val.minv=tree[rt].val.minv+tag;
    tree[rt].t=tree[rt].t+tag;
}
void pushdown(int rt){
    if(tree[rt].t){
        settag(rt<<1,tree[rt<<1].t);
        settag(rt<<1|1,tree[rt<<1|1].t);
        tree[rt].t=0;
    }
}
void modify(int rt,int l,int r,int x,int y,int k){
    if(x<=l&&r<=y){
        tree[rt].t+=k;
        tree[rt].val.mincnt+=(r-l+1)*k;
        return;
    }
    pushdown(rt);
    int mid=l+r>>1;
    if(x<=mid) modify(rt<<1,l,mid,x,y,k);
    if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k);
    pushup(rt);
}
void solve(){
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>x1>>x2>>y1>>y2;
        Vx.push_back(x1);
        Vx.push_back(x2);
        V.push_back({y1,1,x1,x2});
        V.push_back({y2,-1,x1,x2});
    }
    sort(V.begin(),V.end());
    sort(Vx.begin(),Vx.end());
    Vx.erase(unique(Vx.begin(),Vx.end()),Vx.end());
    int m=Vx.size()-1;
    int last=0;
    build(1,1,m);
    int totlen=tree[1].val.mincnt;
    int ans=0;
    for(auto it:V){
        int cov=totlen;
        if(tree[1].val.minv==0){
            cov=totlen-tree[1].val.mincnt;
        }
        ans+=(it[0]-last)*cov;
        last=it[0];
        int x1=lower_bound(Vx.begin(),Vx.end(),it[2])-Vx.begin()+1;
        int x2=lower_bound(Vx.begin(),Vx.end(),it[3])-Vx.begin();
        if(x1>x2) continue;
        modify(1,1,N,x1,x2,it[1]);
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}

二维数点

题意：

思路：

二维数点本质上也是扫描线，即枚举一个指针，去枚举一棵线段树

在这里，枚举纵坐标，线段树维护一个横坐标区间内有多少点

这道题也用了离线的思想，将询问排序，在维护线段树的同时维护答案数组

具体的看代码就懂

Code：

#include <bits/stdc++.h>
#define y1 Y1
#define low(x) (x&(-x))
#define int long long
using namespace std;
const int mxn=2e5+10;
const int mxe=2e5+10;
const int mod=1e9+7;
vector<int> Vx;
vector<array<int,4> > V;
int N,Q,x,y;
int x1,x2,y1,y2;
int ans[mxn],tr[mxn];
void add(int x,int k){
    for(int i=x;i<=N;i+=low(i)) tr[i]+=k;
}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=low(i)) res+=tr[i];
    return res;
}
void solve(){
    cin>>N>>Q;
    for(int i=1;i<=N;i++){
        cin>>x>>y;
        Vx.push_back(x);
        V.push_back({y,0,x});
    }
    for(int i=1;i<=Q;i++){
        cin>>x1>>x2>>y1>>y2;
        V.push_back({y1-1,2,x1-1,i});
        V.push_back({y2,2,x2,i});
        V.push_back({y2,1,x1-1,i});
        V.push_back({y1-1,1,x2,i});
    }
    sort(V.begin(),V.end());
    sort(Vx.begin(),Vx.end());
    Vx.erase(unique(Vx.begin(),Vx.end()),Vx.end());
    for(auto it:V){
        if(it[1]==0){
            int xx=lower_bound(Vx.begin(),Vx.end(),it[2])-Vx.begin()+1;
            add(xx,1);
        }else{
            int xx=upper_bound(Vx.begin(),Vx.end(),it[2])-Vx.begin()+1-1;
            int t=sum(xx);
            if(it[1]==1) ans[it[3]]-=t;
            else ans[it[3]]+=t;
        }
    }
    for(int i=1;i<=Q;i++) cout<<ans[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}

区间不同数之和

题意：

思路：

枚举一个指针，单独考虑每个元素的贡献

对于每个元素都去每个区间更新贡献，这些区间指的是a[r]只出现一次的所有区间，同时维护离线了的答案区间

枚举+序列DS=扫描线

Code：

#include <bits/stdc++.h>
#define low(x) (x&(-x))
#define int long long
using namespace std;
const int mxn=2e5+10;
const int mxe=2e5+10;
const int mod=1e9+7;
vector<pair<int,int> > V[mxn];
int N,Q,l,r;
int tr[mxn];
int a[mxn],pre[mxn],ans[mxn];
void add(int x,int k){
    for(int i=x;i<=N;i+=low(i)) tr[i]+=k;
}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=low(i)) res+=tr[i];
    return res;
}
void solve(){
    cin>>N>>Q;
    for(int i=1;i<=N;i++){
        cin>>a[i];
    }
    for(int i=1;i<=Q;i++){
        cin>>l>>r;
        V[r].push_back({l,i});
    }
    //枚举一个指针，单独考虑每个元素的贡献
    //对于每个元素都去每个区间更新贡献，这些区间指的是a[r]只出现一次的所有区间，同时维护离线了的答案区间
    //枚举+序列DS=扫描线
    for(int r=1;r<=N;r++){
        int p=pre[a[r]];
        add(p+1,a[r]);
        add(r+1,-a[r]);
        pre[a[r]]=r;
        for(auto it:V[r]) ans[it.second]=sum(it.first);
    }
    for(int i=1;i<=Q;i++) cout<<ans[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}