题解 P1114 【“非常男女”计划】

AKB48 · 2013-10-02 20:15:18 · 题解

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

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

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

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