题目大意：给定一个数字串，多次求某个区间内有没有一个长度为k的子串

首先对字符串进行哈希 然后问题就转化成了求一个区间内有没有某个数

可持久化线段树即可 其实我觉得划分树会更快一些 可以写写

※注意事项：

1.n<=200000 我找不到数据范围是眼科大夫去找老阎的关系？

2.哈希值用unsigned long long 铁则 unsigned int 会被卡掉

3.线段树那里直接x+y>>1会爆unsigned long long 转换一下 x+y>>1=(x>>1)+(y>>1)+(x&y&1)

4.Yes和No不要弄反

5.内存不够用 mempool适当开小点 刚好不MLE为止即可 不知道为什么开少一点不会RE

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 200200
#define key 10016959
using namespace std;
typedef unsigned long long ll;
struct abcd{
	abcd *ls,*rs;
	int num;
}*tree[M],mempool[M*50],*C=mempool;
int n,m,k,a[M];
ll sum[M],key_k=1;
abcd* New_Node(abcd *_,abcd *__,int ___)
{
	C->ls=_;
	C->rs=__;
	C->num=___;
	return C++;
}
abcd* Build_Tree(abcd *p,ll x,ll y,ll hash)
{
	ll mid=(x>>1)+(y>>1)+(x&y&1);
	if(x==y)
		return New_Node(0x0,0x0,p->num+1);
	if(hash<=mid)
		return New_Node(Build_Tree(p->ls,x,mid,hash),p->rs,p->num+1);
	else
		return New_Node(p->ls,Build_Tree(p->rs,mid+1,y,hash),p->num+1);
}
bool Get_Ans(abcd *p1,abcd *p2,ll x,ll y,ll hash)
{
	ll mid=(x>>1)+(y>>1)+(x&y&1);
	if(p2->num-p1->num==0)
		return 0;
	if(x==y)
		return 1;
	if(hash<=mid)
		return Get_Ans(p1->ls,p2->ls,x,mid,hash);
	else
		return Get_Ans(p1->rs,p2->rs,mid+1,y,hash);
}
int main()
{
	int i,j,x,y,z;
	bool ans;
	cin>>n>>m>>k;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]*key+a[i];
	}
	for(i=1;i<=k;i++)
		key_k*=key;
	tree[k-1]=New_Node(C,C,0);
	for(i=k;i<=n;i++)
		tree[i]=Build_Tree(tree[i-1],0ull,18446744073709551615ull,sum[i]-sum[i-k]*key_k);
	for(i=1;i<=m;i++)
	{
		ll hash=0;
		scanf("%d%d",&x,&y);
		for(j=1;j<=k;j++)
			scanf("%d",&z),hash=hash*key+z;
		if(y-x+1<k)
			ans=0;
		else
			ans=Get_Ans(tree[x+k-2],tree[y],0ull,18446744073709551615ull,hash);
		printf("%s\n",ans?"No":"Yes");
	}
}

BZOJ 3207 花神的嘲讽计划I Hash+可持久化线段树