BZOJ_3207_花神的嘲讽计划1_(Hash+主席树)

时间：2024-05-19 23:04:50

描述

http://www.lydsy.com/JudgeOnline/problem.php?id=3207

给出一个长度为\(n\)的串,以及\(m\)个长度为\(k\)的串,求每个长度为\(k\)的串在原串\([x,y]\)区间是否出现过.

分析

这道题要求对比长度为\(k\)的串,于是我们把这些串的Hash值都算出来,问题就转化成了求\([x,y]\)的区间中是否出现过某Hash值.

求区间中某一个值出现了多少次,可以用主席树.

p.s.

1.学习了主席树指针的写法,比数组慢好多啊...看来有必要去学一学平衡树的数组写法...不过好处是不用自己算空间...

2.这道题自己算空间的话会MLE,所以卡着空间限制就好,估计数据比较小,可以过.

数组:

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn=+,X=;

 typedef unsigned long long ull;

 const ull INF=~0ull;

 int n,m,k,cnt;

 int a[maxn],rt[maxn];

 ull s[maxn],x=;

 struct node{ int l,r,s; }t[maxn*];

 inline int read(int &x){ x=;int k=;char c;for(c=getchar();c<''||c>'';c=getchar())if(c=='-')k=-;for(;c>=''&&c<='';c=getchar())x=x*+c-'';return x*=k; }

 void update(ull l,ull r,int &pos,ull d){

     t[++cnt]=t[pos]; pos=cnt; t[pos].s++;

     if(l==r) return;

     ull mid=l+(r-l)/;

     if(d<=mid) update(l,mid,t[pos].l,d);

     else update(mid+,r,t[pos].r,d);

 }

 bool query(int x,int y,ull l,ull r,ull d){

     if(t[y].s-t[x].s==) return false;

     if(l==r) return true;

     ull mid=l+(r-l)/;

     if(d<=mid) return query(t[x].l,t[y].l,l,mid,d);

     else return query(t[x].r,t[y].r,mid+,r,d);

 }

 int main(){

     read(n); read(m); read(k);

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

         read(a[i]);

         s[i]=s[i-]*X+(ull)a[i];

     }

     for(int i=;i<=k;i++) x*=X;

     for(int i=k;i<=n;i++) rt[i]=rt[i-], update(0ull,INF,rt[i],s[i]-s[i-k]*x);

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

         ull hash=; bool ans;

         int l,r; read(l); read(r);

         for(int j=,t;j<=k;j++)  hash=hash*X+read(t);

         if(r+-l<k) ans=false;

         else ans=query(rt[l+k-],rt[r],0ull,INF,hash);

         ans?puts("No"):puts("Yes");

     }

     return ;

 }

指针:

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn=+,X=;

 typedef unsigned long long ull;

 const ull INF=~0ull;

 int n,m,k,cnt;

 int a[maxn];

 ull s[maxn],x=;

 struct node{

     node* l,* r; int s;

     node(){}

     node(node *l,node* r,int s):l(l),r(r),s(s){}

 }* rt[maxn],* null;

 inline int read(int &x){ x=;int k=;char c;for(c=getchar();c<''||c>'';c=getchar())if(c=='-')k=-;for(;c>=''&&c<='';c=getchar())x=x*+c-'';return x*=k; }

 node* update(node* t,ull l,ull r,ull d){

     if(l==r) return new node(null,null,t->s+);

     ull mid=l+(r-l)/;

     if(d<=mid) return new node(update(t->l,l,mid,d),t->r,t->s+);

     else return new node(t->l,update(t->r,mid+,r,d),t->s+);

 }

 bool query(node* x,node* y,ull l,ull r,ull d){

     if(y->s-x->s==) return false;

     if(l==r) return true;

     ull mid=l+(r-l)/;

     if(d<=mid) return query(x->l,y->l,l,mid,d);

     else return query(x->r,y->r,mid+,r,d);

 }

 int main(){

     read(n); read(m); read(k);

     null=new node;

     null->l=null, null->r=null, null->s=;

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

         read(a[i]);

         s[i]=s[i-]*X+(ull)a[i];

     }

     for(int i=;i<=k;i++) x*=X;

     rt[k-]=new node(null,null,);

     for(int i=k;i<=n;i++) rt[i]=update(rt[i-],0ull,INF,s[i]-s[i-k]*x);

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

         ull hash=; bool ans;

         int l,r; read(l); read(r);

         for(int j=,t;j<=k;j++)  hash=hash*X+read(t);

         if(r+-l<k) ans=false;

         else ans=query(rt[l+k-],rt[r],0ull,INF,hash);

         ans?puts("No"):puts("Yes");

     }

     return ;

 }

相关文章