HN一天考两个莫队是什么鬼..或者说莫队不是正确的姿势..?
考虑已经知道了
需要先预处理出后缀
那么
模数为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("%lld\n",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("%lld\n",ans[i]); return 0; }