Codeforces Round #780 (Div. 3)F2 Promising String (hard version)题解 （二分+树状数组）

题目链接：F2. Promising String (hard version)
题解：我们可以发现某一段符合的条件一定是‘-’比‘‘+’多出3的整数倍，因为只要‘-’比‘+’多，就一定存在连续的’--‘，此时我们就可以将其变成’+‘，那么相对’+‘‘而言’-‘的数量就减少了3，那么就一定能使得最终’+‘和’-‘的数量相等，我们可以维护从起始点到每个位置时，每个位置上’-‘比’+‘多多少个，即为sum[i]，若某两个位置i，j（isum[i]&&(sum[j]-sum[i])%3==0，这就是一个经典二维偏序问题了，那具体怎么处理呢，我们可以枚举每个位置j看看有多少个i满足条件，这就是F1，但F2数据太大，我们可以利用树状数组，每次将所有sum排序，对于当前sum我们可以二分查找有多少个位置比自己小，再利用树状数组即可实现查找位置小于i并且sum也小于sum[i]的个数，因为要查找的数得满足对3取余和当前相同，所有我们可以开二维树状数组，将对3取余的结果不同的数分开存即可
不懂和细节见代码

Codeforces Round #780 (Div. 3)F2 Promising String (hard version)题解 （二分+树状数组）最先出现在Python成神之路。