2024年1月9日总结-526互联

J 题

题意描述

有一个数组 $A$ 和 $B$, 询问给出 $x, y$ 问 $A[1, x]$ 组成的集合和 $B[1, y]$ 组成的集合是否相同。

另 $S_{0, i}$ 表示 $A$ 的前 $i$ 项组成的集合, $S_{1, i}$ 表示 $B$ 的前 $i$ 项组成的集合

如果有一部分 $S_{1, j}$ 包含 $S_{0, i}$, 那么前缀就长这个样

|-----------------|----------------|---------------|
$S_{0, k} \in S_{0, i}\ \ \ \ \ \ \ \ $ $S_{0, k} = S_{0, i}\ \ \ \ \ \ \ $ $S_{0, i} \in S_{0, k}$

|-----------------|----------------|---------------|
$S_{1, k} \in S_{0, i}\ \ \ \ \ \ \ \ $ $S_{1, k} = S_{0, i}\ \ \ \ \ \ \ $ $S_{0, i} \in S_{1, k}$

如果没有, 图长这样

|-----------------|----------------|---------------|
$S_{0, k} \in S_{0, i}\ \ \ \ \ \ \ \ $ $S_{0, k} = S_{0, i}\ \ \ \ \ \ \ $ $S_{0, i} \in S_{0, k}$

|------------------------|-------------------------|
$S_{1, k} \notin S_{0, i}\ \ \ \ \ \ \ \ $ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ $S_{0, i} \notin S_{1, k}$

可以发现, 随着 $i$ 的增大, 对于 $S_{1, j}$ 的 $j$ 也在增大, 双指针维护可行区间即可

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int x, y, n, q, a[N], b[N], MR[N], ML[N];

set<int>s1, s2;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  for(int i = 1; i <= n; ++i){
    cin >> b[i];
  }
  for(int i = 1, l = 1, r = 1; i <= n; ++i){
    if(s2.find(a[i]) == s2.end()){
      s1.insert(a[i]);
    }
    for(; l <= n && (s1.find(b[l]) != s1.end() || s2.find(b[l]) != s2.end()) && s1.size(); l++){
      if(s1.find(b[l]) != s1.end()){
        s1.erase(b[l]);
      }
      s2.insert(b[l]);
    }
    for(; r <= n && s2.find(b[r]) != s2.end(); r++){
    }
    if(0 == s1.size()){
      ML[i] = l - 1, MR[i] = r - 1;
    }
  }
  cin >> q;
  for(int i = 1; i <= q; ++i){
    cin >> x >> y;
    cout << (y >= ML[x] && y <= MR[x] ? "Yes\n" : "No\n");
  }
  return 0;
}