ABC250 E - Prefix Equality
作者:
江南_2
,
2022-10-05 11:46:30
,
所有人可见
,
阅读 192
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
typedef pair<ll, int> PLI;
const int N = 2e5 + 10;
const ll INF = 1e18;
const int mod = 998244353;
int n, m, sq;
int a[N], b[N];
int asz[N], bsz[N];
bool sz[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
scanf("%d", &m);
set<int> st;
for (int i = 1; i <= n; i ++ )
{
st.insert(a[i]);
asz[i] = st.size();
}
st.clear();
for (int i = 1; i <= n; i ++ )
{
st.insert(b[i]);
bsz[i] = st.size();
}
st.clear();
int i = 1, j = 1, k = 1;
while (k <= n)
{
while (i <= n && asz[i] <= k)
{
if (asz[i - 1] != asz[i])
{
auto it = st.find(a[i]);
if (it != st.end()) st.erase(it);
else st.insert(a[i]);
}
i ++ ;
}
while (j <= n && bsz[j] <= k)
{
if (bsz[j - 1] != bsz[j])
{
auto it = st.find(b[j]);
if (it != st.end()) st.erase(it);
else st.insert(b[j]);
}
j ++ ;
}
if (!st.size()) sz[k] = true;
k ++ ;
}
while (m -- )
{
int x, y;
scanf("%d%d", &x, &y);
if (asz[x] != bsz[y]) puts("No");
else if (sz[asz[x]]) puts("Yes");
else puts("No");
}
}