POI - PA 2010 Round 2 Coins

翻譯:

給你n, k還有一個由R, O組成的長度n的序列。

找出區間[i, j]使得這個區間內O的個數是R的k倍，這個區間最長能多長

n, k <= 1,000,000


Sample Input:
15 3
RORROOROOROOORO



Sample Output:
8





solution:

這題跟之前USACO一題有異曲同工之感。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3274

定義f(i) = 1~i出現多少個R - (i/(k+1))

那麼會發現，若f(a) == f(b)則 [a+1, b]必為合法區間

排序 O(n lg n)或Hash O(n)就結束了。

蝴蝶作法雖然核心一樣不過細節完全不同，雖然一樣O(n lg n)