题目描述
给定两个序列A=(a_1,a_2,...,a_N)和B=(b_1,b_2,...,b_n)。
对于i=1,2,...,Q，回答下面的问题：
如果序列A的前x_i个元素A_1,A_2,...,A_{x_i}构成的集合和序列B的前y_i个元素B_1,B_2,...,B_{y_i}构成的集合相等，输出Yes，否则输出No。
题目分析和解题思路
对于A的任一前缀集合，B要么没有前缀集合与之相等，要么有一个区间[a,b]，前a,a+1,...,b个元素分别组成的前缀集合都和A的前缀集合相等。同样的，对于B的任一前缀集合，A要么没有前缀集合与之相等，要么有一个区间[a,b]，前a,a+1,...,b个元素分别组成的前缀集合都和B的前缀集合相等，因此我们可以同时遍历A，B两个序列，在遍历过程中分别维护前缀集合，保证B的前缀集合一定是A的子集，当B的前缀集合和A的前缀集合相等时就记录下来。
代码
时间复杂度为O(n)。
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> A,B;
for (int i=0;i<n;i++) {
int temp;
cin >> temp;
A.push_back(temp);
}
for (int i=0;i<n;i++) {
int temp;
cin >> temp;
B.push_back(temp);
}
set<int> prefix_a, prefix_b;
map<int,pair<int,int> > match;
int i = 0,j = 0, pb=-1;
for (;i<n;) {
prefix_a.insert(A[i]);
for (;j<n&&prefix_a.count(B[j])&&prefix_a.size()>prefix_b.size();j++) {
prefix_b.insert(B[j]);
}
if (prefix_a.size()==prefix_b.size()) {
int k = i;
for (k=i;k<n&&prefix_a.count(A[k]);k++) {
match[k] = {j-1,-1};
}
for (;j < n &&prefix_a.count(B[j]);j++)
{}
for (;i<n&&prefix_a.count(A[i]);i++) {
match[i].second = j-1;
}
}
else {
i++;
}
}
int q;
cin >> q;
for(;q>0;q--) {
int a,b;
cin >> a >> b;
a--;
b--;
if (!match.count(a)) {
cout << "No" << endl;
}
else if (match[a].first <= b && b <= match[a].second) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
}