【BZOJ3207】花神的嘲讽计划Ⅰ

2015.08.12 10:02 Wed | 13次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给出一个串,每次询问一段区间内是否出现过某个子串,询问的子串长度固定为K。

题解

建一颗主席树,每个位置的值是以这个位置结尾的长度为K的串的hash值,然后就没什么了。
这题就是为了练下hash……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define BASE 13131
#define ll long long
#define N 200005
#define mod 100007
#define ull unsigned long long 
int n,m,K,cnt;
int a[N],root[N];
ull val[N];
int h[N],nxt[200005],tp;
int sum[N*18],ls[N*18],rs[N*18];
int insert(ull k)
{
    int t=k%mod;
    for(int i=h[t];i;i=nxt[i])
    if(val[i]==k) return i;
    val[++tp]=k;nxt[tp]=h[t];h[t]=tp;
    return tp;
}
int find(ull k)
{
    int t=k%mod;
    for(int i=h[t];i;i=nxt[i])
    if(val[i]==k) return i;
    return 0;
}
void build(int &x,int t,int l,int r,int k)
{
    sum[x=++cnt]=sum[t]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) rs[x]=rs[t],build(ls[x],ls[t],l,mid,k);
    else ls[x]=ls[t],build(rs[x],rs[t],mid+1,r,k);
}
int query(int x,int y,int l,int r,int k)
{
    if(l==r) return sum[x]-sum[y];
    if(sum[x]-sum[y]==0) return 0;
    int mid=(l+r)>>1;
    if(k<=mid) return query(ls[x],ls[y],l,mid,k);
    else return query(rs[x],rs[y],mid+1,r,k);
}
int main()
{
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        if(i>=K)
        {
            ull tmp=0;
            for(int j=i-K+1;j<=i;j++) tmp=tmp*BASE+a[j];
            int t=insert(tmp);
            build(root[i],root[i-1],1,200000,t);
        }
    }
    for(int x,y,t,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        ull tmp=0;
        for(int j=1;j<=K;j++)
        {
            scanf("%d",&t);
            tmp=tmp*BASE+t;
        }
        int k=find(tmp);
        if(k&&y-x+1>=K&&query(root[y],root[x+K-2],1,200000,k)) puts("No");
        else puts("Yes"); 
    }
}```