注意题目保证不会有一个矩形完全包括另一个矩形的情况

时间序上从后往前看,一个坐标\((x,y)\)加进来之前,如果已经有\(x_i<x\),则对结果的贡献为\(x-x_i\);若不存在\(x_i<x\),则对结果的贡献为\(x\).纵坐标\(y\)同理.

用两个集合维护已经存在的横纵坐标,每次用set自带的lower_bound查找第一个大于等于当前x和y的值,然后将迭代器--以查找上一个元素(即第一个小于它的元素).

#include
    
     #define X first#define Y secondusing namespace std;typedef long long LL;pair
     
       vz[50005];set
      
        dp1;           //Xset
       
         dp2;           //Yint main(){    #ifndef ONLINE_JUDGE        freopen("in.txt","r",stdin);        freopen("out.txt","w",stdout);    #endif    set
        
          :: iterator it;    set
         
           :: reverse_iterator ir; int n; while(scanf("%d",&n)==1){ dp1.clear(); dp2.clear(); for(int i=1;i<=n;++i) scanf("%lld %lld",&vz[i].first,&vz[i].second); LL res=0; for(int i=n;i>=1;--i){ it = dp1.lower_bound(vz[i].X); if(it==dp1.begin()||dp1.empty()){ res += vz[i].first; } else{ --it; res += vz[i].X - (*it); } it = dp2.lower_bound(vz[i].Y); if(it==dp2.begin()||dp2.empty()){ res += vz[i].second; } else{ --it; res += vz[i].Y - (*it); } dp1.insert(vz[i].first); dp2.insert(vz[i].second); } printf("%lld\n",res); } return 0;}