bzoj 4542: [Hnoi2016]大数

.

题意：给定一个数字串，多个询问l~r之间有多少个子串是p的倍数。
题解：离散化+莫队
若某个子串是p的倍数，设这个子串为$x$，$x$后面一直到结尾的后缀为$y$，以$x$开始的后缀为$z$：$x\equiv 0 \pmod p\\\ x\times 10^k\equiv 0 \pmod p \ (k为y的位数)\\\ x\times 10^k+y\equiv y \pmod p\\\ z\equiv y \pmod p$所以我们只要求出每个后缀$\%p$（记为$a$），然后用找区间内相等的a的对数就好了。a要离散化。
注意$p=2$或$5$时要特判。
代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;

int p,n,m;
char s[100010];
struct query
{
    int l,r,id;
    long long ans;
}q[100010];
long long sum1[100010],sum2[100010],a[100010],ans=0;
int block[100010];
map<int,int>lsh;

int cmp(query x,query y)
{
    return block[x.l]==block[y.l]?x.r<y.r:x.l<y.l;
}
void update(int x,int y)
{
    ans+=min(sum1[a[x]],sum1[a[x]]+y)*y;
    sum1[a[x]]+=y;
}
int cmp2(query x,query y)
{
    return x.id<y.id;
}
int main()
{
    scanf("%d%s",&p,s);
    n=strlen(s);
    scanf("%d",&m);
    if(p==2||p==5)
    {
        for(int i=0;i<n;i++)
        {
            if(i)
            sum1[i]=sum1[i-1];
            sum2[i]=sum2[i-1];
            if((s[i]-'0')%p==0)
            {
                sum1[i]++;
                sum2[i]+=i;
            }
        }
        for(int i=0;i<m;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",sum2[r-1]-sum2[l-2]-(l-2)*(sum1[r-1]-sum1[l-2]));
        }
        return 0;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].l--;
//        q[i].r--;
        q[i].id=i;
    }
    int block_size=sqrt(n);
    for(int i=0;i<n;i++)
    block[i]=i/block_size;
    sort(q,q+m,cmp);
    long long pow=1;
    for(int i=n-1;i>=0;i--)
    {
        a[i]=(a[i+1]+(s[i]-'0')*pow%p)%p;
        pow=pow*10%p;
    }/*
    for(int i=0;i<n;i++)
    printf("%d ",a[i]);
    puts("");*/
    for(int i=0;i<=n;i++)
    lsh[a[i]]=1;
    int nn=0;
    for(map<int,int>::iterator it=lsh.begin();it!=lsh.end();it++)
    it->second=++nn;
    for(int i=0;i<=n;i++)
    a[i]=lsh[a[i]];
    int l=0,r=-1;
    for(int i=0;i<m;i++)
    {
//        printf("%d %d\n",q[i].l,q[i].r);
        while(r<q[i].r)
        update(++r,1);
        while(l>q[i].l)
        update(--l,1);
        while(r>q[i].r)
        update(r--,-1);
        while(l<q[i].l)
        update(l++,-1);
        q[i].ans=ans;
    }
    sort(q,q+m,cmp2);
    for(int i=0;i<m;i++)
    printf("%lld\n",q[i].ans);
}