[BZOJ3207]花神的嘲讽计划Ⅰ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
	if(Head == Tail) {
		int l = fread(buffer, 1, BufferSize, stdin);
		Tail = (Head = buffer) + l;
	}
	return *Head++;
}
int read() {
	int x = 0, f = 1; char c = Getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
	return x * f;
}

#define oo 18446744073709551615llu
#define maxn 200010
#define maxnode 8000010
#define LL long long
#define UL unsigned LL

int ToT, sumv[maxnode], lc[maxnode], rc[maxnode];
void update(int& y, int x, UL l, UL r, UL p) {
	sumv[y = ++ToT] = sumv[x] + 1;
	if(l == r) return ;
	UL mid = l + (r - l >> 1); lc[y] = lc[x]; rc[y] = rc[x];
	if(p <= mid) update(lc[y], lc[x], l, mid, p);
	else update(rc[y], rc[x], mid+1, r, p);
	return ;
}
int query(int o, UL l, UL r, UL p) {
	if(!o) return 0;
	if(l == r) return sumv[o];
	UL mid = l + (r - l >> 1);
	if(p <= mid) return query(lc[o], l, mid, p);
	return query(rc[o], mid+1, r, p);
}

int A[maxn], rt[maxn];
UL idx[maxn], Hash[maxn];

int main() {
//	freopen("taunt3.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	int n = read(), q = read(), k = read();
	for(int i = 1; i <= n; i++) A[i] = read();
	idx[0] = 1;
	for(int i = 1; i <= n; i++) idx[i] = idx[i-1] * 233;
	for(int i = 1; i <= n; i++) Hash[i] = Hash[i-1] * 233 + A[i];
	for(int i = 1; i <= n - k + 1; i++) {
		UL tmp = Hash[i+k-1] - Hash[i-1] * idx[k];
//		printf("%llu(%d)%c", tmp, ToT, i < n - k + 1 ? ‘ ‘ : ‘\n‘);
		update(rt[i], rt[i-1], 0, oo, tmp);
	}
	while(q--) {
		int ql = read(), qr = read(); UL tmp = 0;
		for(int i = 1; i <= k; i++) tmp = tmp * 233 + read();
		if(qr - ql + 1 < k){ puts("Yes"); continue; }
//		printf("%d %d\n", query(rt[qr-k+1], 0, MOD - 1, tmp), query(rt[ql-1], 0, MOD - 1, tmp));
		puts(query(rt[qr-k+1], 0, oo, tmp) - query(rt[ql-1], 0, oo, tmp) ? "No" : "Yes"); // */
	}
	
	return 0;
}