莫队入门2 洛谷P3245 [HNOI2016]大数

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=2e5+5;
 5 int n,m,p,l=1,r=0,tot=0;
 6 ll blg[N],suff[N],bin[N],f[N],presum_p[N],count_p[N],ans[N],cnt[N];
 7 
 8 struct event{
 9     int l,r,pos;
10 }e[N];
11 void build(int n)
12 {
13     int sz=sqrt(n);
14     for(int i=1;i<=n;i++)
15     blg[i]=(i-1)/sz+1; 
16 }
17 static bool cmp(event &a,event &b)
18 {
19     return (blg[a.l]^blg[b.l])?blg[a.l]1)?a.rb.r);
20 }
21 
22 void add(int n)
23 {
24     tot-=cnt[f[n]]*(cnt[f[n]]-1)/2;
25     ++cnt[f[n]];
26     tot+=cnt[f[n]]*(cnt[f[n]]-1)/2;
27 }
28 void del(int n)
29 {
30     tot-=cnt[f[n]]*(cnt[f[n]]-1)/2;
31     --cnt[f[n]];
32     tot+=cnt[f[n]]*(cnt[f[n]]-1)/2;
33 }
34 int main()
35 {
36     string s;
37     scanf("%d",&p);
38     cin>>s;
39     scanf("%d",&m);
40     for(int i=1;i<=m;i++)
41     {
42         scanf("%d%d",&e[i].l,&e[i].r);
43         e[i].pos=i;
44     }
45     n=s.size();
46     build(n);
47     sort(e+1,e+m+1,cmp);
48     ll x=1;
49     
50     for(int i=n;i>=1;i--)
51     {
52         bin[i]=suff[i]=(suff[i+1]+1ll*(s[i-1]^48)*x)%p;
53         x=x*10%p;
54     }
55     
56     sort(bin+1,bin+n+2);
57     int len=unique(bin+1,bin+n+2)-bin-1;
58     for(int i=1;i<=n+1;i++)f[i]=lower_bound(bin+1,bin+len+1,suff[i])-bin;
59     
60     if(p==2||p==5)
61     {
62     
63         for(int i=1;i<=n;i++)
64         {
65             presum_p[i]=presum_p[i-1];
66             count_p[i]=count_p[i-1];
67             if((s[i-1]-'0')%p==0)presum_p[i]+=i,count_p[i]++;
68         }
69         for(int i=1;i<=m;i++)
70         {
71             ll sum=0;
72             int pl=e[i].l,pr=e[i].r;
73             sum=(presum_p[pr]-presum_p[pl-1])-1ll*(pl-1)*(count_p[pr]-count_p[pl-1]);
74             ans[e[i].pos]=sum;
75         }
76         for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
77     }
78     else
79     {
80         for(int i=1;i<=m;i++)
81         {
82             int pl=e[i].l,pr=e[i].r+1;
83             while(l);
84             while(l>pl)add(--l);
85             while(rr);
86             while(r>pr)del(r--);
87             ans[e[i].pos]=tot;
88         }
89         for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
90     }
91     return 0;
92 }