自动搬运

查看原文

来自洛谷，原作者为

	AKB48 None

搬运于2025-08-24 21:21:06，当前版本为作者最后更新于2013-10-02 20:15:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

引入相对差的概念。即a[i]表示第i个位置男生人数-女生人数的差值。

那么差值相等的两个位置之间的人数是满足男女相等的。

从此统计l[a[i]]和r[a[i]]。

特别要注意的是a[0]=0 统计的时候要把0的位置当做差为0的起点。