「BZOJ3207」花神的嘲讽计划Ⅰ

Description

DJ在讲课之前会有一个长度为NN方案,我们可以把它看作一个数列;
同样,花神在听课之前也会有一个嘲讽方案,有MM个,每次会在xxyy的这段时间开始嘲讽,为了减少题目难度,每次嘲讽方案的长度是一定的,为KK
花神嘲讽DJ让DJDJ尴尬需要的条件:
xyx\sim y的时间内DJDJ没有讲到花神的嘲讽方案,即J的讲课方案中的xyx\sim y没有花神的嘲讽方案【这样花神会嘲讽J不会所以不讲】。
经过众蒟蒻努力,在一次讲课之前得到了花神嘲讽的各次方案,DJ得知了这个消息以后欣喜不已,DJ想知道花神的每次嘲讽是否会让DJ尴尬【说不出话来】。

Input

1133个数NNMMKK
22NN个数,意义如上;
33行到第3+M13+M-1行,每行K+2K+2个数,前两个数为x,yx,y,然后KK个数,意义如上;

Output

对于每一个嘲讽做出一个回答会尴尬输出Yes,否则输出No

Sample Input

1
2
3
4
5
6
7
8 5 3
1 2 3 4 5 6 7 8
2 5 2 3 4
1 8 3 2 1
5 7 4 5 6
2 5 1 2 3
1 7 3 4 5

Sample Output

1
2
3
4
5
No
Yes
Yes
Yes
No

HINT

20%20\%的数据:1N10001\leq N\leq 1000;1M10001\leq M\leq 1000;
40%40\%的数据:1N100001\leq N\leq 10000;1M100001\leq M\leq 10000;
100%100\%的数据:1N1000001\leq N\leq 100000;1M1000001\leq M\leq 100000;yx+1Ny-x+1\leq N;
Kyx+1K\leq y-x+1
K20K\leq 20;
xyx\leq y;
题中所有数据不超过2×1092\times 10^9;保证方案序列的每个数字N\leq N

Solution

对每个点ii,记录[ik+1,i][i-k+1,i]的hash值,循环直接在主席树上查询,双hash,否则容易被卡。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120000;
struct TT {
struct T {
int l, r, c;
}t[N * 32];
int tot;
void ins(int pre, int &o, int l, int r, int x) {
o = ++tot;
t[o] = t[pre];
if(l == r) {
++t[o].c;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) ins(t[pre].l, t[o].l, l, mid, x);
else ins(t[pre].r, t[o].r, mid + 1, r, x);
}
int query(int o, int l, int r, int x) {
if(!o) return 0;
if(l == r) return t[o].c;
int mid = (l + r) >> 1;
if(x <= mid) return query(t[o].l, l, mid, x);
else return query(t[o].r, mid + 1, r ,x);
}
int rt[N];
}t1,t2;
int n, m, K;
const ll p1 = 1e9 + 7, p2 = 1e9 + 9;

ll a[N];

int main() {
n = read(), m = read(), K = read();
ll bin1 = 1, bin2 = 1;
ll v = (n + 1);
for(int i = 1; i < K; ++i) {
bin1 = bin1 * v % p1;
bin2 = bin2 * v % p2;
}
ll now1 = 0, now2 = 0;
for(int i = 1; i <= n; ++i) {
a[i] = read();
t1.rt[i] = t1.rt[i - 1];
t2.rt[i] = t2.rt[i - 1];
if(i > K) {
now1 = (now1 - bin1 * a[i - K] % p1 + p1) % p1;
now2 = (now2 - bin2 * a[i - K] % p2 + p2) % p2;
}
now1 = (now1 * v % p1+ a[i]) % p1;
now2 = (now2 * v % p2+ a[i]) % p2;
if(i >= K) {
t1.ins(t1.rt[i], t1.rt[i], 0, p1 - 1, now1);
t2.ins(t2.rt[i], t2.rt[i], 0, p2 - 1, now2);
}
}
for(int T = 1; T <= m; ++T) {
int x = read(), y = read();
now1 = 0;
now2 = 0;
for(int i = 1; i <= K; ++i) {
int x = read();
now1 = (now1 * v % p1 + x) % p1;
now2 = (now2 * v % p2 + x) % p2;
}
if(t1.query(t1.rt[y], 0, p1 - 1, now1) - t1.query(t1.rt[min(y, max(0, x + K - 1 - 1))], 0, p1 - 1, now1) > 0 &&
t2.query(t2.rt[y], 0, p2 - 1, now2) - t2.query(t2.rt[min(y, max(0, x + K - 1 - 1))], 0, p2 - 1, now2) > 0
) puts("No");
else puts("Yes");
}
return 0;
}