「广州集训 Day2」瓜分领土 - 分类讨论+线段树

题目大意

石头、剪刀和布闹别扭了，他们要分家。
他们生活在一个离散的一维空间里，简单点说，他们拥有在一条直线上的N间房子，每间房子有一个风水值（有正有负）。
然后，他们决定将这$N$间房子分成非空的三个连续段，从左到右数，第一段的房子全部属于石头，第二段的房子全部属于剪刀，第三段的房子全部属于布。
由于他们希望公平，并且又由于剪刀是他们的老大哥，他们决定根据这些条件制定了一个评判标准：
设石头拥有的房子的风水值和为$a$，剪刀拥有的房子的风水值和为$b$，布拥有的房子的风水值和为$c$，剪刀拥有$n$间房子。
那么通过给定一个参数$x$。
那么，这种分配的合理值就是$max(a,b,c)-min(a,b,c)+x\times n$.
合理值越小，表示这种分配越合理。
因此，我们现在就是要求出这个最小的合理值。

---

题目分析

为了方便叙述，规定以下字母：
$a,b,c$与原题描述相同。
$x,y$分别表示三者的分界线，如图：

原题中的$x$使用$X$代替。
$sum[]$表示风水值前缀和。

这道题贼厉害的，若风水值全是非负数，那么可以枚举第一个分界点，然后三分查找第二个分界点即可。
然而风水值可能有负，因此前缀和不一定单调，就有问题了。

不妨讨论$6$种情况，将$max(a,b,c)-min(a,b,c)+x\times n$拆开。

在本处只讨论$a\ge b\ge c$这一种情况，其余5种情况请自行推(bao)导(zha)（本人推了1张/2页草稿纸）。

当$a\ge b\ge c$时，用前缀和表示即为：

$$sum[x]\ge sum[y]-sum[x]\ge sum[n]-sum[y]$$

拆开化简得到：

$$sum[y]\le 2sum[x]$$ $$sum[y]\ge \frac{sum[n]+sum[x]}{2}$$

不难发现，$y$合法的位置在$sum$的值域中是一段连续的区间。
因此我们可以对$sum$进行排序，二分出这段连续的区间的断点。

这样我们就可以确定$y$的合法区间，如何统计答案呢。
此时的合理值为：

$$sum[x]-(sum[n]-sum[y])+X(y-x)$$

化简得到：

$$-sum[n]+sum[x]-Xx+(sum[y]+Xy)$$

我们可以枚举$x$，在线段树中查询$sum[y]+Xy$的最小值。

合并刚刚的限制条件与统计答案的信息，不难发现当$a\ge b\ge c$时，我们可以以$sum[y]$为下标，以$sum[y]+Xy$为值建立线段树。

具体的方案是，从大到小枚举$x$，将$y=x+1$的信息插入线段树，然后二分找到区间，在线段树中找到区间最小值。

---

细节

在上述推导二分区间时，出现了下面的式子：

$$sum[y]\ge \frac{sum[n]+sum[x]}{2}$$

因为普通的除以$2$会向下取整，因此可能将区间拓宽。
所以对于下界带除法的应向上取整。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=100005;
struct Tree {
	int left,right;
	LL min;
	Tree(int l=0,int r=0,LL m=LLONG_MAX/2):left(l),right(r),min(m) {}
};
struct Segment_Tree {
	Tree tree[maxn*4];
	#define ls index<<1
	#define rs index<<1|1
	void build(int index,int Left,int Right) {
		tree[index]=Tree(Left,Right);
		if(Left==Right)return;
		int mid=(Left+Right)>>1;
		build(ls,Left,mid);
		build(rs,mid+1,Right);
	}
	void push_up(int index) {
		tree[index].min=min(tree[ls].min,tree[rs].min);
	}
	void modify(int index,int target,LL v) {
		if(target>tree[index].right||target<tree[index].left)return;
		if(tree[index].left==tree[index].right) {
			tree[index].min=min(tree[index].min,v);
			return;
		}
		modify(ls,target,v);
		modify(rs,target,v);
		push_up(index);
	}
	LL query(int index,int Left,int Right) {
		if(Left>tree[index].right||Right<tree[index].left)return LLONG_MAX/2;
		if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].min;
		return min(query(ls,Left,Right),query(rs,Left,Right));
	}
} st[7];
int n;
LL x,sum[maxn],sum2[maxn],ans=LLONG_MAX;
pair<LL,LL> bound(int pos,int id) {
	LL up,down;
	if(id==1) {
		down=ceil((sum[n]+sum[pos])/2.0);
		up=2*sum[pos];
	}
	if(id==2) {
		down=sum[n]-sum[pos];
		up=(sum[n]+sum[pos])/2.0;
	}
	if(id==3) {
		down=ceil((sum[n]+sum[pos])/2.0);
		up=sum[n]-sum[pos];
	}
	if(id==4) {
		down=max(2*sum[pos],sum[n]-sum[pos]);
		up=1e17;
	}
	if(id==5) {
		down=-1e17;
		up=min(2*sum[pos],sum[n]-sum[pos]); 
	}
	if(id==6) {
		down=2*sum[pos];
		up=(sum[n]+sum[pos])/2.0;
	}
	return make_pair(down,up);
}
LL segment_val(int pos,int id) {
	if(id==1)return sum[pos]+x*pos;   //abc
	if(id==2)return x*pos-sum[pos];   //acb
	if(id==3)return sum[pos]+x*pos;   //bca
	if(id==4)return 2*sum[pos]+x*pos; //bac
	if(id==5)return x*pos-2*sum[pos]; //cab
	if(id==6)return x*pos-sum[pos];   //cba
}
LL get_ans(int pos,int id) {
	if(id==1)return sum[pos]-sum[n]-x*pos;
	if(id==2)return 2*sum[pos]-x*pos;
	if(id==3)return -2*sum[pos]-x*pos;
	if(id==4)return -sum[pos]-x*pos-sum[n];
	if(id==5)return sum[n]+sum[pos]-x*pos;
	if(id==6)return sum[n]-sum[pos]-x*pos;
}
void Solve(int pos,int id) {
	pair<LL,LL> tmp=bound(pos,id);
	LL down=tmp.first,up=tmp.second;
	int l=lower_bound(sum2+1,sum2+n+1,down)-sum2,r=upper_bound(sum2+1,sum2+n+1,up)-sum2-1;
	if(l>r)return;
	ans=min(ans,get_ans(pos,id)+st[id].query(1,l,r));
}
struct number {
	LL s;
	int id;
	bool operator < (const number& b) const {
		return s<b.s;
	}
} a[maxn];
int M[maxn];
int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++) {
		sum[i]=a[i].s=a[i-1].s+Get_Int();
		a[i].id=i;
	}
	x=Get_Int();
	sort(a+1,a+n+1);
	for(int i=1; i<=n; i++)M[a[i].id]=i,sum2[i]=a[i].s;
	for(int i=1; i<=6; i++)st[i].build(1,1,n);
	for(int i=n-2; i>=1; i--)
		for(int j=1; j<=6; j++) {
			st[j].modify(1,M[i+1],segment_val(i+1,j));
			Solve(i,j);
		}
	printf("%lld\n",ans);
	return 0;
}