bzoj 4542: [Hnoi2016]大数（莫队）

4542: [Hnoi2016]大数

Time Limit: 20 Sec Memory Limit: 128 MB Submit: 1252 Solved: 436 [Submit][Status][Discuss]

Description

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

Input

　　第一行一个整数：P。第二行一个串：S。第三行一个整数：M。接下来M行，每行两个整数 fr,to，表示对S 的子串S[fr…to]的一次询问。注意：S的最左端的数字的位置序号为 1；例如S为213567，则S[1]为 2，S[1…3]为 2 13。N,M<=100000，P为素数

Output

　　输出M行，每行一个整数，第 i行是第 i个询问的答案。

Sample Input

11 121121 3 1 6 1 5 1 4

Sample Output

5 3 2 //第一个询问问的是整个串，满足条件的子串分别有：121121,2112,11,121,121。

HINT

2016.4.19新加数据一组

Source

[Submit][Status][Discuss]

题解：莫队

A*10^k+B = B (mod p) 如果10^k与p互质的话，那么A是p的倍数，这个应该很显然吧。。。。

然后我们可以对于每一个位置维护后缀和如果我们要表示[l,r]的数在p意义下的余数，那么其实就是s[l]-s[r+1]

那么问题就变成了求一段区间中相同余数的数对数。用莫队即可求解。

但是这道题需要注意下算法的常数，比如p可能是long long 范围的数，那么余数需要用到离散化，如果每次都查询离散化后的值(用map)，那么实际是在莫队的时间复杂度上乘(logp)。在c++中乘除运算的速度要远高于加减运算，所以在移动左右端点的过程中，尽量不用乘除。cnt[i]表示余数为i的数的个数，那么对答案的贡献就是cnt[i]*(cnt[i]-1)/2.我们自然可以这么计算，不过考虑cnt[i]->cnt[i]+1,对答案的影响实际就是+cnt[i]。

还有需要特判p=2,p=5的情况，这时候余数其实就只与最后一位有关，所以我们可以记录1到每个位置的答案，以及1到每个位置出现了多少余数为0的位置，那么最后的答案可以直接计算得出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define N 200003
#define LL long long 
using namespace std;
char s[N];
int n,m,block,belong[N];
LL a[N],c[N],cnt[N],b[N],ans,p;
struct data{
    int l,r,id;
}q[N];
map<LL,LL> mp;
int cmp(data a,data b){
    return belong[a.l]<belong[b.l]||belong[a.l]==belong[b.l]&&a.r<b.r;
}
void change(int x,int val)
{
    LL t=mp[a[x]];
    ans-=(LL)cnt[t]*(cnt[t]-1)/2;
    cnt[t]+=(LL)val;
    ans+=(LL)cnt[t]*(cnt[t]-1)/2;
}
int main()
{
    scanf("%lld",&p);
    scanf("%s",s+1); n=strlen(s+1);
    if (p!=5&&p!=2) {
        a[n]=(LL)(s[n]-'0')%p; b[n]=a[n];  LL t=1;
        for (int i=n-1;i>=1;i--)  {
         t=(t*10)%p,a[i]=(LL)(a[i+1]+(LL)(s[i]-'0')*t)%p;
         b[i]=a[i];
        }
        sort(b+1,b+n+2);
        t=unique(b+1,b+n+2)-b-1;
        for (int i=1;i<=t;i++) mp[b[i]]=i;
        for (int i=1;i<=n+1;i++) a[i]=mp[a[i]];
        scanf("%d",&m);
        block=ceil(sqrt(n+1));
        for (int i=1;i<=n+1;i++) belong[i]=(i-1)/block+1;
        for (int i=1;i<=m;i++) 
         scanf("%d%d",&q[i].l,&q[i].r),q[i].r++,q[i].id=i;
        sort(q+1,q+m+1,cmp);
        int l=1; int r=0; 
        for (int i=1;i<=m;i++) {
          while(r<q[i].r) ++r,ans+=cnt[a[r]]++;
          while(l>q[i].l) --l,ans+=cnt[a[l]]++;
          while(l<q[i].l) ans-=--cnt[a[l]],l++;
          while(r>q[i].r) ans-=--cnt[a[r]],r--;
          c[q[i].id]=ans;
        }
        for (int i=1;i<=m;i++) PRintf("%lld\n",c[i]);
        return 0;
    }
    for (int i=1;i<=n;i++)
     if (!((s[i]-'0')%p))a[i]=a[i-1]+1,b[i]=(LL)b[i-1]+i;
     else a[i]=a[i-1],b[i]=b[i-1];
    scanf("%d",&m);
    for (int i=1;i<=m;i++) {
        int l,r; scanf("%d%d",&l,&r);
        printf("%lld\n",(LL)b[r]-b[l-1]-(a[r]-a[l-1])*(LL)(l-1));
    }
}

bzoj 4542: [Hnoi2016]大数 （莫队）