先Orz诸位大神为敬Orz
大家好,我是peehs_moorhsum(moorhsum)
我的同学是一个热爱学习的孩子,今天他想要学习数据结构技巧。
在看了一些博客学了一些姿势、A了UOJ上的基础数据结构练习题后,他想要再找一些题来练练手。于是我给他出了一道题。
内存:256MB | 时间限制:2s
- 题面
给定 $m$ 次整系数多项式函数 $f(x)$,支持以下操作:
操作 $1$:将 $a[l]$ 至 $a[r]$ 变为 $f(a[l])$ 至 $f(a[r])$
操作 $2$:询问区间 $a[L]$ 至 $a[R]$ 中所有元素之和
由于答案可能很大,只需输出模 $2016$ 的结果即可。
- 输入数据:
第一行一个正整数 $n$,下一行 $n$ 个正整数,表示 $a[1]$ ~ $a[n]$
第三行一个正整数 $m$,下一行 $m+1$ 个正整数,分别表示 $0$ 次项、$1$ 次项、……、$m$ 次项系数
第五行一个正整数 $q$,接下来每行三个正整数 $b$、$L$、$R$
若 $b = 1$ 表示执行操作 $1$,其中 $l = L$,$r = R$
若 $b = 2$ 表示询问 $a[L]$ 至 $a[R]$ 的和
- 输出数据:
对于每组询问,输出 $a[L]$ 至 $a[R]$ 的和
- 数据范围:
对于所有数据,满足 $m <= 10^5$,$a[1]$ 至 $a[n]$ 及所有次项系数均在 $int$ 范围之内
对于前50%的数据 满足 $1 <= n$、$q <= 10^5$ 且对于任意正整数x,y 有$gcd(x-y,2016)=gcd((f(x) - f(y)), 2016)$
对于后50%的数据 满足 $n <= 10^6$、$q <= 1000$
作为一个不怎么熟练的初学者,他想了好久都没做出来。而我又回家睡觉去了,一时间联系不上。
于是他就在网站上寻(pian)求(dian)帮(ji)助(lv),得到了一定的关注。
我醒来之后,打算写写题解,以终止他的钓鱼。然后就有了这篇博(guan)文(shui)。
// 这理由都想给自己满分
算法一
暴力模拟 时间复杂度:O(nmq)
期望得分:0分
算法二
我们发现,由于f(x)为多项式函数,所以对于y mod 2016 = x,f(y) mod 2016 = f(x) mod 2016
于是我们可以维护f(0) ~ f(2015) mod 2016的余数,再进行暴力模拟
时间复杂度:O(2016m + nq)
期望得分:0分
算法三
将2016分解因数,得2016 = 32 * 7 * 9
又32、9、7两两互素,于是只需求出结果 mod 32、9、7的余数即可得出答案
可以对算法二执行优化,维护f(0) ~ f(31) mod 32的值,f(0) ~ f(7) mod 7的值,f(0) ~ f(8) mod 9的值,再进行暴力搜索即可
时间复杂度:O(48m + nq)
期望得分:0分
算法四
在算法三中,已经解决了预处理的问题。
现在,只要维护一个数据结构使得可以快速进行区间操作。
容易看出,在前50%的数据中,对于任何两个模2016不同余的数x,y,f(x)和f(y)模32,7,9均不同余
可以用分块维护mod 32余0~31的链表(按数组中位置从小到大),mod 9余0~8的链表(按数组中位置从小到大),mod 7余0~6的链表(按数组中位置从小到大)即可。
时间复杂度:O(48m + 48q√n)
期望得分:50分
算法五
对于算法四,亦可使用Splay进行维护
时间复杂度:O(48m + 48*q*log n)
期望得分:50分
算法六(前方玄学请注意)
算法五已经可以解决前50%的数据
现在只需考虑后50%的数据即可
在算法五当中,将无法立即添加的Splay置于一边,称为“累赘Splay”
当累赘Splay个数达到√(32 * n * logn)或√(7 * n * logn)或√(9 * n * logn)时,将累赘Splay合并
均摊复杂度为每次(√32 + √7 + √9) * √(log n*n)
在这种复杂度下,已经可以通过此题
时间复杂度:O(48m + (√32 + √7 + √9) * √(log n*n) * q)
空间复杂度:O(n)
期望得分:100分
此题好像可以通过改进算法四AC……没细想
第一篇博文,水一些请见谅O(∩_∩)O~
(在bzoj上,peehs_moorhsum是我同学……moorhsum是我……你问我究竟是谁,我是神秘的人民群众O(∩_∩)O)
附录:在写完博客之后,心情大好
于是当时就写了两行标程,然后发现出不出来数据……
定睛一看,发现前50%的数据根本不可能,又改了改
再看了看,发现在博客里的复杂度多了一个48……然后计算下来还没有暴力快……
2333~
UPD: 这道题用线段树+次数开根预处理可以轻松完成
但线段树太难写了对不对
不过骗到了不少评论……蒟蒻很是开心O(∩_∩)O~
(注:如果此题增加删点,插点操作,用splay亦可完成……
但是……它的名字不好!