6K4C0G - Online C++0x Compiler & Debugging Tool

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define file "o"
#define ff(i,a,b) for(auto i=(a); i<=(b); ++i)
#define ffr(i,b,a) for(auto i=(b); i>=(a); --i)
#define nl "\n"
#define ss " "
#define pb emplace_back
#define fi first
#define se second
#define sz(s) (int)(s).size()
#define all(s) (s).begin(), (s).end()
#define ms(a,x) memset(a,x,sizeof(a))
#define cn continue
#define re exit(0)

typedef long long ll;
typedef vector<int> vi;

inline void rf(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if(fopen(file".inp","r")){
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    }
}

struct BIT {
    int n; vi f;
    BIT(){} BIT(int n):n(n),f(n+1,0){}
    inline void add(int i,int v){ for(; i<=n; i+=i&-i) f[i]+=v; }
    inline int sum(int i){ int r=0; for(; i>0; i-=i&-i) r+=f[i]; return r; }
};

struct MST {
    int n; vector<vi> t;
    MST(){}
    MST(const vector<int>& a){ build(a); }
    void build(const vector<int>& a){
        int m = (int)a.size();
        n = 1; while(n < m) n <<= 1;
        t.assign(2*n, {});
        for(int i=0;i<m;i++) t[n+i] = {a[i]};
        for(int i=n-1;i>=1;i--){
            auto &L=t[i<<1], &R=t[i<<1|1];
            t[i].resize(sz(L)+sz(R));
            merge(all(L), all(R), t[i].begin());
        }
    }
    void collect(int l,int r, vector<int>& nodes){
        l+=n; r+=n;
        vector<int> left, right;
        while(l<=r){
            if(l&1){ left.pb(l); l++; }
            if(!(r&1)){ right.pb(r); r--; }
            l>>=1; r>>=1;
        }
        reverse(all(right));
        nodes.clear();
        nodes.reserve(sz(left)+sz(right));
        for(int id:left) nodes.pb(id);
        for(int id:right) nodes.pb(id);
    }
};

int main(){
    rf();
    int n; if(!(cin>>n)) return 0;

    vector<vi> g1(n), g2(n);
    ff(i,0,n-1){
        int d; cin>>d; g1[i].reserve(d);
        ff(j,1,d){int x;cin>>x; g1[i].pb(x);}
    }
    ff(i,0,n-1){
        int d; cin>>d; g2[i].reserve(d);
        ff(j,1,d){int x;cin>>x; g2[i].pb(x);}
    }

    auto dfs = [&](const vector<vi>& g){
        vi tin(n), tout(n), it(n,0); vector<char> vis(n,0);
        vector<int> st; st.pb(0); int T=0;
        while(!st.empty()){
            int v=st.back();
            if(!vis[v]){vis[v]=1; tin[v]=T++;}
            if(it[v]<(int)g[v].size()){int u=g[v][it[v]++]; st.pb(u);}
            else{tout[v]=T; st.pop_back();}
        }
        return pair<vi,vi>(tin,tout);
    };

    auto p1=dfs(g1), p2=dfs(g2);
    vi tin1=p1.fi, tout1=p1.se, tin2=p2.fi, tout2=p2.se;

    vi ordX(n); ff(v,0,n-1) ordX[tin1[v]]=v;
    vi posX(n); ff(i,0,n-1) posX[ordX[i]]=i;

    vi y2node(n); ff(v,0,n-1) y2node[tin2[v]]=v;
    vector<int> P(n);
    ff(y,0,n-1){int v=y2node[y]; P[y]=posX[v];} // x in [0..n-1]

    MST mst(P);
    BIT bit(n+2);

    int q; cin>>q;
    vector<string> ans(q);
    vector<int> nodes; nodes.reserve(64);
    vector<int> used; used.reserve(n);

    ff(i,0,q-1){
        int u,v; cin>>u>>v;
        int Lx=tin1[u], Rx=tout1[u]-1;          // x-range inclusive
        int Ly=tin2[v], Ry=tout2[v]-1;          // y-range inclusive
        if(Lx>Rx || Ly>Ry){ ans[i]="YES"; cn; }

        mst.collect(Ly,Ry,nodes);
        ll inv=0; int inserted=0;
        used.clear();

        for(int id: nodes){
            const auto &vec = mst.t[id];
            auto itL = lower_bound(all(vec), Lx);
            auto itR = upper_bound(all(vec), Rx);
            for(auto it=itL; it!=itR; ++it){
                int x = *it + 1;               // BIT is 1-based
                inv += inserted - bit.sum(x);
                bit.add(x,1);
                used.pb(x);
                ++inserted;
            }
        }

        for(int x: used) bit.add(x,-1);
        ans[i] = (inv==0 ? "YES" : "NO");
    }

    ff(i,0,q-1) cout<<ans[i]<<nl;
    re;
}