526互联

Codeforces Round 685 (Div. 2) B. Non-Substring Subsequence

发布时间 2023-10-13 15:33:09作者: zsxuan

对于一个长为 \(n\) 的 \(01\) 字符串 \(s\) 有 \(n\) 个询问。第 \(i\) 个询问被 \(l_i, r_i\) 描述 \(1 \leq l_i < r_i \leq n\) 。

对于每个询问，你需要确定 \(s\) 中是否存在一个子序列等同于子串 \(s[l_i \cdots r_i]\) 。

显然子序列可以和子串仅有一个字符不相同。于是 \(s_{l_i}\) 不是第一次出现，或者 \(s_{r_i}\) 不是最后一次出现。则存在一个合法子序列。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n, q; std::cin >> n >> q;
	std::string s; std::cin >> s;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) a[i] = s[i - 1] - '0';
	int fir[2] = {0}, lst[2] = {0};
	for (int i = 1; i <= n; i++) {
		if (!fir[a[i]]) fir[a[i]] = i;
		lst[a[i]] = i;
	}
	for (int i = 0; i < q; i++) {
		int l, r; std::cin >> l >> r;
		if (l != fir[a[l]] || r != lst[a[r]]) std::cout << "YES\n";
		else std::cout << "NO\n";
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}