線段樹 + 字元串Hash - Codeforces 580E

  Kefa and Watch

Problem's Link

Mean: 

給你一個長度為n的字元串s，有兩種操作：

1 L R C : 把s[l,r]全部變為c;

2 L R d : 詢問s[l,r]是否是周期為d的重複串。

analyse:

n最大為1e5，且m+k最大也為1e5，這就要求操作1和操作2都要采用logn的算法，是以用線段樹.

對于更新操作，使用區間更新就可解決。

主要是如何在logn的時間内完成詢問操作.

我們采用線段樹維護hash值的方法.

結合于類似KMP的性質，我們發現，字元串[l,r]有長度為w的循環節，隻需要使得[l,r-w]=[l+w,r]即可。證明過程看這裡

這題的hash不同于普通的字元串hash，因為涉及到動态修改，是以需要預先處理出所有的base，在修改的時候直接用.

Time complexity: O(N)

view code

      |  Github |  Facebook  |  Twitter |