CFの過去問を埋めます！！(決意)

せっかくの機会なので、CFの過去問をガチで埋めていこうと思います。しばらく経つ頃にはきっと私はレッドコーダーになっていることでしょう。(現在Div1底辺)

昨日といた問題

103D
こういう手の問題で平方分割をするのは典型ですが、この問題はクエリ先読みが大事です。

#include<stdio.h>
#include<algorithm>
using namespace std;
int SQ=600;
int b[300000];
long long c[601][601];
long long ans[300000];
pair<pair<int,int> ,int> query[300000];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		query[i]=make_pair(make_pair(p-1,q),i);
	}
	std::sort(query,query+n);
	int at=a-1;
	for(int i=n-1;i>=0;i--){
		while(at>=query[i].first.first){
			for(int j=1;j<SQ;j++){
				c[j][at%j]+=b[at];
			}
			at--;
		}
		if(query[i].first.second<SQ){
			ans[query[i].second]=c[query[i].first.second][query[i].first.first%query[i].first.second];
		}else{
			for(int j=query[i].first.first;j<a;j+=query[i].first.second)ans[query[i].second]+=b[j];
		}
	}
	for(int i=0;i<n;i++)printf("%lld\n",ans[i]);
}