bzoj 3207: 花神的嘲讽计划Ⅰ

.

题意：给定一个序列和若干询问，询问一个串是否是原序列l到r范围的子串。
题解：哈希+主席树。暴力求出原序列每个长度为k的子串的哈希值，然后问题就转化为区间内是否存在某个数。一开始读错题。。以为是子序列。。想了好久。。。。。。
代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,m,k,base=233,num=0,root[100010];
unsigned long long a[100010],hh=1,s[100010],inf=0;
struct tree
{
    int lc,rc,c;
    tree()
    {
        lc=rc=c=0;
    }
}tr[8000010];

int ins(int ot,unsigned long long l,unsigned long long r,unsigned long long x)
{
    int rt=++num;
    tr[rt]=tr[ot];
    tr[rt].c++;
    if(l==r)
    return rt;
    unsigned long long md=(l>>1)+(r>>1)+((l&1)&&(r&1));
//    printf("%d %llu %llu %llu %llu\n",num,l,r,md,x);
    //Sleep(3000);
    if(x<=md)
    tr[rt].lc=ins(tr[ot].lc,l,md,x);
    else
    tr[rt].rc=ins(tr[ot].rc,md+1,r,x);
    return rt;
}
bool get(int ot,int rt,unsigned long long l,unsigned long long r,unsigned long long x)
{
//    printf("%lld %lld %d %d %lld\n",l,r,tr[ot].c,tr[rt].c,x);
    if(!rt)
    return 0;
    if(l==r)
    return tr[rt].c-tr[ot].c;
    unsigned long long md=(l>>1)+(r>>1)+((l&1)&&(r&1));
    if(x<=md)
    return get(tr[ot].lc,tr[rt].lc,l,md,x);
    else
    return get(tr[ot].rc,tr[rt].rc,md+1,r,x);
}
int main()
{
//    freopen("3207.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)
    hh*=base;
    for(int i=1;i<=n;i++)
    {
        scanf("%llu",&a[i]);
        a[i]+=a[i-1]*base;
    }
    for(int i=k;i<=n;i++)
    {
        s[i]=a[i]-a[i-k]*hh;
//        printf("%lld ",s[i]);
        inf=max(inf,s[i]);
    }
//    puts("");
    for(int i=k;i<=n;i++)
    {
//        printf("YES");
    root[i]=ins(root[i-1],0,inf,s[i]);
//    printf("%d\n",i);
    }
//    printf("%d\n",num);
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x+=k-2;
        unsigned long long hh=0;
        for(int j=0;j<k;j++)
        {
            int x;
            scanf("%d",&x);
            hh=hh*base+x;
        }
        if(hh>inf)
        {
            puts("Yes");
            continue;
        }
//        printf("%d %d %lld\n",x,y,hh);
        if(get(root[x],root[y],0,inf,hh))
        puts("No");
        else
        puts("Yes");
    }
}