自动搬运

查看原文

来自洛谷，原作者为

	Miko35 阿玮你又在打电动喔，去看会书好不好

搬运于2025-08-24 22:26:59，当前版本为作者最后更新于2020-12-24 13:33:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意清晰思路简单码量少好评，卡常一万年 -9 差评。

成为了相同题目数量下罚时（可能）最长的队伍，顺便水一水题解。

似乎是目前的最优解，但估计马上就不是了（

题意很简单就是给一个序列， 每次询问给出 $d,p_1,p_2$，让你求这个玩意：

$$\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}\sum_{k=0}^{d-1}a_{p_1+d\cdot i+j}\times a_{p_2+d\cdot j+k} $$

(第一遍看成了 $a_{p_1}+d\cdot i+ja_{p_2}+d\cdot j+k$，然后愣了三秒（笑

首先是发现 $k$ 与 $a_{p_1+d\cdot i+j}$ 无关，然后就可以把式子变成这个形式：

$$\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}a_{p_1+d\cdot i+j}\times \sum_{k=0}^{d-1}a_{p_2+d\cdot j+k} $$

然后维护一个前缀和 $sum$，式子就变成了：

$$\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}a_{p_1+d\cdot i+j}\times (sum_{p2+d(j+1)-1}-sum_{p2+d\cdot j-1}) $$

然后做到这里发现很难再继续化简，爬回去重新读题，发现询问保证 $a$ 的下标在 $[1,n]$ 内，而不是多余的下标不予计算。

这样的话，当 $j=k=d-1$ 时，$a_{p_2+d\cdot j+k}=a_{p_2+d(d-1)+d-1}=a_{p_2+d^2}$；当 $j=k=0$ 时，$a_{p_2+d\cdot j+k}=a_{p_2}$。然后又保证了下标在 $[1,n]$ 内，所以 $p_2+d^2∈[1,n]$，$p_2∈[1,n]$。所以 $d∈[1,\sqrt{n-1}]$（所有数值为 $[1,{10}^9]$ 以内的整数）。

所以维护一个 $s_{i,j}$ 表示：

$$s_{i,j}=\sum_{k=0}^{\lfloor \frac{j-1}{i} \rfloor}a_{j-ki} $$

意义通俗一点说就是，从 $j$ 到 $1$ 的“隔 $i$ 个的”前缀和。

显然，这个 $s$ 递推的话就是：

$$s_{i,j}=\begin{cases} a_j&1 \leq j\leq i\\ s_{i,j-i}&i< j \leq n \end{cases}$$

这样的话这个式子继续化简，发现只有 $a_{p_1+d\cdot i+j}$ 含有 $i$ 这一项，用同样的套路把它提出来：

$$\sum_{j=0}^{d-1}(sum_{p_2+d(j+1)-1}-sum_{p_2+d\cdot j-1})\times \sum_{i=0}^{d-1}a_{p_1+d\cdot i+j} $$

然后用维护的 $s_{i,j}$ 改写一下：

$$\sum_{j=0}^{d-1}(sum_{p_2+d(j+1)-1}-sum_{p_2+d\cdot j-1})(s_{d,p_1+d(d-1)+j}-s_{d,p_1+j}+a_{p_1+j}) $$

这样单次询问直接暴力枚举 $j$，做到 $\mathcal{O}(d)$ 的复杂度。这种做法的时间复杂度为 $\mathcal{O}(m \sqrt{n})$，可以通过本题。

#include <bits/stdc++.h>
#define rgi register int
using namespace std;
namespace IO{
#define getchar() (P1_==P2_&&(P2_=(P1_=Ibuf)+fread(Ibuf,1,1<<21,stdin),P1_==P2_)?EOF:*P1_++)
#define putchar(c) (O-Obuf<8388608)?(*O++=c):(fwrite(Obuf,O-Obuf,1,stdout),O=Obuf,*O++=c)
	char Ibuf[8388608],*P1_=Ibuf,*P2_=Ibuf,Obuf[8388608],*O=Obuf;
	int f,ch,Onum[32],Ohd;long long K_;
	template<typename T>inline void read(T&x){
		x=f=ch=0;while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
		while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		f&&(x=-x);
	}
	template<typename T>inline void write(T x){
		if(x==0)return putchar('0'),void();
		if(x<0)putchar('-'),x=-x;
		while(x>0)K_=x/10,Onum[++Ohd]=(x-(K_<<1)-(K_<<3))^'0',x=K_;
		while(Ohd>0)putchar(Onum[Ohd]),--Ohd;
	}
	inline void _Exit0(){
		fwrite(Obuf,O-Obuf,1,stdout),exit(0);
	}
}using namespace IO;
int Block,n,m,p1,p2,d;
unsigned int a[200010],ans;
unsigned int s[450][200010],sum[200010];
int main(){
	read(n),Block=sqrt(n);
	for(rgi i=1;i<=n;++i)read(a[i]),sum[i]=sum[i-1]+a[i];
	for(rgi i=1;i<=Block;++i){
		for(rgi j=1;j<=i;++j)s[i][j]=a[j];
		for(rgi j=i+1;j<=n;++j)s[i][j]=s[i][j-i]+a[j];
	}
	read(m);
	for(rgi t=1;t<=m;++t){
		read(d),read(p1),read(p2),ans=0;
		for(rgi j=0;j<d;++j)ans+=(s[d][p1+(d-1)*d+j]-s[d][p1+j]+a[p1+j])*(sum[p2+d*(j+1)-1]-sum[p2+d*j-1]);
		write(ans),putchar('\n');
	}
	_Exit0();
}