题解

不用主席树的做法，但思想和主席树差不多。

首先肯定是将所有 $k$ 的区间转换成哈希值，不用多说。然后问题就是在 $[l+k-1,r]$ 中有没有出现这个哈希值。

考虑转化。

我们可以先离散化以下，然后用桶储存 $A$ 中每个哈希值出现的位置，查询时在对应的桶里二分，看看第一个大于等于 $l+k-1$ 的值 $x$ 和最后一个小于等于 $r$ 的值 $y$，看看是否满足 $x\le y$。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
namespace cjdst{

	template <typename T>
	class Fenwick_Tree{
		std::vector <T> tr;
		int n;

		public:

		Fenwick_Tree(){}
		Fenwick_Tree(int n, std::vector <T> a){
			tr.resize(n + 5, 0);
			this -> n = n;
			for(int i = 1; i <= n; i++){
				tr[i] += a[i];
				if(i + (i & (-i)) <= n){
					tr[i + (i & (-i))] += tr[i];
				}
			}
		}
		void modify(int idx, T val){
			for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
		}
		T query(int idx){
			T ans = 0;
			for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
			return ans;
		}
	};

	template <typename T>
	class Segtree{
		std::vector <T> tr;
		std::vector <int> left, right;
		std::vector <T> lazytag;
		void push_up(int u){
			tr[u] = tr[u << 1] + tr[u << 1 | 1];
		}
		void push_down(int u){
			tr[u << 1] += (right[u << 1] - left[u << 1] + 1) * lazytag[u];
			tr[u << 1 | 1] += (right[u << 1 | 1] - left[u << 1 | 1] + 1) * lazytag[u];
			lazytag[u << 1] += lazytag[u];
			lazytag[u << 1 | 1] += lazytag[u];
			lazytag[u] = 0;
		}
		void build(int u, int l, int r, std::vector <T> &a){
			left[u] = l, right[u] = r;
			if(l == r){
				tr[u] = a[l];
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid, a);
			build(u << 1 | 1, mid + 1, r, a);
			push_up(u);
		}
		void _modify(int u, int l, int r, T val){
			if(left[u] >= l && right[u] <= r){
				tr[u] += (right[u] - left[u] + 1) * val;
				lazytag[u] += val;
				return;
			}
			push_down(u);
			if(right[u << 1] >= l) _modify(u << 1, l, r, val);
			if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
			push_up(u);
		}
		T _query(int u, int l, int r){
			if(left[u] >= l && right[u] <= r){
				return tr[u];
			}
			push_down(u);
			T ans = 0;
			if(right[u << 1] >= l) ans += _query(u << 1, l, r);
			if(left[u << 1 | 1] <= r) ans += _query(u << 1 | 1, l, r);
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n, std::vector <T> a){
			tr.resize(n * 4 + 5);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			lazytag.resize(n * 4 + 5);
			build(1, 1, n, a);
		}
		void modify(int l, int r, T val){
			_modify(1, l, r, val);
		}
		T query(int l, int r){
			return _query(1, l, r);
		}
	};
	
	class dsu{
		std::vector <int> father, siz;

		public:

		int n, unions;
		dsu(){
			n = 0;
		}
		dsu(int n){
			this -> n = n;
			unions = n;
			father.resize(n + 5, 0);
			siz.resize(n + 5, 1);
			for(int i = 1; i <= n; i++){
				father[i] = i;
			}
		}
		int find(int n){
			return (father[n] == n ? n : father[n] = find(father[n]));
		}
		void merge(int x, int y){
			x = find(x), y = find(y);
			if(x == y) return;
			if(siz[x] < siz[y]) std::swap(x, y);
			siz[x] += siz[y];
			father[y] = x;
			unions--;
		}
	};
	
	template <typename T, int siz>
	class matrix{
		public:

		std::vector <std::vector <T>> a;
		T mod;
		matrix(T m){
			a.resize(siz, std::vector <T>(siz, 0));
			mod = m;
		}
		matrix(std::vector <std::vector <T>> v, T m){
			a = v;
			mod = m;
		}
		matrix operator * (matrix <T, siz> b){
			matrix <T, siz> ans(mod);
			for(int i = 0; i < siz; i++){
				for(int k = 0; k < siz; k++){
					for(int j = 0; j < siz; j++){
						ans.a[i][j] += a[i][k] * b.a[k][j] % mod;
						ans.a[i][j] %= mod;
					}
				}
			}
			return ans;
		}
	};

	void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
	}

	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;

	void solve(){
		const int mul = 131;
		int n, m, k;
		std::cin >> n >> m >> k;
		ull ksm = 1;
		for(int i = 1; i <= k; i++){
			ksm *= mul;
		}
		std::vector <int> a(n + 5, 0);
		std::vector <ull> hash(n + 5, 0);
		std::vector <ull> query(m + 5, 0);
		std::vector <int> left(m + 5, 0), right(m + 5, 0); 
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			hash[i] = hash[i - 1] * mul + a[i];
			if(i > k){
				hash[i] -= a[i - k] * ksm;
			}
			// std::cout << hash[i] << ' ';
		}
		
		for(int i = 1; i <= m; i++){
			int l, r;
			std::vector <int> b(k + 5, 0);
			std::cin >> l >> r;
			ull cur = 0;
			for(int j = 1; j <= k; j++){
				std::cin >> b[j];
				cur = cur * mul + b[j];
			}
			query[i] = cur;
			left[i] = l;
			right[i] = r;
		}
		
		std::vector <ull> mp{0};
		for(int i = k; i <= n; i++){
			mp.push_back(hash[i]);
		}
		for(int i = 1; i <= m; i++){
			mp.push_back(query[i]);
		}
		std::sort(mp.begin(), mp.end());
		for(int i = k; i <= n; i++){
			hash[i] = lower_bound(mp.begin(), mp.end(), hash[i]) - mp.begin();
		}
		for(int i = 1; i <= m; i++){
			query[i] = lower_bound(mp.begin(), mp.end(), query[i]) - mp.begin();
		}
		
		std::vector <std::vector <int>> bucket(mp.size() + 5, std::vector <int>{0});
		for(int i = k; i <= n; i++){
			bucket[hash[i]].push_back(i);
		}
		
		for(int i = 1; i <= m; i++){
			if(right[i] - left[i] + 1 < k){
				std::cout << "Yes\n";
				continue;
			}
			left[i] += k - 1;
			int idx1 = lower_bound(bucket[query[i]].begin(), bucket[query[i]].end(), left[i]) - bucket[query[i]].begin();
			int idx2 = upper_bound(bucket[query[i]].begin(), bucket[query[i]].end(), right[i]) - bucket[query[i]].begin() - 1;
			if(idx1 > idx2){
				std::cout << "Yes\n";
			}else{
				std::cout << "No\n";
			}
		}
	}
}


int main(){
	cjdst::init();
	int T = 1;
	// std::cin >> T;
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}
	std::cout.flush();

	return 0;
}

时间复杂度：$O((n+m)\log (n+m))$。