BZOJ 3207花神の皮肉計画I題解&コード

題意:n個の数を与え、長さnのシーケンス([1,n]の区間と見なすことができる)を形成するm組のクエリがあり、各グループのクエリに対して1つのxと1つのyが与えられ、その後、1つの長さkのシーケンスsが与えられる.区間[x,y]において、少なくとも1つのシーケンスがシーケンスsと完全に一致している場合、出力No、そうでなければ出力Yes.**なお、マッチングに成功した出力Noは、失敗した場合のみYesを出力する
考え方:まぁ...k個の数字hashごとに永続化可能なセグメントツリーの対応位置に一気に格納することで,n−k+1個のセグメントツリーのルートノードが得られ,[k,n]となる.x+k-2からy番目のセグメントツリーの対応する位置のsize[]が変化するかどうかを問い合わせるたびに(差は0ではない)、変化が発生すると、この区間にsize[y]-size[x+k-2]個の一致するシーケンスが存在することを示します.
hash私は本当に黄先輩のhash方式を借りることができませんでした

#include<iostream>
#include<stdio.h>
#define ull unsigned long long
#define inf 18446744073709551615UL
using namespace std;
const int maxn=200005;
int n,m,k,x,y,a,tot,val[maxn],s[maxn*40],son[maxn*40][2];
ull rt[maxn],v[maxn],M=1,b;
void addtree(ull l,ull r,int rl,int rn,ull value)
{
    s[rn]=s[rl]+1;
    if(l==r)
        return;
    ull mid=l/2+r/2;
    mid+=(l&1)&&(r&1);
    if(value>mid)son[rn][1]=++tot,son[rn][0]=son[rl][0],addtree(mid+1,r,son[rl][1],son[rn][1],value);
    else son[rn][0]=++tot,son[rn][1]=son[rl][1],addtree(l,mid,son[rl][0],son[rn][0],value);
}
void insert(int a,int b,ull c)
{
    rt[b]=++tot;
    addtree(1,inf,rt[a],rt[b],c);
}
int query(ull l,ull r,int rl,int rn,ull value)
{
    if(l==r)
        return s[rn]-s[rl];
    ull mid=l/2+r/2;
    mid+=(l&1)&&(r&1);
    if(value>mid)return query(mid+1,r,son[rl][1],son[rn][1],value);
    else return query(l,mid,son[rl][0],son[rn][0],value);
}
int main(void)
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        val[i]++;
    }
    for(int i=1;i<=n;i++)
        v[i]=v[i-1]*107,v[i]+=(ull)val[i];
    for(int i=1;i<=k;i++)
        M*=107;
    for(int i=k;i<=n;i++)
        insert(i-1,i,v[i]-v[i-k]*M);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        b=0;
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&a);
            b*=107;
            b+=(ull)(a+1);
        }
        if(query(1,inf,rt[x+k-2],rt[y],b))printf("No
");
        else printf("Yes
");
    }
    return 0;
}