题目描述:
给两个长度为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
西月弦 阅读(476)
评论(0) 编辑 收藏 引用 所属分类:
解题报告