纵星辰陨落，你仍将歌唱。

宝宝题。

有结论：一个序列是合法的当且仅当不存在形如

a,b,a,b

的子序列。此时你删除中间的

a

或者

b

都会导致两侧的

a

或者

b

删不掉，而不存在这种子序列说明至多存在子序列

a,b,a

，此时删除中间的

b

之后可以拼合两边的

a

一起删除。

考虑上述子序列，一个四元组

(i,j,k,l)

满足

i<j<k<l

且

p=a_i=a_k

，

q=a_j=a_l

，

p\ne q

，他是一个上述的非法子序列，此时所有包含

[i,l]

的区间都非法。这个东西有支配对，首先可以只保留

j,l

是

q

相邻两次出现位置的四元组，贡献不劣，原因是如果

j,l

不是相邻的两次出现，那么

j

可以往右移或者

l

可以往左移，区间

[i,l]

的变化不劣。所以枚举

j

，此时

l

已经确定，

i

取最大的满足在

(j,l)

中存在一个

a_j=a_i

的位置即可。因此，对于一个

j

只有一个四元组是有贡献的，四元组总数

O(n)

。用线段树求四元组，扫描

j

的同时求出每个位置

x

上一次在

j

之前出现的位置，单点修改查询区间最大值。把得到的区间信息挂在

l

上，得到

p_k

表示当四元组的

l=k

时，左端点

i

最大是多少。

于是可以简单判断区间合法性。我们记

f_r

表示以

r

结尾的合法区间的左端点最小是多少，查询等于判断

f_r\le l

。

f

是好求的，等于

p

的前缀

\max

加一。

时间复杂度 1log。

CPP

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e5 + 10;
int n, Q, A[N], pos[N], nxt[N], res[N];

namespace Sgt {

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int tr[N << 2];
void build() { for (int i = 1; i <= n * 4; i ++) tr[i] = 0; }
void update(int p, int l, int r, int x, int k) {
	if (x > r || x < l) return ;
	if (l == r) { tr[p] = k; return ; }
	int mid = (l + r) >> 1;
	update(ls(p), l, mid, x, k), update(rs(p), mid + 1, r, x, k);
	tr[p] = max(tr[ls(p)], tr[rs(p)]); return ;
}
int query(int p, int l, int r, int x, int y) {
	if (x > r || y < l) return 0;
	if (x <= l && y >= r) return tr[p];
	int mid = (l + r) >> 1;
	return max(query(ls(p), l, mid, x, y), query(rs(p), mid + 1, r, x, y));
}

}

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	int _; cin >> _;
	while (_ --) {
		cin >> n >> Q; Sgt::build();
		for (int i = 1; i <= n; i ++) pos[i] = nxt[i] = res[i] = 0;
		for (int i = 1; i <= n; i ++) {
			cin >> A[i];
			if (pos[A[i]]) nxt[pos[A[i]]] = i;
			pos[A[i]] = i;
		}
		for (int i = 1; i <= n; i ++) {
			if (nxt[i]) res[nxt[i]] = Sgt::query(1, 1, n, i + 1, nxt[i] - 1);
			Sgt::update(1, 1, n, nxt[i], i);
		}
		for (int i = 1; i <= n; i ++) res[i] = max(res[i], res[i - 1]);
		int x, y;
		while (Q --) {
			cin >> x >> y; cout << (res[y] < x ? "YES\n" : "NO\n");
		}
	}
	return 0;
}

纵星辰陨落，你仍将歌唱。

文章操作

相关推荐

评论

纵星辰陨落，你仍将歌唱。