题解 P5112 【FZOUTSY】

mrsrz · 2018-12-23 09:30:00 · 题解

显然只要考虑以每个位置开头的k个字符就可以了。

现在就要把每个位置i按照其之后的k个字符分类。

不难想到一个好写、方便且效率高的算法：哈希。

我们对每个位置i开始的连续k个字符的哈希值处理出来（可以通过每个位置的后缀哈希值处理出来，处理后缀哈希值显然O(n)扫一遍即可），然后用map对其进行离散。

接下来的问题就是：给定一个序列a_i，每次询问一个区间内有多少对数相等。

小Z的袜子

莫队一下即可。

等等复杂度不对啊，O(n\sqrt n)的啊！

没错O(n\sqrt n)就是能跑3e6

正确的做法是把块长设为\frac n {\sqrt m}，此时时间复杂度为O(n\sqrt m)，由于条件n^2m\leqslant 10^{15}，所以是正确的。

然鹅块长\sqrt n确实过了，应该是出题人没卡

注意事项：

由于字符集比较小，字符比较多，取模的单哈希容易被卡（我就被卡了好几次），双哈希会TLE。但是出题人貌似没有特意卡哈希，所以自然溢出就过了。

Code：

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<unordered_map>
const int base=233;
typedef long long LL;
#define N 3000005
std::unordered_map<LL,int>X;
inline int readint(){
    int c=getchar(),d=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
    d=d*10+(c^'0');
    return d;
}
int n,m,k,id[N],fp=0,buc[N];
LL ans[N],hx[N],H[N],pw[N];
int siz;
char s[N];
struct que{
    int l,r,id;
    inline bool operator<(const que&rhs)const{
        return(l/siz!=rhs.l/siz)?l<rhs.l:r<rhs.r;
    }
}q[100005];
int main(){
    n=readint(),m=readint(),k=readint();
    for(int i=*pw=1;i<=n;++i)pw[i]=1LL*pw[i-1]*base;
    scanf("%s",s+1);
    for(int i=n;i;--i)hx[i]=(hx[i+1]*base+s[i]-'a');
    for(int i=1;i<=n-k+1;++i){
        H[i]=hx[i]-hx[i+k]*pw[k];
        if(!X.count(H[i]))X[H[i]]=++fp;
        id[i]=X[H[i]];
    }
    for(int i=1;i<=m;++i){
        q[i].l=readint(),q[i].r=readint();q[i].id=i;
        if(q[i].r>n-k+1)q[i].r=n-k+1;
        if(q[i].l>q[i].r)q[i].l=1,q[i].r=0;
    }
    siz=n/sqrt(m);
    std::sort(q+1,q+m+1);
    LL now=0;
    for(int l=1,r=0,i=1;i<=m;++i){
        while(r<q[i].r)now+=buc[id[++r]]++;
        while(l>q[i].l)now+=buc[id[--l]]++;
        while(l<q[i].l)now-=--buc[id[l++]];
        while(r>q[i].r)now-=--buc[id[r--]];
        ans[q[i].id]=now;
    }
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
    return 0;
}