（分块暴力）Time to Raid Cowavans CodeForces

题意

给你一段长度为n(1 ≤ n ≤ 3·1e5)的序列，m (1 ≤ p ≤ 3·1e5)个询问，每次询问a,a+b,a+2b+...<=n的和

思路

一开始一直想也想不到怎么分，去维护哪些信息，看了题解才知道其实分块不仅仅可以将一列序列分块，还可以将数据进行分块，下面讨论具体做法

首先这道题不是在线询问，可以离线做，先读入所有的询问，将询问从小到大排序
①当b＜√n时，对于每一个b我们可以预处理出这样的一个数组sum[i]，就是以i为起点间隔为b的序列和（可以用一个简单的dp求出来），然后O(1)查询，这么做的好处就是如果不同的询问a不同，b相同，经过排序我们就可以直接使用这个sum数组,时间复杂度为O(n√n)。
②当b≥√n时，直接暴力求和，时间复杂度为O(m√n)
所以总时间复杂度为O((m+n)√n)

#include<iostream>

#include<algorithm>

#include<cmath>

 using namespace std;

 const int maxn=3e5+;

 typedef long long ll;

 ll a[maxn];

 struct node{

     int a,b,id;

     bool operator<(const node &s) const

     {

         return b<s.b;

     }

 }b[maxn];

 ll ans[maxn];

 ll sum_b[maxn];

 int main()

 {

     int n,m;

     scanf("%d",&n);

     int bl=sqrt(n);

     for(int i=;i<=n;i++)

         scanf("%I64d",&a[i]);

     scanf("%d",&m);

     for(int i=;i<=m;i++){

         b[i].id=i;

         scanf("%d%d",&b[i].a,&b[i].b);

     }

     sort(b+,b++m);

     b[].b=;

    for(int i=;i<=m;i++){

        if(b[i].b>=bl){

            ans[b[i].id]=;

            for(int k=b[i].a;k<=n;k+=b[i].b)

                ans[b[i].id]+=a[k];

        }

        else{

            if(b[i].b==b[i-].b){

                ans[b[i].id]=sum_b[b[i].a];

            }

            else{

                for(int j=n;j>=;j--)

                    if(j+b[i].b>n)

                        sum_b[j]=a[j];

                    else

                        sum_b[j]=sum_b[j+b[i].b]+a[j];

                ans[b[i].id]=sum_b[b[i].a];

            }

        }

    }

    for(int i=;i<=m;i++)

        printf("%I64d\n",ans[i]);

    return ;

}

巴特西

（分块暴力）Time to Raid Cowavans CodeForces - 103D

最新文章

热门文章