ACM-ICPC 2018 徐州赛区网络预赛 G. Trace

题目大意 :
有n波海浪，每个海浪是一个以(0,0)为左下角(x,y)为右上角的长方形，每一波海浪会留下自己的长方形边界为海浪残留，同时会冲刷掉长方形内部的其他海浪残留，问n波之后，留下来的海浪边界总长度为多少n<50000

逆序考虑海浪，维护两个函数 col_limit(x)和row_limit(y) 分别表示第x列的前col_limit(x)行的残留会被后面的海浪冲刷掉，第y行的前row_limit(y)列的残留会被后面的冲刷掉。我们可以根据这两个函数转移出第i个海浪对答案的贡献，然后我们考虑，如何更新出i-1下的正确col_limit函数和row_limit函数，容易发现，这是一个区间取最值操作。
现在来总结一下，对于这两个函数，我们有两种操作：区间取最值，点查询。-> 用线段树维护即可

#include<bits/stdc++.h>
using namespace std;

#define ml ((l+r)>>1)
#define mr (ml+1)
struct seg_tree{// 5e4*50*4=5e4*200=1e7
    static const int maxn=5e4+5;
    int mxx[maxn*2*25],lz[maxn*2*25],ls[maxn*2*25],rs[maxn*2*25],tot;

    void push_son(int&son,int l,int r,int lzrt){
        if(son==0) {
            son=++tot;
            mxx[son]=0;
            lz[son]=-1;
            ls[son]=0;
            rs[son]=0;
        }
        if(lzrt!=-1){
            mxx[son]=max(mxx[son],lzrt);
            lz[son]=max(lz[son],lzrt);
        }
    }
    void push_down(int rt,int l,int r){
        push_son(ls[rt],l,ml,lz[rt]);
        push_son(rs[rt],mr,r,lz[rt]);
        lz[rt]=-1;
    }
    void push_up(int rt,int l,int r){
        // nothing
    }
    void build(int rt,int l,int r){//1 1 n
        rt=tot=0;
        push_son(rt,l,r,0);
    }
    void update(int rt,int l,int r,int ql,int qr,int d){
        if(ql<=l&&r<=qr){
            push_son(rt,l,r,d);
        }
        else{
            push_down(rt,l,r);
            if(ml>=ql) update(ls[rt],l,ml,ql,qr,d);
            if(mr<=qr) update(rs[rt],mr,r,ql,qr,d);
            push_up(rt,l,r);
        }
    }
    int query(int rt,int l,int r,int q){
        if(l==r){
            return mxx[rt];
        }
        else{
            push_down(rt,l,r);
            if(ml>=q) return query(ls[rt],l,ml,q);
            else return query(rs[rt],mr,r,q);
        }
    }
}row,col;
//2e7*32bit=2e7*4b=2e4*4kb=20*4mb=80mb   ok

const int maxn=5e4+5;
int x[maxn],y[maxn];
int main(){
    int n;
    scanf("%d",&n);
    row.build(1,1,1e7+5);
    col.build(1,1,1e7+5);
    for(int i=1;i<=n;i++) scanf("%d%d",x+i,y+i);
    long long ans=0;
    for(int i=n;i>=1;i--){
        int rowlimit=row.query(1,1,1e7+5,y[i]);
        int collimit=col.query(1,1,1e7+5,x[i]);
        if(x[i]>rowlimit) ans+=x[i]-rowlimit;
        if(y[i]>collimit) ans+=y[i]-collimit;
        row.update(1,1,1e7+5,1,y[i],x[i]);
        col.update(1,1,1e7+5,1,x[i],y[i]);
    }
    cout<<ans<<endl;
}