【CF103D】Time to Raid Cowavans

题目

题目链接：https://codeforces.com/problemset/problem/103/D
给一个序列 (a) ，(m) 次询问，每次询问给出 (t, k) 。求 (a_t + a_{t+k}+a_{t+2k}+cdots+a_{t+pk}) 其中 (t+pk leq n) 且 (t+(p+1)k > n)。
(n,m leq 300000,a_i leq 10^9)。

思路

一眼题吧。
考虑一个阈值 (t)，对于 (kleq t) 的询问，(O(tn)) 预处理出来然后 (O(1)) 回答，对于 (k>t) 的询问，直接 (O(frac{n}{t})) 回答。
取 (t=sqrt{n}approx 350)，时间复杂度为 (O(msqrt{n}))。把询问离线一下就可以做到空间复杂度 (O(n))。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=301000,M=550;
int n,m,a[N];
ll sum[N],ans[N];

struct node
{
	int x,y,id;
}b[N];

bool cmp(node x,node y)
{
	return x.y<y.y;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&b[i].x,&b[i].y);
		b[i].id=i;
	}
	sort(b+1,b+1+m,cmp);
	for (int i=1;i<=m;i++)
		if (b[i].y<=M)
		{
			if (b[i].y!=b[i-1].y)
				for (int j=n;j>=1;j--)
					sum[j]=sum[j+b[i].y]+a[j];
			ans[b[i].id]=sum[b[i].x];
		}
		else
		{
			for (int j=b[i].x;j<=n;j+=b[i].y)
				ans[b[i].id]+=a[j];
		}
	for (int i=1;i<=m;i++)
		printf("%lld
",ans[i]);
	return 0;
}