BZOJ 3207: 花神的嘲讽计划Ⅰ(莫队+哈希)

解题思路

　　刚开始写了个莫队+哈希+$map$的$O(n\sqrt(n)log(n)$的辣鸡做法，$T$飞了。后来看了看别人博客发现其实并不用拿$map$当桶存那些哈希值。因为只有$n-k+1$个哈希值，可以提前预处理出来，然后离散化。时间复杂度$O(n\sqrt(n))$，比主席树都快。

代码

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

using namespace std;

typedef unsigned long long ull;

const int N=100005;

const int base=666623333;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return f?x:-x;

}

int n,m,k,ans[N],siz,cnt[N],tot;

ull hsh[N],tb[N],a[N],cpy[N];

struct Query{

    int l,r,id;

    ull w;

    friend bool operator<(const Query A,const Query B){

        if(A.l/siz!=B.l/siz) return A.l<B.l;

        if((A.l/siz)&1) return A.r>B.r;

        return A.r<B.r;

    }

}q[N];

inline void del(int x){

    if(x+k-1>n) return;

    cnt[a[x]]--;

}

inline void add(int x){

    if(x+k-1>n) return;

    cnt[a[x]]++;

}

int main(){

    ull HSH; int x,y,pos; bool flag;

    n=rd(),m=rd(),k=rd(); tb[0]=1; siz=sqrt(n);

    for(int i=1;i<=n;i++){

        x=rd();

        hsh[i]=hsh[i-1]*base+x;

    }

    for(int i=1;i<=k;i++) tb[i]=tb[i-1]*base;

    for(int i=1;i<=n-k+1;i++) a[++tot]=hsh[i+k-1]-hsh[i-1]*tb[k],cpy[tot]=a[tot];

    sort(cpy+1,cpy+1+tot); int u=unique(cpy+1,cpy+1+tot)-cpy-1;

    for(int i=1;i<=tot;i++) a[i]=lower_bound(cpy+1,cpy+1+u,a[i])-cpy;

    for(int i=1;i<=m;i++){

        x=rd(),y=rd(); flag=false; HSH=0; y=y-k+1;

        for(register int j=1;j<=k;j++) HSH=HSH*base+rd();

        pos=lower_bound(cpy+1,cpy+1+u,HSH)-cpy;

        if(cpy[pos]!=HSH) q[i].w=0;

        else q[i].w=pos;

        q[i].l=x; q[i].r=y; q[i].id=i;

    }

    sort(q+1,q+1+m); int L=1,R=0;

    for(int i=1;i<=m;i++){

        while(L<q[i].l) {del(L); L++;}

        while(L>q[i].l) {L--; add(L);}

        while(R<q[i].r) {R++; add(R);}

        while(R>q[i].r) {del(R); R--;}

        ans[q[i].id]=(cnt[q[i].w]>0)?0:1;

    }

    for(int i=1;i<=m;i++) puts(ans[i]?"Yes":"No");

    return 0;

}

巴特西

BZOJ 3207: 花神的嘲讽计划Ⅰ(莫队+哈希)

解题思路

代码

最新文章

热门文章