#include <bits/stdc++.h>
using namespace std;
int c[500005], d[500005], e[500005], X[500005], Y[500005], bit[500005], ans[500005], n, q;
vector<pair<pair<int, int>, pair<int, int> > > event;
vector<int> a[500005], store[500005];
void update(int x, int y)
{
for (int i=x; i<=n; i+=i&(-i))
bit[i]+=y;
}
int query(int x)
{
int res=0;
for (int i=x; i; i-=i&(-i))
res+=bit[i];
return res;
}
void solve(int t)
{
for (int i=1; i<=n; i++)
bit[i]=0;
sort(event.begin(), event.end());
int ind=0;
set<int> s;
for (int i=1; i<=n; i++)
{
while (ind<event.size() && event[ind].first.first==i)
{
if (event[ind].first.second)
{
if (query(event[ind].second.first-1)==query(event[ind].second.second))
ans[event[ind].first.second]=1;
}
else if (event[ind].second.first)
{
if (t)
{
while (s.size() && *prev(s.end())>=event[ind].second.second)
{
update(*prev(s.end()), 1);
s.erase(prev(s.end()));
}
}
else
{
while (s.size() && *s.begin()<=event[ind].second.second)
{
update(*s.begin(), 1);
s.erase(s.begin());
}
}
}
else
s.insert(event[ind].second.second);
ind++;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=1; i<n; i++)
cin >> c[i];
for (int i=1; i<=n; i++)
{
int m;
cin >> m;
while (m--)
{
int x;
cin >> x;
a[i].push_back(x);
}
d[i]=n+1;
}
for (int i=1; i<=n; i++)
{
store[c[i-1]].push_back(i);
for (int x:a[i])
{
for (int y:store[x])
d[y]=i;
store[x].clear();
}
}
for (int i=1; i<=n; i++)
store[i].clear();
for (int i=n; i>=1; i--)
{
store[c[i]].push_back(i);
for (int x:a[i])
{
for (int y:store[x])
e[y]=i;
store[x].clear();
}
}
cin >> q;
for (int i=1; i<=q; i++)
cin >> X[i] >> Y[i];
for (int i=1; i<=n; i++)
{
event.push_back({{e[i]+1, 0}, {0, i}});
event.push_back({{i, 0}, {1, d[i]-1}});
}
for (int i=1; i<=q; i++)
if (X[i]<Y[i])
event.push_back({{X[i], i}, {X[i], Y[i]-1}});
solve(0);
event.clear();
for (int i=1; i<=n; i++)
{
event.push_back({{n-d[i]+2, 0}, {0, i}});
event.push_back({{n-i+1, 0}, {1, e[i]+1}});
}
for (int i=1; i<=q; i++)
if (X[i]>Y[i])
event.push_back({{n-X[i]+1, i}, {Y[i]+1, X[i]}});
solve(1);
for (int i=1; i<=q; i++)
cout << (ans[i]?"YES":"NO") << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |