柒葉灬 的博客

柒葉灬 的博客

「BalkanOI 2018 Day1」Election 题解

posted on 2019-04-07 21:09:30 | under 题解 |

倍增解法

可能講的不會很清楚。


設 $'C'$ 為 $1$ , $'T'$ 為 $-1$ 。

一段合法的串滿足:

1.所有前綴 $>=0$ 。

2.所有後綴 $>=0$ 。


設 $1$ 到 $i$ 的和為 $sum[i]$ (即前綴)

一段合法的串滿足:

1.所有的 $sum[i]>=0 (i∈[1,n])$ 。(每個前綴和 $>=0$ )

2.所有的 $sum[n]-sum[i]>=0 (i∈[1,n])$ 。(每個後綴和 $>=0$ )


修改操作造成的影響:當修改了 $x$ 位置的時候, $sum[i]++;(i∈[x,n])$ 。


1.使所有的 $sum[i]>=0$ 的贡献显然是 $max\{-sum[i],(i∈[0,n])\}$


接下來需要使所有的 $sum[i]<=sum[n],(i∈[1,n])$

2.这时候肯定会有一个最大的 $sum'[i]$ (操作后),把 $sum'[n]$ 加到 $sum'[i]$ 的贡献就是 $sum'[i]-sum'[n]$

这个最大的 $sum'[i]$ 就是: $max\{sum[j]-sum[i],(i,j∈[0,n],i<j)\}$

因为对于每一个 $sum'[i]=sum[i]-min\{sum[j],j∈[0,i)\}$

(注意:一定是右边的减左边的)

而 $sum'[n]$ 就是 $sum[n]+max\{-sum[i],(i∈[0,n])\}$

答案就是 $2$ 个操作加起来就行了。


结论:

最后化简可以直接得到: $ans=max\{sum[j]-sum[i],(i,j∈[0,n],i<j)\}-sum[n]$


离线可以做到 $O(n)$