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

题意

给定一个长度为 n 的序列和一个正整数 k，有 m 次操作。(n,m,k<=10⁵) 每次操作是将一个区间 [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;
}