1921-F 题目大意
有一个长为\(n\)的序列\(a\),有\(q\)次询问,对于每次询问:
- 给定\(s,d,k\),请输出\(\sum_{i=1}^{k}i*a_{s+(i-1)*d}\)
Solution
根号分治。
- 对于\(d\ge \sqrt{n}\)的情况,直接暴力计算即可。
- 对于\(d\le \sqrt{n}\)的情况,这时需要预处理两个数组:\(pre,sum\),这里\(pre[d][i]\)表示公差为\(d\),最后一个元素为\(a[i]\)的数列的前缀和;\(sum[d][i]\)表示公差为\(d\)的数列,\(a[i]*\)其项数的前缀和,递推式子如下:
这时可以\(O(1)\)的计算出询问结果为\(sum[d][s+d*k]-sum[d][s]-(pre[d][s+d*k]-pre[d][s])*(s/d)\)。
根号算法结合了暴力计算以及数列求和的优点,真正实现了时空平衡,复杂度均为\(O(n\sqrt{n})\)。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
ll pre[400][N],sum[400][N];
void solve(){
int n,q;
cin>>n>>q;
int B=sqrt(n);
vector<ll> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int d=1;d<=B;d++){
for(int i=1;i<=n;i++){
pre[d][i+d]=pre[d][i]+a[i];
sum[d][i+d]=sum[d][i]+a[i]*(i/d+1);
}
}
while(q--){
int s,d,k;
cin>>s>>d>>k;
if(d<B){
cout<<sum[d][s+d*k]-sum[d][s]-(pre[d][s+d*k]-pre[d][s])*(s/d)<<" ";
}else{
ll res=0;
for(ll i=1;i<=k;i++){
res+=a[s+d*(i-1)]*i;
}
cout<<res<<" ";
}
}
cout<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
标签:pre,int,sum,CF,sqrt,1921,根号
From: https://www.cnblogs.com/fengxue-K/p/17984154