这是一道挂羊头卖狗肉的题。(虽然我也不知道究竟能不能用线段树解决)但是分块实在是太方便了。

题意

给定一个长度为n的序列和一个正整数k,有m次操作。(n,m,k<=105)每次操作是将一个区间[a,b]加上一个数c,或者询问区间[a,b]中是k的整数倍的数有几个。

思路

可以用分块大法。每一块保存这个块中处以k为各个余数的数的个数,以及这些数同时加上了多少。这样就可以O(sqrt(n))修改,查询。
(1) 如果当前修改一整块,则直接修改“这些数同时加上了多少”
(2) 如果当前修改块部分,则修改“这个块中处以k为各个余数的个数”


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int kmod[450][200501];
int an[450];
int src[200501];
int n,m,k,ksize;

inline int read(void)
{
    int x=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}

inline void input(void)
{
    n=read(),m=read(),k=read();
    ksize=sqrt(n);
    for(register int i=1;i<=n;i++)src[i]=read(),src[i]%=k,kmod[(i-1)/ksize][src[i]]++;
}

inline void add(int l,int r,int x)
{
    int top,nk;
    top=min((l-1)/ksize*ksize+ksize,r),nk=(l-1)/ksize;
    for(register int i=l;i<=top;++i)
    {
        --kmod[nk][src[i]];
        src[i]=(src[i]+x)%k;
        ++kmod[nk][src[i]];
        if(i==r)return;
    }
    top=(r-1)/ksize*ksize+1,nk=(r-1)/ksize;
    for(register int i=r;i>=top;--i)
    {
        --kmod[nk][src[i]];
        src[i]=(src[i]+x)%k;
        ++kmod[nk][src[i]];
    }

    top=(r-1)/ksize-1;
    for(register int i=(l-1)/ksize+1;i<=top;++i)an[i]=(an[i]+x)%k;
}

inline int cnt(int l,int r)
{
    int ans=0,top;
    top=min((l-1)/ksize*ksize+ksize,r);
    for(register int i=l;i<=top;++i)
    {
        if(!((src[i]+an[(l-1)/ksize])%k))++ans;
        if(i==r)return ans;
    }
    top=(r-1)/ksize*ksize+1;
    for(register int i=r;i>=top;--i)if(!((src[i]+an[(r-1)/ksize])%k))++ans;
    top=(r-1)/ksize-1;
    for(register int i=(l-1)/ksize+1;i<=top;++i)ans+=kmod[i][(10*k-an[i])%k];
    return ans;
}

int main()
{
    char com[10];
    int l,r,x;
    input();
    for(int i=1;i<=m;i++)
    {
        scanf("%s",com);
        if(com[0]=='a')l=read(),r=read(),x=read(),add(l,r,x);
        if(com[0]=='c')l=read(),r=read(),printf("%d\n",cnt(l,r));
    }
    return 0;
}
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *