loj 6095 花神的嘲讽计划 题解

题目

哈希记录每个 \(k\) 长度的串，询问的时候可以拿主席树或二分，这里说下二分。
将 \(n-k+1\) 个串从小到大排序，以哈希值为第一关键字，序号为第二关键字。
每次询问直接查找大于等于当前哈希值的位置即可，找到之后判断一下合不合法即可。
具体看代码：

#include<bits/stdc++.h>
typedef unsigned long long ull;
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=1e5+10;
const ull P=133331;
int n,m,k,cnt,a[N],temp[N],len,q[30],root[N];
ull hash[N];
struct HASH{
	ull hs;int l;
}h[N];
inline ull qpow(ull a,ull b){
	ull ans=1;
	for(;b;b>>=1,a*=a)if(b&1)ans=ans*a;
	return ans;
}
inline bool cmp(HASH a,HASH b){if(a.hs==b.hs)return a.l<b.l;return a.hs<b.hs;}
int main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	n=read(),m=read(),k=read();
	ull mul=qpow(P,k);
	for(int i=1;i<=n;++i)a[i]=read(),hash[i]=hash[i-1]*P+a[i];
	n=n-k+1;
	for(int i=1;i<=n;++i)
		h[i].l=i,h[i].hs=hash[i+k-1]-hash[i-1]*mul;
	std::stable_sort(h+1,h+n+1,cmp);
	for(int i=1;i<=m;++i){
		int l=read(),r=read()-k+1;
		HASH zc={0,l};
		for(int j=1;j<=k;++j)zc.hs=zc.hs*P+read();
		int pd=std::lower_bound(h+1,h+n+1,zc,cmp)-h;
		if(pd<=n&&h[pd].l<=r&&h[pd].hs==zc.hs)std::cout<<"No\n";
		else std::cout<<"Yes\n";
	}
}

写这个题解主要是因为有些思维定式了，一开始没读懂题意，看题解去了，发现有个二分的做法，因为老想着主席树，所以一眼不知道二分咋做，问了int_R他说这不一眼，然后我发现好像确实一眼，并且代码难度小多了。
学些数据结构导致把前面基础的东西忘了还是挺可怕的。故写篇题解提醒一下以后的自己，不要忘记之前的一些基础算法。