題目描述:
   給兩個長度為200,000的全排列a,b. 尋找整數(shù)k的個數(shù),使a的每個數(shù)加上k以后,是b的子序列.

算法分析:
   用線段樹維護哈希值...神思想...

   根據(jù)b數(shù)組構(gòu)造c數(shù)組,使c[b[i]] = i, 也就是大小為i的值在b中的位置.
   這樣的話,從k 到 k+n,就對應(yīng)了c中的一段連續(xù)區(qū)間. 這是一個匹配問題, 很容易想到多項式哈希.
   
   我一開始想的匹配方法是將c數(shù)組中的子串進行離散化去和a的變化數(shù)組進行匹配,發(fā)現(xiàn)需要用splay維護.... GGG...
   
   正解是,用c數(shù)組一段連續(xù)區(qū)間,對應(yīng)的b數(shù)組中的位置進行哈希直接和a數(shù)組匹配,這樣不需要涉及數(shù)值的離散化,位置的離散化直接用線段樹就和哈希值一塊維護了. Orz....

代碼 http://codeforces.ru/contest/213/submission/1997993