UOJ Logo peehs_moorhsum的博客

博客

关于胡搞的一道基础数据结构练习题

2016-09-02 20:38:14 By peehs_moorhsum

QS_Studio

先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亦可完成……

但是……它的名字不好!

评论

chenyuqi
前排%%%
indogent
前排%%%
yanQval
中排跪地%%%
chenyuqi
围观作者调试一小时 MarkDown O(∩_∩)O~
Drench
那一堆期望得分0分 不给暴力活路啊
WrongAnswer
一道防得分好题!
yanph2003
后排卒%%%
jobs
我只能说:卡暴力好题....
moorhsum
@peehs_moorhsum 同学你好呀
yanph2003
可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。