[ccPBOXES]Pretty Boxes

将其按照$(S_{i},P_{i})$递增排序，此时问题即选择$k$对括号并最大化$\sum_{i\in R}P_{i}-\sum_{i\in L}P_{i}$

结论：对于$k$时的最优选法$(L_{k},R_{k})$，存在$k+1$时的最优选法$(L_{k+1},R_{k+1})$满足$L_{k}\subseteq L_{k+1}$且$R_{k}\subseteq R_{k+1}$

（证明参考codechef的题解）

在$i\in L_{k}$处标记1，$i\in R_{k}$处标记-1，记$sum_{i}$为以此法标记的前缀和，合法当且仅当$sum_{i}$均非负（初始合法）

设额外选择的位置分别为$x,y$，显然选择后仍合法当且仅当$\forall y\le i

考虑使用线段树维护，由于区间内并不一定有0，将0用区间最小值代替即可

具体的，对于一个区间维护以下信息：

1.$\min sum_{i}$（以下记为$mn$）$,\min P_{x}$和$\max P_{y}$

2.$\max P_{y}-P_{x}$（无限制&要求$\forall y\le i

3.$\min P_{x}$（要求$\forall l\le i

由于需要求方案（选择后不能再选），还需要存储$P_{i}$取到最大/最小的位置

通过上述信息即可支持合并&修改，时间复杂度为$o(n\log n)$，可以通过

  1 #include
  2 using namespace std;
  3 #define N 200005
  4 #define oo 0x3f3f3f3f
  5 #define ll long long
  6 #define L (k<<1)
  7 #define R (L+1)
  8 #define mid (l+r>>1)
  9 pair<int,int>a[N];
 10 int n,x,y,P[N],mn[N<<2],tag[N<<2],mng[N<<2],mxg[N<<2],mnf[N<<2],mxf[N<<2];
 11 ll sum;
 12 struct Pair{
 13     int x,y;
 14     int get_val(){
 15         if (!x)return -oo;
 16         return P[y]-P[x];
 17     }
 18 }ans,g[N<<2],f[N<<2];
 19 int get_min(int x,int y){
 20     if ((x)&&((!y)||(P[x]return x;
 21     return y;
 22 }
 23 int get_max(int x,int y){
 24     if ((x)&&((!y)||(P[x]>P[y])))return x;
 25     return y;
 26 }
 27 Pair get_max(Pair x,Pair y){
 28     if (x.get_val()>y.get_val())return x;
 29     return y;
 30 }
 31 void upd(int k,int x){
 32     tag[k]+=x,mn[k]+=x;
 33 }
 34 void up(int k){
 35     mn[k]=min(mn[L],mn[R]);
 36     mng[k]=get_min(mng[L],mng[R]);
 37     mxg[k]=get_max(mxg[L],mxg[R]);
 38     g[k]=get_max(g[L],g[R]);
 39     g[k]=get_max(g[k],Pair{mng[L],mxg[R]});
 40     g[k]=get_max(g[k],Pair{mng[R],mxg[L]});
 41     f[k]=Pair{mng[L],mxg[R]};
 42     if (mn[L]==mn[R]){
 43         mnf[k]=mnf[L],mxf[k]=mxf[R];
 44         f[k]=get_max(f[k],get_max(f[L],f[R]));
 45         f[k]=get_max(f[k],Pair{mnf[R],mxf[L]});
 46     }
 47     else{
 48         if (mn[k]==mn[L]){
 49             mnf[k]=mnf[L];
 50             mxf[k]=get_max(mxf[L],mxg[R]);
 51             f[k]=get_max(f[k],get_max(f[L],g[R]));
 52             f[k]=get_max(f[k],Pair{mng[R],mxf[L]});
 53         }
 54         else{
 55             mnf[k]=get_min(mng[L],mnf[R]);
 56             mxf[k]=mxf[R];
 57             f[k]=get_max(f[k],get_max(g[L],f[R]));
 58             f[k]=get_max(f[k],Pair{mnf[R],mxg[L]});
 59         }
 60     }
 61 }
 62 void down(int k){
 63     upd(L,tag[k]),upd(R,tag[k]),tag[k]=0;
 64 }
 65 void build(int k,int l,int r){
 66     if (l==r){
 67         mng[k]=mxg[k]=mnf[k]=l,mxf[k]=0;
 68         return;
 69     }
 70     build(L,l,mid),build(R,mid+1,r),up(k);
 71 }
 72 void update(int k,int l,int r,int x){
 73     if (l==r){
 74         mng[k]=mxg[k]=mnf[k]=mxf[k]=0;
 75         return;
 76     }
 77     down(k);
 78     if (x<=mid)update(L,l,mid,x);
 79     else update(R,mid+1,r,x);
 80     up(k);
 81 }
 82 void update(int k,int l,int r,int x,int y,int z){
 83     if ((l>y)||(x>r))return;
 84     if ((x<=l)&&(r<=y)){
 85         upd(k,z);
 86         return;
 87     }
 88     down(k);
 89     update(L,l,mid,x,y,z);
 90     update(R,mid+1,r,x,y,z);
 91     up(k);
 92 }
 93 int main(){
 94     scanf("%d",&n);
 95     for(int i=1;i<=n;i++)scanf("%d%d",&a[i].first,&a[i].second);
 96     sort(a+1,a+n+1);
 97     for(int i=1;i<=n;i++)P[i]=a[i].second;
 98     build(1,1,n);
 99     for(int i=1;i<=(n>>1);i++){
100         ans=f[1];
101         if (mn[1])ans=g[1];
102         if (ans.get_val()>0){
103             x=ans.x,y=ans.y,sum+=ans.get_val();
104             update(1,1,n,x),update(1,1,n,y);
105             if (x1,1,n,x,y-1,1);
106             else update(1,1,n,y,x-1,-1);
107         }
108         printf("%lld\n",sum);
109     }
110     return 0;
111 }