「USACO07MAR」Balance Lineup

题意：FJ 决定将一些奶牛（也许全部）摄入其家庭画像中，为方便取像， FJ 已安排所有 $N$ 头奶牛在一条直线。每头奶牛用 $x$ 坐标（范围：$0\sim 10 ^9$）表示其位置，并用 $0$ 或 $1$ 表示其品种。多年来， FJ 总是做一些别出心裁的事情，当然这项活动也不例外。他决定在他的照片中将只有一部分奶牛，并且照片必须在“平衡” 。所谓“平衡”，就是指连续的一组奶牛中，包含的两种品种数量是一样的，即 $0$ 和 $1$ 的个数应该是相等的。那么请你来帮助 FJ 确定相片的最大宽度。注意，在 $x$ 数轴上没有两个奶牛共用相同的 $x$ 坐标。

这道题要转个弯，然后就很简单。

首先一想到就是 DP，我们用 $sum[i]$ 代表从一开始到现在 $1$ 的个数和 $0$ 的个数的差，当这个差值为 $0$ 时显然 $dis[i]-dis[1]$ (将 $dis$ 从小到大排序后)就是答案。

怎么求这个差值呢？我们只需把 $0$ 看作 $-1$，然后求个前缀和，得到的就是差值。

但是怎么求一个子串内的 $1$ 和 $0$ 的个数呢？例如这个数据：

坐标	$4$	$10$	$11$	$12$	$13$	$22$	$25$
类型	$1$	$1$	$0$	$1$	$0$	$1$	$1$
$sum$	$1$	$2$	$1$	$2$	$1$	$2$	$3$

很容易可以发现，当这个子串为 $[dis[l],dis[r]]$ 时，如果 $sum[dis[l-1]]=sum[dis[r]]$ 时，那么这个子串内的 $1$ 和 $0$ 就相同。

证明也很简单，由于 $sum[dis[l-1]]=sum[dis[r]]$，说明其内部的和为 $0$，说明 $-1$ 的个数和 $1$ 的个数一样多，即 $0$ 类型和 $1$ 类型一样多，证毕。

于是我们用一个 vector 数组，把每个 $sum$ 值对应的下表编号存进来，每次找这个值对应的最大坐标和最小坐标即可求出(由于 $sum$ 值可能为负，需要平移下标)。

最后注意如果最大下标和最小下标相同，说明只是一个数，需要特判。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=200000;
int n,sum[201010],minn=1e9,maxx=-1e9,ans=-1e9;
struct node
{
	int p;
	int d;
}a[201010];
vector<int> s[401010];
int cmp(node x,node y)
{
	return x.d<y.d;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].p,&a[i].d);
		if(!a[i].p)
			a[i].p=-1;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+a[i].p;
		s[sum[i]+maxn].push_back(i);
		minn=min(minn,sum[i]);
		maxx=max(maxx,sum[i]);
	}
	for(int i=minn;i<=maxx;i++)
	{
		int maxd=-1e9;
		int mind=1e9;
		for(int j=0;j<s[i+maxn].size();j++)
		{
			maxd=max(maxd,s[i+maxn][j]);
			mind=min(mind,s[i+maxn][j]);
		}
		if(maxd==mind)
			mind=maxd-1;
		ans=max(ans,a[maxd].d-a[mind+1].d);
	}
	printf("%d",ans);
	return 0;
}