因为 $K$ 是固定的，所以我们可以预处理每一段 $K$ 个的序列的哈希值，那么对于询问我们只要判断区间内是否有此哈希值即可
显然主席树维护，没了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef unsigned long long ull; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,base=1e9+7; int n,m,K,a[N]; ull h[N],fac[N],b[N]; inline ull get_h(int l,int r) { return h[r]-h[l-1]*fac[r-l+1]; } int rt[N],t[N*40],lc[N*40],rc[N*40],cnt; void ins(int &o,int l,int r,int pre,int v) { o=++cnt; t[o]=t[pre]+1; if(l==r) return; int mid=l+r>>1; if(v<=mid) ins(lc[o],l,mid,lc[pre],v),rc[o]=rc[pre]; else ins(rc[o],mid+1,r,rc[pre],v),lc[o]=lc[pre]; } bool query(int &o,int l,int r,int pre,int v) { if(l==r) return t[o]>t[pre]; int mid=l+r>>1; return v<=mid ? query(lc[o],l,mid,lc[pre],v) : query(rc[o],mid+1,r,rc[pre],v); } int main() { n=read(),m=read(),K=read(); for(int i=1;i<=n;i++) a[i]=read(); fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*base; for(int i=1;i<=n;i++) h[i]=h[i-1]*base+a[i]; n=n-K+1; for(int i=1;i<=n;i++) b[i]=get_h(i,i+K-1); sort(b+1,b+n+1); for(int i=1;i<=n;i++) ins(rt[i],1,n,rt[i-1], lower_bound(b+1,b+n+1,get_h(i,i+K-1))-b ); int l,r; ull now; while(m--) { l=read(),r=read()-K+1; now=0; for(int i=1;i<=K;i++) now=now*base+read(); if(l>r) { printf("Yes "); continue; } int pos=lower_bound(b+1,b+n+1,now)-b; if(b[pos]!=now) { printf("Yes "); continue; } if( query(rt[r],1,n,rt[l-1],pos) ) printf("No "); else printf("Yes "); } return 0; }