Luogu

BZOJ

分析

莫队 Day2两个莫队题海星

首先考虑怎么判断 $[l,r]$ 能被 $P$ 整除。

设 $num[i]$ 表示 $i\sim n$ 所构成的数。如果 $[l,r]$ 能被 $P$ 整除,那么有 $\frac{num[l]-num[r+1]}{10^{r-l+1}}\equiv0\pmod P$。

这里可以分类讨论一下了。

  • 当 $P\neq 2$ 且 $P\neq5$ 时

此时有 $\gcd(10,P)=1$ ,于是可以得到 $num[l]-num[r+1]\equiv0\pmod P$。

进一步得到: $num[l]\% P=num[r+1]\%P$。

  • 当 $P=2$ 或 $P=5$ 时

此时只要判断最后一位就行了。


然后再来考虑莫队怎么转移。仍然分类讨论一下:

  • 当 $P\neq 2$ 且 $P\neq 5$ 时

设 $h[\,]$ 为离散化后的 $num[\,]$ ,$cnt[i]$ 为当前区间内等于 $i$ 的 $h[\,]$ 的数量。

那么加入第 $i$ 个数时,答案加上 $cnt[h[i]]$ , $cnt[h[i]]$ 加上 $1$ 即可。

删除同理,$cnt[h[i]]$ 减去 $1$ ,答案减去 $cnt[h[i]]$ 。

  • 当 $P=2$ 或 $P=5$ 时

设 $cnt$ 为当前区间内 $P$ 的倍数的个数。

从左边加入一个数时,如果为 $P$ 的倍数就将 $cnt$ 加 $1$,再将答案加上 $cnt$ 。

从右边加入一个数时,如果为 $P$ 的倍数就将 $cnt$ 加 $1$,再将答案加上区间长度。

删除同理。


细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int N=100000+10;

int P,n,m,block;
char s[N];
struct Query { int l,r,id; } q[N];
struct Duliu { int val,id; } tmp[N];
int a[N],pw[N],h[N];
ll ans,Ans[N];

bool operator <(Duliu a,Duliu b) { return a.val<b.val; }
inline int cmp(Query a,Query b) {
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

namespace SubTask1 { //p=2 || p=5
    int cnt=0,l,r;
    inline void addl(int x) { cnt+=(a[x]%P==0),ans+=cnt; }
    inline void addr(int x) { if (a[x]%P==0) ++cnt,ans+=r-l+1; }
    inline void dell(int x) { ans-=cnt,cnt-=(a[x]%P==0); }
    inline void delr(int x) { if (a[x]%P==0) ans-=r-l+1,--cnt; }
    
    inline void work() {
        l=1,r=0;
        for (re int i=1;i<=m;++i) {
            while (l<q[i].l) dell(l),++l;
            while (l>q[i].l) --l,addl(l);
            while (r<q[i].r) ++r,addr(r);
            while (r>q[i].r) delr(r),--r;
            Ans[q[i].id]=ans;
        }
    }
}

namespace SubTask2 { //p!=2 && p!=5
    int cnt[N];
    inline void add(int x) { ans+=cnt[h[x]],++cnt[h[x]]; }
    inline void del(int x) { --cnt[h[x]],ans-=cnt[h[x]]; }
        
    inline void work() {
        int l=1,r=0;
        for (re int i=1;i<=m;++i) {
            ++q[i].r;
            while (l<q[i].l) del(l++);
            while (l>q[i].l) add(--l);
            while (r<q[i].r) add(++r);
            while (r>q[i].r) del(r--);
            Ans[q[i].id]=ans;
        }
    }
}

int main() {
    scanf("%d",&P); scanf("%s",s+1); n=strlen(s+1);
    for (re int i=1;i<=n;++i) a[i]=s[i]-'0';
    
    pw[0]=1; for (re int i=1;i<=n;++i) pw[i]=1ll*pw[i-1]*10%P;
    for (re int i=n;i>=1;--i)
        tmp[i]=(Duliu){(tmp[i+1].val+1ll*a[i]*pw[n-i])%P,i};
    sort(tmp+1,tmp+n+1);
    for (re int i=1,tot=0;i<=n;++i) {
        if (tmp[i].val!=tmp[i-1].val) ++tot;
        h[tmp[i].id]=tot;
    }
    
    scanf("%d",&m);
    for (re int i=1;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    block=sqrt(n); sort(q+1,q+m+1,cmp);
    
    if (P==2||P==5) SubTask1::work();
    else SubTask2::work();
    for (re int i=1;i<=m;++i) printf("%lld\n",Ans[i]);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 17 PM