【hash+主席树】花神的嘲讽计划Ⅰ

主席树, 哈希

传送门：BZOJ3207

思路：蛤希（unsigned long long自然溢出）以后即为判断区间内有没有一个数，主席树即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define uLL unsigned long long
#define N 1200000
const int B=129;
int n,m,p,cnt,x,L,R,root[N],sum[N*6],ls[N*6],rs[N*6];
uLL tmp,pw[N],hs[N];
int getint(){
	char ch; int sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
void ins(int &rt,int rt2,uLL l,uLL r,uLL k){
	if (!rt) rt=++cnt; sum[rt]=sum[rt2];
	if (l==r){sum[rt]++; return;}
	uLL mid=(l>>1)+(r>>1)+((l&1)&(r&1));
	if (k<=mid){rs[rt]=rs[rt2]; ins(ls[rt],ls[rt2],l,mid,k);}
	if (k>mid){ls[rt]=ls[rt2]; ins(rs[rt],rs[rt2],mid+1,r,k);}
	sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
int query(int rt,uLL l,uLL r,uLL k){
	if (!rt || sum[rt]==0) return 0;
	if (l==r) return sum[rt];
	uLL mid=(l>>1)+(r>>1)+((l&1)&(r&1));
	if (k<=mid) return query(ls[rt],l,mid,k); if (k>mid) return query(rs[rt],mid+1,r,k);
	return 0;
}
	
int main(){
	n=getint(); m=getint(); p=getint();
	pw[0]=1; for (int i=1;i<=p;i++) pw[i]=pw[i-1]*B;
	for (int i=1;i<=n;i++){
		x=getint(); hs[i]=hs[i-1]*B+x;
		if (i>=p){tmp=hs[i]-hs[i-p]*pw[p]; ins(root[i],root[i-1],0,-1,tmp);}
	}
	for (int i=1;i<=m;i++){
		L=getint(); R=getint(); L+=p-1;
		for (int j=1;j<=p;j++){x=getint(); hs[j]=hs[j-1]*B+x;};
		if (L>R){puts("Yes"); continue;}
		if (query(root[R],0,-1,hs[p])-query(root[L-1],0,-1,hs[p])) puts("No"); else puts("Yes");
	}
	
	return 0;
}