4542: [Hnoi2016]大数|莫队

HN一天考两个莫队是什么鬼..或者说莫队不是正确的姿势..?
考虑已经知道了 l..r 的答案新添入 r+1 如何更新当前答案
需要先预处理出后缀 modp 的值 bi ，假设子序列 l..r 模 p 的值为 x
那么 x?10r?l+b[r]=b[l] 然后就可以直接莫队统计了
模数为2或5的时候要特判一下

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<ctime>
#include<set>
#include<map>
#define N 110000
#define ll long long
using namespace std;
struct W{int l,r,p;}q[N];
char s[N];
long long sum[N],mod,ss[N],ans[N];
long long a[N],b[N],c[N],h[N],now;
int bl[N],cnt[N];
int n,m,Q,tot,block;
void solve_2_5()
{
    for(int i=1;i<=n;i++)
    {
        ss[i]=ss[i-1];
        sum[i]=sum[i-1];
        if((s[i]-'0')%mod==0) sum[i]+=i,ss[i]++;
    }
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
    {
        int l,r;scanf("%d%d",&l,&r);
        printf("%lldn",sum[r]-sum[l-1]-(ss[r]-ss[l-1])*(l-1));
    }
}
bool cmp(int x,int y)
{
    return b[x]<b[y];
}
bool cmp1(W a,W b)
{
    return bl[a.l]<bl[b.l]||(bl[a.l]==bl[b.l]&&a.r<b.r);
}
int main()
{
    scanf("%lld%s",&mod,s+1);
    n=strlen(s+1); block=sqrt(n);
    if(mod==2||mod==5)
    {
        solve_2_5();
        return 0;
    }
    a[0]=1;
    for(int i=1;i<=n;i++) a[i]=10*a[i-1]%mod;
    for(int i=n;i>=1;i--) b[i]=(a[n-i]*(s[i]-'0')+b[i+1])%mod;
    for(int i=1;i<=n;i++) c[i]=i;
    sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++)
        if(b[c[i]]==b[c[i-1]]) h[c[i]]=tot;
        else h[c[i]]=++tot;
    for(int i=1;i<=n;i++) bl[i]=(i-1)/block;
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].p=i;
    sort(q+1,q+Q+1,cmp1);
    int L=1,R=0;
    for(int i=1;i<=Q;i++)
    {
        while(L>q[i].l) now+=cnt[h[L-1]]+(h[R+1]==h[L-1]),cnt[h[--L]]++;
        while(R<q[i].r) cnt[h[++R]]++,now+=cnt[h[R+1]];

        while(L<q[i].l) cnt[h[L]]--,now-=cnt[h[L]]+(h[R+1]==h[L]),L++;
        while(R>q[i].r) now-=cnt[h[R+1]],cnt[h[R--]]--;
        ans[q[i].p]=now;
    }
    for(int i=1;i<=Q;i++) printf("%lldn",ans[i]);
    return 0;
}

（编辑：拼字网 - 核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!