【BZOJ3207】花神的嘲讽计划Ⅰ

#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef unsigned long long ll;const int maxn=200010;ll hash[maxn],seed[maxn];int v[maxn],rt[maxn];int n,m,k,tot;const ll inf=-1;struct sag{	int ls,rs,siz;}s[maxn*50];int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}void insert(int x,int &y,ll l,ll r,ll pos){	if(pos>r)	return ;	y=++tot;	if(l==r)	{		s[y].siz=s[x].siz+1;		return ;	}	ll mid=l/2+r/2+(l&r&1);	if(pos<=mid)	s[y].rs=s[x].rs,insert(s[x].ls,s[y].ls,l,mid,pos);	else	s[y].ls=s[x].ls,insert(s[x].rs,s[y].rs,mid+1,r,pos);	s[y].siz=s[s[y].ls].siz+s[s[y].rs].siz;}int query(int x,int y,ll l,ll r,ll pos){	if(l==r)	return s[y].siz-s[x].siz;	ll mid=l/2+r/2+(l&r&1);	if(pos<=mid)	return query(s[x].ls,s[y].ls,l,mid,pos);	else	return query(s[x].rs,s[y].rs,mid+1,r,pos);}int main(){	n=rd(),m=rd(),k=rd();	int i,j,a,b;	ll t;	for(seed[0]=1,i=1;i<=k;i++)	seed[i]=seed[i-1]*131;	for(i=1;i<=n;i++)	v[i]=rd();	for(i=1;i<=k;i++)	hash[1]=hash[1]*131+v[i];	for(i=k+1;i<=n;i++)	hash[i-k+1]=hash[i-k]*131-v[i-k]*seed[k]+v[i];	for(i=1;i<=n-k+1;i++)	insert(rt[i-1],rt[i],0,inf,hash[i]);	for(i=1;i<=m;i++)	{		a=rd(),b=rd()-k+1;		for(t=0,j=1;j<=k;j++)	t=t*131+rd();		if(query(rt[a-1],rt[b],0,inf,t))	printf("No\n");		else	printf("Yes\n");	}	return 0;}