[BZOJ]4542: [Hnoi2016]大数 莫队

Description

　　小 B 有一个很大的数 S，长度达到了 N 位；这个数可以看成是一个串，它可能有前导 0，例如00009312345。小B还有一个素数P。现在，小 B 提出了 M 个询问，每个询问求 S 的一个子串中有多少子串是 P 的倍数（0 也是P 的倍数）。例如 S为0077时，其子串 007有6个子串：0,7,00,07,007显然0077的子串007有6个子串都是素数7的倍数。

题解：

不错的题目。对于一个从 l 开始一直到结尾的子串 x ，和一个从 r+1 开始一直到结尾的子串 y ，若 x?mod?p=y?mod?p ，那么显然 l 到 r+1 的子串%p等于0，那么问题就转化为在区间内找两个相等的数的方案数了，可以用莫队解决。注意要特判 p=2 或者 p=5 的情况，因为这时满足前面的条件不一定满足后面的条件，也很好解决，因为一个子串只要个位数%p=0，那么整个子串就满足条件，处理几个前缀和就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
#define LL long long
const int Maxn=100010;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int P,n,Q,bel[Maxn];
LL s1[Maxn],s2[Maxn],Pow[Maxn];
char str[Maxn];
struct Ask{int l,r,id;}q[Maxn];
bool cmpq(Ask a,Ask b){return((bel[a.l]==bel[b.l])?a.r<b.r:a.l<b.l);}
struct Node{int x,id;}a[Maxn];
bool cmpa(Node a,Node b){return a.x<b.x;}
int b[Maxn];
LL cnt[Maxn],Ans=0,ans[Maxn];
void update(int pos,int v)
{
    Ans-=cnt[b[pos]]*(cnt[b[pos]]-1)/2LL;
    cnt[b[pos]]+=(LL)(v);
    Ans+=cnt[b[pos]]*(cnt[b[pos]]-1)/2LL;
}
int main()
{
    P=read();scanf("%s",str+1);n=strlen(str+1);Q=read();
    int size=(int)(sqrt(n));for(int i=1;i<=n;i++)bel[i]=(i-1)/size+1;
    for(int i=1;i<=Q;i++)q[i].l=read(),q[i].r=read()+1,q[i].id=i;
    Pow[0]=1;for(int i=1;i<=n;i++)Pow[i]=Pow[i-1]*10LL%P;
    a[n+1].x=0;a[n+1].id=n+1;for(int i=n;i;i--)a[i].x=((str[i]-'0')*Pow[n-i]%P+a[i+1].x)%P,a[i].id=i;
    if(P==2||P==5)
    {
        s1[0]=s2[0]=0;
        for(int i=1;i<=n;i++)s1[i]=s1[i-1]+((str[i]-'0')%P==0),s2[i]=s2[i-1]+(((str[i]-'0')%P==0)?i:0);
        for(int i=1;i<=Q;i++)
        {
            int l=q[i].l,r=q[i].r-1;
            printf("%lldn",s2[r]-s2[l-1]-(s1[r]-s1[l-1])*(l-1));
        }
    }
    else
    {
        sort(q+1,q+1+Q,cmpq);
        sort(a+1,a+2+n,cmpa);
        int now=0;a[0].x=-1;
        for(int i=1;i<=n+1;i++)
        {
            if(a[i].x!=a[i-1].x)now++;
            b[a[i].id]=now;
        }
        int l=1,r=0;
        for(int i=1;i<=Q;i++)
        {
            while(l>q[i].l)update(--l,1);
            while(r<q[i].r)update(++r,1);
            while(l<q[i].l)update(l++,-1);
            while(r>q[i].r)update(r--,-1);
            ans[q[i].id]=Ans;
        }
        for(int i=1;i<=Q;i++)printf("%lldn",ans[i]);
    }
}