Loj 6169 相似序列

Posted on | Views:

Hash + 主席树.

给每种元素随机分配一个大权值,若两个区间内权值和相等,就可以认为它们在排序后是一样的.

现在可以允许排序后有一个位置不同.

以权值为下标建出主席树,二分出第一个不能匹配的权值 $x$ ,最后一个不能被匹配的权值 $y$ .

若 $x,y$ 是来自两个不同的子串,且 $[x,y]$ 内没有其它权值,说明排序后它们位置能对应上,两个子串就相似了.

可以记录一下每种权值的个数,方便判断.

时间复杂度 $O(n\log n)$ .

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
typedef unsigned long long ull;
ull gen()
{
	ull a = rand(), b = rand(), c = rand(), d = rand();
	return a | (b << 15) | (c << 30) | (d << 45);
}
const int N = 1e5 + 10;
int n, m = 100000, q, idx, a[N], ls[N * 20], rs[N * 20], cnt[N * 20], rt[N];
ull val[N], b[N], sum[N * 20];
void upd(int &x, int lst, int l, int r, int pos, ull c)
{
	x = ++idx;
	ls[x] = ls[lst], rs[x] = rs[lst], cnt[x] = cnt[lst], sum[x] = sum[lst];
	++cnt[x], sum[x] += c;
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	if (pos <= mid)
		upd(ls[x], ls[lst], l, mid, pos, c);
	else
		upd(rs[x], rs[lst], mid + 1, r, pos, c);
}
int tx, ty;
int query_first(int A, int B, int C, int D, int l, int r)
{
	if (l == r)
	{
		if (sum[B] - sum[A] == sum[D] - sum[C])
			return -1;
		tx = cnt[B] - cnt[A] - (cnt[D] - cnt[C]);
		return l;
	}
	int mid = (l + r) >> 1;
	if (sum[ls[B]] - sum[ls[A]] != sum[ls[D]] - sum[ls[C]])
		return query_first(ls[A], ls[B], ls[C], ls[D], l, mid);
	else
		return query_first(rs[A], rs[B], rs[C], rs[D], mid + 1, r);
}int query_last(int A, int B, int C, int D, int l, int r)
{
	if (l == r)
	{
		if (sum[B] - sum[A] == sum[D] - sum[C])
			return -1;
		ty = cnt[B] - cnt[A] - (cnt[D] - cnt[C]);
		return l;
	}
	int mid = (l + r) >> 1;
	if (sum[rs[B]] - sum[rs[A]] != sum[rs[D]] - sum[rs[C]])
		return query_last(rs[A], rs[B], rs[C], rs[D], mid + 1, r);
	else
		return query_last(ls[A], ls[B], ls[C], ls[D], l, mid);
}
int query_cnt(int A, int B, int C, int D, int l, int r, int L, int R)
{
	if (L <= l && r <= R)
		return cnt[B] - cnt[A] + cnt[D] - cnt[C];
	int res = 0, mid = (l + r) >> 1;
	if (L <= mid)
		res += query_cnt(ls[A], ls[B], ls[C], ls[D], l, mid, L, R);
	if (!res && R > mid)
		res += query_cnt(rs[A], rs[B], rs[C], rs[D], mid + 1, r, L, R);
	return res;
}
bool check(int A, int B, int C, int D)
{
	if (B - A != D - C)
		return false;
	int x = query_first(rt[A - 1], rt[B], rt[C - 1], rt[D], 1, m);
	if (x == -1)
		return true;
	int y = query_last(rt[A - 1], rt[B], rt[C - 1], rt[D], 1, m);
	if (x == y)
		return true;
	if ((tx > 0) == (ty > 0))
		return false;
	if (abs(tx) > 1 || abs(ty) > 1)
		return false;
	if (x + 1 > y - 1)
		return true;
	return query_cnt(rt[A - 1], rt[B], rt[C - 1], rt[D] ,1, m, x + 1, y - 1) == 0;
}
void solve()
{
	for (int i = 1; i <= idx; ++i)
		ls[i] = rs[i] = cnt[i] = sum[i] = 0;
	idx = 0;
	for (int i = 1; i <= m; ++i)
		val[i] = gen();
	n = read(), q = read();
	for (int i = 1; i <= n; ++i)
	{
		a[i] = read();
		b[i] = val[a[i]];
		upd(rt[i], rt[i - 1], 1, m, a[i], b[i]);
	}
	for (int t = 1; t <= q; ++t)
	{
		int A = read(), B = read(), C = read(), D = read();
		puts(check(A, B, C, D) ? "YES" : "NO");
	}
}
int main()
{
	srand(time(0));
	int T = read();
	while (T--)
		solve();
	return 0;
}