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(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#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\n",ans+=res.Val());
		Upd(1,1,n,res.x,1),Upd(1,1,n,res.y,-1);
		i++;
	}
	while(i<=n/2) printf("%lld\n",ans),i++;
}