HNOI2016 大数（number）lt;莫队gt;

题目

分析

一道典型的莫队。
先预处理出后缀，即f[i]表示i~(n-1) mod p 的值.
但p的值不小，显然不能直接存，加一个离散化。

观察题目，发现一串数s(l~r)整除p满足s(l~n-1)%p==s(r+1~n-1)%p
但p值为2或5不满足这个性质需要特判（不过数据中好像没有，于是笔者没写，有兴趣的可以自己去写写。。。。。。）

然后问题转化为求一段区间中有几对相等的f值。

套一个莫队。（ans（l，r）可以由【ans（l+1，r），ans（l-1，r），ans（l，r+1），ans（l，r-1）】推出，为保证时间复杂度，用个分块【因为不会曼哈顿树】）。

注意：要在数列的后面加一个f值为0。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=200000+10;
char a[maxn];
ll p,n,m,s[maxn],_10[maxn]/*_10[i]表示10的i次方modp*/,f[maxn]/*f[i]表示i~l mod p 的值*/,cd[maxn];
ll cur,sum[maxn],kuai,ans[maxn];
struct query
{
    ll t,x,y;
}q[maxn];
//把每个区间(l,r)看成一个点(x,y),相同块中的点按y排序，否则按x排序，可以保证n^1.5的时间复杂度
bool operator < (const query& a,const query& b){
    if(a.x/kuai==b.x/kuai) return a.y<b.y;
    else return a.x<b.x;
}
int main()
{
    //freopen("number.in","r",stdin);
    //freopen("number.out","w",stdout); 
    cin>>p;
    _10[0]=1;//其实这个_10数组可以只用一个变量
    _10[1]=10%p;
    for(int i=2;i<maxn;i++){
        _10[i]=(_10[i-1]*_10[1])%p;
    }

    char c;
    scanf("%s",a);
    n=strlen(a);
    kuai=(ll)sqrt((double)n);//按x坐标分块，kuai表示没段块的长度
    cin>>m;
    for(int i=1;i<=m;i++)
      scanf("%lld%lld",&q[i].x,&q[i].y),q[i].x--,q[i].t=i;
    sort(q+1,q+m+1);
    for(int i=0;i<n;i++)
      s[i]=a[i]-'0';

    f[n-1]=s[n-1]%p;
    cd[n-1]=f[n-1];
    for(int i=n-2;i>=0;i--){
        f[i]=(f[i+1]+(_10[n-i-1]*s[i])%p)%p;
        cd[i]=f[i];
    }
    //for(int i=0;i<n;i++) printf("%lld ",f[i]);printf("n");
    //离散化
    cd[n]=0;
    sort(cd,cd+n+1);
    int tot=0;
    for(int i=1;i<=n;i++){
        if(cd[i]!=cd[tot]) cd[++tot]=cd[i];
    }
    for(int i=0;i<n;i++)
    {
        int mid,l=0,r=tot;
        while(l<r)    //在ad中找到f的位置
        {
            mid=(l+r)>>1;
            if(cd[mid]<f[i]) l=mid+1;
            else r=mid;
        }
        f[i]=l;
    }
    //***********************************************  
    int l,r;
    l=1;r=0;
    for(int i=1;i<=m;i++)
    {
        while(r<q[i].y) 
          cur+=sum[f[++r]]++;
        while(l>q[i].x)
          cur+=sum[f[--l]]++;
        while(r>q[i].y)
          cur-=--sum[f[r--]];
        while(l<q[i].x)
          cur-=--sum[f[l++]];
        ans[q[i].t]=cur;
    }
    for(int i=1;i<=m;i++) printf("%lldn",ans[i]);
    return 0; 
} 
/*
样例：
11
121121
3
1 6
1 5
1 4
*/

（编辑：晋中站长网）

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