题意：一共有n头牛， 每头牛有一个重量，m次询问， 每次询问有a，b 求出 a，a+b，a+2b的牛的重量和。
题解：对于m次询问，b>sqrt(n)的时候我们直接把结果跑出来，当b<sqrt(n)的时候我们离线询问，算出所有一个b的任意一起点的值。 复杂度为 q*sqrt(n);
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define max3(a,b,c) max(a,max(b,c)) 12 #define min3(a,b,c) min(a,min(b,c)) 13 #define Show(x) cout << x << ' '; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const LL mod = (int)1e9+7; 17 const int N = 3e5 + 100; 18 int n, m, k, p; 19 int w[N]; 20 LL tot[N]; 21 LL ans[N]; 22 struct Node{ 23 int a, b, id; 24 }q[N]; 25 bool cmp(Node x1, Node x2){ 26 return x1.b < x2.b; 27 } 28 int main(){ 29 scanf("%d", &n); 30 for(int i = 1; i <= n; i++) scanf("%d", &w[i]); 31 scanf("%d", &p); 32 k = sqrt(n); 33 int t = 0, a, b; 34 LL tmp; 35 for(int i = 1; i <= p; i++){ 36 scanf("%d%d", &a, &b); 37 if(b >= k){ 38 tmp = 0; 39 for(int i = a; i <= n; i += b) 40 tmp += w[i]; 41 ans[i] = tmp; 42 } 43 else { 44 q[t].a = a; 45 q[t].b = b; 46 q[t].id = i; 47 t++; 48 } 49 } 50 sort(q,q+t,cmp); 51 for(int i = 0; i < t; i++){ 52 if(i == 0 || q[i].b != q[i-1].b){ 53 b = q[i].b; 54 for(int i = n; i >= 1; i--){ 55 if(i+b > n) tot[i] = w[i]; 56 else tot[i] = tot[i+b] + w[i]; 57 } 58 } 59 ans[q[i].id] = tot[q[i].a]; 60 } 61 for(int i = 1; i <= p; i++){ 62 printf("%I64d ", ans[i]); 63 } 64 return 0; 65 }