「NOIP模拟赛」小奇的数列

2015年9月13日3,1589

「题目背景」

小奇总是在数学课上思考奇怪的问题。

 

「问题描述」

给定一个长度为n的数列,以及m次询问,每次给出三个数l,r和P,询问 (a[l’] + a[l’+1] + … + a[r’]) mod P的最小值。

其中l <= l’ <= r’ <= r。

 

即模意义下的区间子串和最小值。

 

「输入格式」

第一行包含两个正整数n和m,表示数列的长度和询问的个数。
第二行为n个整数,为a[1]..a[n]。
接下来m行,每行三个数l,r和P,代表一次询问。

 

「输出格式」

对于每次询问,输出一行一个整数表示要求的结果

 

「样例输入」

4 2

8 15 9 9

1 3 10

1 4 17

 

「样例输出」

2

1

 

「数据范围」

对于20%的数据 n<=100,m<=100,p<=200

对于40%的数据 n<=200,m<=1000,p<=500

对于70%的数据 n<=100000,m<=10000,p<=200

对于100%的数据 n<=500000,m<=10000,p<=500,1<=a[i]<=10^9

 

题解

对于20%的数据,最暴力的做法,在区间内枚举子串,暴力求和取模,最后得出最小值,复杂度m*n^3

对于40%的数据,算法1的区间求和改用前缀和相减,复杂度m*n^2

接下来,思考一下抽屉原理,如果询问的区间长度大等p的话,一定有两个前缀和相减等于0,那么直接输出0即可

对于70%的数据,把所有长度大等p的区间特判,其余暴力,复杂度m*p^2

考虑生日悖论,数列如果是随机生成的,找到2个前缀和相同的就返回0,期望复杂度为m*p

由于第10组数据是随机生成的,所以算法3可以通过8个测试点

对于100%的数据,使用平衡树来寻找某个数的前驱,复杂度为m*p*logp(可能高于noip难度),需要手写treap,splay或替罪羊树等。set由于常数较大,实测和暴力结果一样。

 

说点什么

提醒
avatar
Palain
Palain

其实这题用树状数组维护权值直接艹过去就好了……

cyy489
cyy489

tyvj,vijos……找以下就行了。

早开的晚霞

这道题在哪交呢?

zld3794955

可以尝试离线黑科技。。方便很多呢2333

蒻

您是不甘心pkusc这题被暴力艹了么。。。
丧心病狂