題目描述:
給兩個長度為200,000的全排列a,b. 尋找整數k的個數,使a的每個數加上k以后,是b的子序列.
算法分析:
用線段樹維護哈希值...神思想...
根據b數組構造c數組,使c[b[i]] = i, 也就是大小為i的值在b中的位置.
這樣的話,從k 到 k+n,就對應了c中的一段連續區間. 這是一個匹配問題, 很容易想到多項式哈希.
我一開始想的匹配方法是將c數組中的子串進行離散化去和a的變化數組進行匹配,發現需要用splay維護.... GGG...
正解是,用c數組一段連續區間,對應的b數組中的位置進行哈希直接和a數組匹配,這樣不需要涉及數值的離散化,位置的離散化直接用線段樹就和哈希值一塊維護了. Orz....
代碼
http://codeforces.ru/contest/213/submission/1997993
posted on 2012-08-10 22:54
西月弦 閱讀(480)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告