CodeForces 103D 分块处理-白红宇

CodeForces 103D 分块处理

阅读量：7114 次

发布时间：2019-06-28

本文共 1804 字，大约阅读时间需要 6 分钟。

题目链接：http://codeforces.com/problemset/problem/103/D

题意：给定一个长度为n的序列。然后q个询问。每个询问为(a,b),表示从序列第a项开始每b项的加和。

思路：2014集训队论文中的<<根号算法——不只是分块>>中提到这题。传统的数据结构比较擅长处理连续区间的询问。但是不擅长处理间隔位置的询问。考虑到分块。对于b>sqrt(n)的询问。我们暴力计算。可以发现b越大我们扫描的位置就会越小。最大扫描次数为O(n/sqrt(n))。然后对于b<sqrt(n)的。我们离线处理。以b为关键字来分组。询问中b相同的为一组。然后用预存部分和来计算。这样整体的时间复杂度为O(n*sqrt(n)).

#define _CRT_SECURE_NO_DEPRECATE#include
     
        #include
      
         #include
       
        #include
        
           #include
         
            #include
          
            #include
           
            #include
            
             #include
             
              #include
              using namespace std;typedef long long int LL;const int MAXN = 3*100000 + 10;int block, n, q, a[MAXN];LL ans[MAXN],sum[MAXN];struct Query{ int id, pos; Query(int _id = 0, int _pos = 0) :id(_id), pos(_pos){} };vector
               
                D[MAXN];void init(){ block = (int)sqrt(n + 0.5); for (int i = 1; i < MAXN; i++){ if (D[i].empty()){ continue; } if (i > block){ for (int j = 0; j < D[i].size(); j++){ LL res = 0; for (int k = D[i][j].pos; k <= n; k += i){ res += a[k]; } ans[D[i][j].id] = res; } } else{ memset(sum, 0, sizeof(sum)); for (int j = n; j > 0; j--){ sum[j] = a[j]+(j+i<=n?sum[i+j]:0); } for (int j = 0; j < D[i].size(); j++){ ans[D[i][j].id] = sum[D[i][j].pos]; } } D[i].clear(); }}int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); while (~scanf("%d", &n)){ for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); } scanf("%d", &q); for (int i = 1; i <= q; i++){ int pos, d; scanf("%d%d", &pos, &d); D[d].push_back(Query(i, pos)); //相同d的为一组 } init(); for (int i = 1; i <= q; i++){ printf("%lld\n", ans[i]); } }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}

转载于:https://www.cnblogs.com/kirito520/p/5933636.html

你可能感兴趣的文章