Codechef November Chanllenge 2019 Div1 PrettyBox (贪心,线段树)
前言:这篇文章主要讲如何用线段树优化贪心,关于贪心的证明建议看官方题解
贪心思路:
首先肯定要按照((S_i,P_i))递增的顺序排序
每次选取两个点,一个标记为左括号,权值为(-P_i),一个标记为右括号,权值为(P_i),显然只要是一个合法的括号序列即可
题解证明了在不断增加括号时,不会出现一个位置的括号情况改变
现在我们的贪心问题就在于怎样找到一对最优的括号,注意每次选出的 两个括号之间并不一定匹配
为了便于描述,把左括号看做1,右括号看做-1,一个合法括号序列满足任何一个前缀和(ge 0)
考虑什么样的情况可以放置左右括号,设分别放在(x,y)
1.(x<y)显然合法
2.(x>y)时,如果存在一个括号对,将((x,y))包含在一起,即((y,x))这一段区间不跨过一个前缀和为(0)的位置
如果把序列 看做 由一段段 前缀和为0的位置 分割开来的 一个个联通块,似乎比较好理解
也就是块内随意选,之间只能由小到大匹配
接下来考虑用线段树维护这样的块的信息,下面只讨论(x>y)的情况
由于线段树每个结点统计区间([l,r])的信息,所以实际上块之间的间隔并不为0
设([l,r])中最小的前缀和为(Min)(是指从(l)开始的前缀和)
不妨统计([l,r])中不跨过一个前缀和为(Min)的位置的答案(Ans),以及跨过的答案(Ans2)
合并两个区间时,需要找到
左区间中 右边连续的一段不跨过最小值 的最大权值 (R)
右区间中 左边连续的一段不跨过最小值 的最小权值 (L)
以及任意的最小值最大值(mi,ma)
然后按照(Min)的权值大小关系 ,判断这4种权值的合并应该被分配到(Ans)还是(Ans2)
合并(L,R)时注意(L)优先看左儿子,(R)优先看右儿子,具体实现看代码中的(Up)函数
每次存下答案找到最优配对后,在序列上对应放置-1,1单点修改即可,复杂度为(O(nlog n))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ a=min(a,b); }
template <class T> inline void cmax(T &a,T b){ a=max(a,b); }
char IO;
int rd(){
int s=0,f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=2e5+10,M=N<<2;
int n;
Pii T[N];
int A[N];
int S[M]; // 区间和
int Min[M]; // 前缀最小值
struct Node{
int x;
Node(){}
Node(int x):x(x){}
int operator < (const Node __) const { return A[x]<A[__.x]; }
} L[M],R[M]; // 左最小,右最大 , 记录的是不跨过最小值的权值
Node mi[M],ma[M]; // 区间最大最小,没有限制
struct Pair{
int x,y;
Pair(){}
Pair(int x,int y):x(x),y(y){}
Pair(Node x,Node y):x(x.x),y(y.x){}
int Val() const { return A[y]-A[x]; }
int operator < (const Pair __) const { return Val()<__.Val(); }
} Ans[M],Ans2[M]; // 不跨过最小值的答案以及x<y的答案,包含最小值的答案
// 区间答案
void Up(int p){
S[p]=S[p<<1]+S[p<<1|1];
Min[p]=min(Min[p<<1],S[p<<1]+Min[p<<1|1]);
mi[p]=min(mi[p<<1],mi[p<<1|1]),ma[p]=max(ma[p<<1],ma[p<<1|1]);
Ans[p]=max(Ans[p<<1],Ans[p<<1|1]);
Ans2[p]=Pair(mi[p<<1|1],ma[p<<1]);
cmax(Ans2[p],Ans2[p<<1]);
cmax(Ans2[p],Ans2[p<<1|1]);
cmax(Ans[p],Pair(mi[p<<1],ma[p<<1|1]));
Ans[p]=max(Ans[p],Pair(L[p<<1|1],R[p<<1]));
if(Min[p<<1]!=Min[p]) {
cmax(Ans[p],Ans2[p<<1]);
cmax(Ans[p],Pair(L[p<<1|1],ma[p<<1]));
L[p]=min(mi[p<<1],L[p<<1|1]);
} else {
L[p]=L[p<<1];
}
if(S[p<<1]+Min[p<<1|1]!=Min[p]) {
cmax(Ans[p],Ans2[p<<1|1]);
cmax(Ans[p],Pair(mi[p<<1|1],R[p<<1]));
R[p]=max(R[p<<1],ma[p<<1|1]);
} else {
R[p]=R[p<<1|1];
}
}
void Build(int p,int l,int r){
if(l==r) {
S[p]=Min[p]=0;
L[p]=n+1,R[p]=n+2;
mi[p]=ma[p]=l;
Ans[p]=Ans2[p]=Pair(n+1,n+2);
return;
}
int mid=(l+r)>>1;
Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
Up(p);
}
void Upd(int p,int l,int r,int x,int k) {
if(l==r) {
S[p]=Min[p]=k;
L[p]=n+1,R[p]=n+2;
mi[p]=n+1,ma[p]=n+2;
Ans[p]=Ans2[p]=Pair(n+1,n+2);
return;
}
int mid=(l+r)>>1;
x<=mid?Upd(p<<1,l,mid,x,k):Upd(p<<1|1,mid+1,r,x,k);
Up(p);
}
int main(){
rep(i,1,n=rd()) T[i].first=rd(),T[i].second=rd();
sort(T+1,T+n+1);
rep(i,1,n) A[i]=T[i].second;
A[n+1]=1e9+10,A[n+2]=-1e9-10;
ll ans=0;
int i=1;
Build(1,1,n);
while(i<=n/2) {
Pair res=Ans[1];
if(res.Val()<=0) break;
printf("%lld
",ans+=res.Val());
Upd(1,1,n,res.x,1),Upd(1,1,n,res.y,-1);
i++;
}
while(i<=n/2) printf("%lld
",ans),i++;
}