【BZOJ3207】花神的嘲讽计划Ⅰ

  直接把序列中每个连续的k个数字合起来hash一遍，然后查询就好了。

#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const int maxn=200010,p=201517;
const LL RAD[7]={14503,5305,321,34355,3,3928,149};
vector <int> A[p];
int n,m,k,x,y;
 
LL s[maxn],d[maxn];
 
void Build_Hash_Table()
{
    LL key=0,o=1;
    for (int i=1;i<=k;i++) o=o*173%p;
    for (int i=1;i<k;i++) key=(key*173+s[i]*RAD[s[i]%7])%p;
    for (int i=k;i<=n;i++) key=((key*173+s[i]*RAD[s[i]%7]-s[i-k]*RAD[s[i-k]%7]%p*o%p)%p+p)%p,A[key].push_back(i-k+1);
}
 
int Key_Calc()
{
    LL key=0;
    for (int i=1;i<=k;i++) key=(key*173+d[i]*RAD[d[i]%7])%p;
    return key;
}
 
bool Check(int key)
{
    if (A[key].size()==0) return false;
    int l=0,r=A[key].size()-1,mid;
    while (l<r) (A[key][mid=(l+r)>>1]>=x)?r=mid:l=mid+1;
    if (A[key][l]<x) return false;
    while (A[key][l]+k-1<=y)
    {
        int left=A[key][l],flag=1;
        for (int i=1;i<=k&&flag;i++) if (d[i]!=s[left+i-1]) flag=0;
        if (flag) return true;
        l++;
    }
    return false;
}
 
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) scanf("%lld",&s[i]);
    Build_Hash_Table();
    while (m--)
    {
        scanf("%d%d",&x,&y);
        for (int i=1;i<=k;i++) scanf("%lld",&d[i]);
        if (Check(Key_Calc())) printf("No\n");else printf("Yes\n");
    }
    return 0;
}