Codechef November Chanllenge 2019 Div1 PrettyBox (贪心，线段树)

Posted on Edited on In

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++;
}