ACM-ICPC 2018 徐州赛区网络预赛 G Trace(逆向，两颗线段树写法）

https://nanti.jisuanke.com/t/31459

思路

• 凡是后面的轨迹对前面的轨迹有影响的，可以尝试从后往前扫
• 区间修改需要push_down,单点更新所以不需要push_up(用于区间查询)
• 多颗线段树的时候将函数写进结构体里，这样所有函数只需要写一次了

#include<bits/stdc++.h>

#define pb push_back

#define M 100005

using namespace std;

int n,i,x[M],y[M],sz,tp;

long long ans;

vector<int>p;

struct N{

	int ma[M<<2];

	void push_down(int o){

		if(ma[o]>ma[o<<1])ma[o<<1]=ma[o];

		if(ma[o]>ma[o<<1|1])ma[o<<1|1]=ma[o];

		ma[o]=0;

	}

	void bd(int o,int l,int r){

		ma[o]=0;

		if(l==r)return;

		int mid=(l+r)/2;

		bd(o<<1,l,mid);bd(o<<1|1,mid+1,r);

	}

	void ud(int o,int l,int r,int L,int R,int x){

		if(L<=l&&r<=R){ma[o]=max(ma[o],x);return ;}

		push_down(o);

		int mid=(l+r)/2;

		if(L<=mid)ud(o<<1,l,mid,L,R,x);

		if(R>mid)ud(o<<1|1,mid+1,r,L,R,x);

	}

	int qy(int o,int l,int r,int pos){

		if(l==r)return ma[o];

		push_down(o);

		int mid=(l+r)/2;

		if(pos<=mid)return qy(o<<1,l,mid,pos);

		return qy(o<<1|1,mid+1,r,pos);

	}

}X,Y;

int id(int x){return lower_bound(p.begin(),p.begin()+sz,x)-p.begin()+1;}

int main(){

	scanf("%d",&n);p.clear();

	for(i=1;i<=n;i++){

		scanf("%d%d",&x[i],&y[i]);

		p.pb(x[i]);p.pb(y[i]);

	}

	sort(p.begin(),p.end());

	sz=unique(p.begin(),p.end())-p.begin();

	X.bd(1,1,sz);Y.bd(1,1,sz);

	ans=0;

	for(i=n;i>=1;i--){

		tp=X.qy(1,1,sz,id(y[i]));

	   if(x[i]>tp){

	   	ans+=x[i]-tp;

	   	X.ud(1,1,sz,1,id(y[i]),x[i]);

	   }

	   tp=Y.qy(1,1,sz,id(x[i]));

	   if(y[i]>tp){

	   	ans+=y[i]-tp;

	   	Y.ud(1,1,sz,1,id(x[i]),y[i]);

	   }

	}

	cout<<ans<<endl;

}