2018网络预选赛 徐州G 线段树

线段树，假设求(x1,y1)点的贡献，就找所有比该点出现时间晚，且x坐标大于x1的点中y最大的，贡献就是Y-y1,由于题目条件限制，不可能有x坐标大于(x1,y1)且y坐标大于y1的点，所以贡献肯定为正。

思路参考了这篇博客：https://blog.csdn.net/qq_39599067/article/details/82560005#accode。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
struct node{
    int x,y;
};
node xx[maxn],yy[maxn],re[maxn];
int x[maxn],y[maxn],maxv[2][maxn*4];
int ql,qr,v,p;
bool cmpx(node a,node b){
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x; 
}
bool cmpy(node a,node b){
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y; 
}
void update(int o,int L,int R,int pos){
    if(L==R){
        maxv[pos][o]=v;
        return;
    }
    int M=L+(R-L)/2;
    if(p<=M)update(o*2,L,M,pos);
    else update(o*2+1,M+1,R,pos);
    maxv[pos][o]=max(maxv[pos][o*2],maxv[pos][o*2+1]);
}
int query(int o,int L,int R,int pos){
    int ans=0;
    if(ql<=L&&qr>=R){
        return maxv[pos][o];
    }
    int M=L+(R-L)/2;
    if(ql<=M)ans=max(ans,query(o*2,L,M,pos));
    if(qr>M)ans=max(ans,query(o*2+1,M+1,R,pos));
    return ans;
}
int main(){
    int n;
    long long ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
        xx[i].x=yy[i].x=re[i].x=x[i];
        xx[i].y=yy[i].y=re[i].y=y[i];
    }
    sort(xx+1,xx+1+n,cmpx);
    sort(yy+1,yy+1+n,cmpy);
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    for(int i=n;i>=1;i--){
        int pos=lower_bound(x+1,x+1+n,re[i].x)-x;
        if(pos==n)ans+=1ll*re[i].y;
        else{
            ql=pos+1,qr=n;
            ans+=1ll*(re[i].y-query(1,1,n,0));
        }
        p=pos;
        v=re[i].y;
        update(1,1,n,0);
        pos=lower_bound(y+1,y+1+n,re[i].y)-y;
        if(pos==n)ans+=1ll*re[i].x;
        else{
            ql=pos+1,qr=n;
            ans+=1ll*(re[i].x-query(1,1,n,1));
        }
        p=pos;
        v=re[i].x;
        update(1,1,n,1);
    }
    printf("%lld
",ans);
}