Educational Codeforces Round 102

倒序开的题,十分钟想出G,然后写了一个多小时
分别经历了(O(n^4),O(n^3),O(nVlogV),O(n^2logn))...

G

(f_i)为目前在第(i)点的答案
如果中间经历一段长度为(len_1)的,块增加序列(就是序列({a})在干的事)
(g_i)表示经历完后第(i)点的答案

那么我们有(g_i=sumlimits_{jle i}f_j{len_1choose i-j})

如果中间经历一段长度为(len_2)的,块减少序列(就是序列({b})在干的事)
(h_i)表示经历完后第(i)点的答案

那么我们有(h_i=sumlimits_{jge i}g_j{len2choose j-i})

[egin{aligned} h_i&=sumlimits_{jge i}g_j{len_2choose j-i}\ &=sumlimits_{jge i}{len_2choose j-i}sumlimits_{kle j}f_k{len_1choose j-k}\ &=sumlimits_{k}f_ksumlimits_{jge i,jge k}{len_1choose j-k}{len_2choose j-i}\ &=sumlimits_{k}f_k {len_1+len_2choose j-i+k}\ end{aligned}]

显然后面这个是个卷积形式
直接卷过不去,因为(len_1+len_2)(O(10^5))级别的
由于题目中(|a_i-b_i|le 5)的条件
(h_i)的这个(i)下标的是(O(n))级别的,所以右边保留(O(n))项即可

时间复杂度(O(n^2logn))

原文地址:https://www.cnblogs.com/Grice/p/14281971.html