[bzoj3207]花神的嘲讽计划Ⅰ[可持久化线段树，hash]

将每k个数字求一个哈希值，存入可持久化线段树，直接查询即可

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <ctime>

 using namespace std;

 #define    INF    0xffffffffU

 int    n,m,k,tot;

 unsigned int  Sum[]={};

 int    val[],Left[],Right[],a[],root[];

 void    Insert(const unsigned int l,const unsigned int r,const int root_l,int & root_r,const unsigned int d)

 {

     val[root_r=++tot]=val[root_l]+;

     if(l==r)return ;

     unsigned int    mid=l+((r-l)>>);

     if(d<=mid)

     {

         Right[root_r]=Right[root_l];

         Insert(l,mid,Left[root_l],Left[root_r],d);

     }

     else

     {

         Left[root_r]=Left[root_l];

         Insert(mid+,r,Right[root_l],Right[root_r],d);

     }

     return ;

 }

 int    Query(const unsigned int l,const unsigned int r,const int root_l,const int root_r,const unsigned int d)

 {

     if(l==r)return val[root_r]-val[root_l];

     unsigned int    mid=l+((r-l)>>);

     if(d<=mid)return Query(l,mid,Left[root_l],Left[root_r],d);

     return Query(mid+,r,Right[root_l],Right[root_r],d);

 }

 int main()

 {

     int    i,j;

     unsigned int    t=;

     scanf("%d%d%d",&n,&m,&k);

     for(i=;i<=k;++i)t=t*;

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

     {

         scanf("%d",&a[i]);

         Sum[i]=Sum[i-]*+a[i];

     }

     for(i=k;i<=n;++i)

     {

         Insert(,INF,root[i-],root[i],Sum[i]-Sum[i-k]*t);

     }

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

     {

         int    l,r,b;

         unsigned int    temp=0U;

         scanf("%d%d",&l,&r);

         for(j=;j<=k;++j)scanf("%d",&b),temp=temp*+b;

         printf("%s\n",Query(,INF,root[l+k-],root[r],temp)?"No":"Yes");

     }

     return ;

 }