Codeforces103D - Time to Raid Cowavans

Portal

Description

给出长度为\(n(n\leq3\times10^5)\)的序列\(\{a_n\}\)，进行\(q(q\leq3\times10^5)\)次询问：给出\(x,y\)，求\(\sum_{i=x,i+=y}^n a_i\)。

Solution

将询问离线，按\(y\)排序。

对于\(y<\sqrt n\)，对于每个\(y\)计算sum[i]表示\(x=i\)时的答案。计算sum[i]复杂度为\(O(n)\)，每次询问为\(O(1)\)，对于\(\sqrt n\)个\(y\)总复杂度为\(O(n\sqrt n)\)。

对于\(y>\sqrt n\)，直接循环计算\(\sum_{i=x,i+=y}^n a_i\)。每次询问复杂度为\(O(\sqrt n)\)，总复杂度为\(O(m\sqrt n)\)。

Code

//Time to Raid Cowavans

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long lint;

inline char gc()

{

    static char now[1<<16],*S,*T;

    if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}

    return *S++;

}

inline int read()

{

    int x=0; char ch=gc();

    while(ch<'0'||'9'<ch) ch=gc();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();

    return x;

}

int const N=3e5+1000;

int n,m,n0; lint a[N];

struct query{int a,b,id;} q[N];

bool cmpB(query x,query y) {return x.b<y.b;}

lint sum[N],ans[N];

int main()

{

    n=read(); n0=sqrt(n);

    for(int i=1;i<=n;i++) a[i]=read();

    m=read();

    for(int i=1;i<=m;i++) q[i].a=read(),q[i].b=read(),q[i].id=i;

    sort(q+1,q+m+1,cmpB);

    for(int t=1;t<=m;t++)

    {

        lint res=0;

        if(q[t].b<=n0&&q[t].b!=q[t-1].b) for(int i=n;i>=1;i--) sum[i]=a[i]+sum[i+q[t].b];

        if(q[t].b<=n0) res=sum[q[t].a];

        else for(int i=q[t].a;i<=n;i+=q[t].b) res+=a[i];

        ans[q[t].id]=res;

    }

    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);

    return 0;

}

P.S.

又得开long long...