#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; // supports: point modify, range apply, range query, walk to find first/last with some precedent // you are to implement the 2 structs Tag and Info // for the walks, pass a lambda that takes in Info and return true iff the node with that Info will contain the desired element template<class Info, class Tag> struct LazySegmentTree { int n; vector<Info> info; vector<Tag> tag; LazySegmentTree() : n(0) {} LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); } template<class T> LazySegmentTree(vector<T> init_) { init(init_); } void init(int n_, Info v_ = Info()) { init(vector<Info>(n_, v_)); } template<class T> void init(vector<T> init_) { n = init_.size(); info.assign(4 << __lg(n), Info()); tag.assign(4 << __lg(n), Tag()); function<void(int, int, int)> build = [&](int p, int l, int r) { if (r - l == 1) { info[p] = init_[l]; return; } int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m, r); pull(p); }; build(1, 0, n); } void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; } void apply(int p, const Tag &v) { info[p].apply(v); tag[p].apply(v); } void push(int p) { apply(2 * p, tag[p]); apply(2 * p + 1, tag[p]); tag[p] = Tag(); } void modify(int p, int l, int r, int x, const Info &v) { if (r - l == 1) { info[p] = v; return; } int m = (l + r) / 2; push(p); if (x < m) { modify(2 * p, l, m, x, v); } else { modify(2 * p + 1, m, r, x, v); } pull(p); } void modify(int p, const Info &v) { modify(1, 0, n, p, v); } Info rangeQuery(int p, int l, int r, int x, int y) { if (l >= y || r <= x) { return Info(); } if (l >= x && r <= y) { return info[p]; } int m = (l + r) / 2; push(p); return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y); } Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); } void rangeApply(int p, int l, int r, int x, int y, const Tag &v) { if (l >= y || r <= x) { return; } if (l >= x && r <= y) { apply(p, v); return; } int m = (l + r) / 2; push(p); rangeApply(2 * p, l, m, x, y, v); rangeApply(2 * p + 1, m, r, x, y, v); pull(p); } void rangeApply(int l, int r, const Tag &v) { return rangeApply(1, 0, n, l, r, v); } template<class F> int findFirst(int p, int l, int r, int x, int y, F &&pred) { if (l >= y || r <= x) { return -1; } if (l >= x && r <= y && !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = findFirst(2 * p, l, m, x, y, pred); if (res == -1) { res = findFirst(2 * p + 1, m, r, x, y, pred); } return res; } template<class F> int findFirst(int l, int r, F &&pred) { return findFirst(1, 0, n, l, r, pred); } template<class F> int findLast(int p, int l, int r, int x, int y, F &&pred) { if (l >= y || r <= x) { return -1; } if (l >= x && r <= y && !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = findLast(2 * p + 1, m, r, x, y, pred); if (res == -1) { res = findLast(2 * p, l, m, x, y, pred); } return res; } template<class F> int findLast(int l, int r, F &&pred) { return findLast(1, 0, n, l, r, pred); } }; struct Tag { int chmin = 1e9; void apply(const Tag &t) & { chmin = min(chmin, t.chmin); } }; struct Info { int mn = 1e9; void apply(const Tag &t) & { mn = min(mn, t.chmin); } Info operator+(const Info &b) { return {min(mn, b.mn)}; } }; struct Tag2 { int chmax = -1e9; void apply(const Tag2 &t) & { chmax = max(chmax, t.chmax); } }; struct Info2 { int mx = -1e9; void apply(const Tag2 &t) & { mx = max(mx, t.chmax); } Info2 operator+(const Info2 &b) { return {max(mx, b.mx)}; } }; template <class T> struct Fenwick { int n, log; vector<T> bit; Fenwick(int n) : n(n), log(32 - __builtin_clz(n + 1)), bit(n + 1, 0) {} void add(int i, T delta) { for (; i <= n; i += i & -i) { bit[i] += delta; } } T sum(int i) { T res = 0; for (; i > 0; i -= i & -i) { res += bit[i]; } return res; } T sum(int l, int r) { return sum(r)-sum(l-1); } int kth(T k) { T sum = 0; int pos = 0; for (int l = log - 1; l >= 0; l--) { if (pos + (1 << l) <= n && sum + bit[pos + (1 << l)] <= k) { pos += 1 << l; sum += bit[pos]; } } return pos; } }; void solve(){ int n; cin >> n; vector<int> a(n+1), b(n+1); for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ cin >> b[i]; } vector<int> lt(n+1, 0), rt(n+1, n+1); LazySegmentTree<Info, Tag> T1(n*2+1), T2(n*2+1); for(int i = n; i >= 1; i--){ rt[i] = min(rt[i], T1.rangeQuery(b[i], a[i]).mn); rt[i] = min(rt[i], T2.rangeQuery(a[i], a[i]+1).mn); T1.modify(a[i], {i}); T2.rangeApply(b[i], a[i], {i}); } LazySegmentTree<Info2, Tag2> T3(n*2+1), T4(n*2+1); for(int i = 1; i <= n; i++){ lt[i] = max(lt[i], T3.rangeQuery(b[i], a[i]).mx); lt[i] = max(lt[i], T4.rangeQuery(a[i], a[i]+1).mx); T3.modify(a[i], {i}); T4.rangeApply(b[i], a[i], {i}); } struct segment{ int l, id; }; vector<vector<int>> pos(n+2), neg(n+2); for(int i = 1; i <= n; i++){ if(lt[i] > 0) pos[i].push_back(lt[i]); pos[rt[i]].push_back(i); if(lt[i] > 0) neg[rt[i]].push_back(lt[i]); } Fenwick<int> bit(n+1); int Q; cin >> Q; vector<vector<segment>> q(n+1); vector<int> req(Q+1); for(int i = 1; i <= Q; i++){ int l, r; cin >> l >> r; q[r].push_back({l, i}); req[i] = r-l+1; } vector<int> ans(Q+1); for(int i = 1; i <= n; i++){ for(int j : pos[i]){ bit.add(j, 1); } for(int j : neg[i]){ bit.add(j, -1); } for(auto it : q[i]){ ans[it.id] = bit.sum(it.l, i); } } for(int i = 1; i <= Q; i++){ if(ans[i] == req[i]){ cout << "Yes"; }else{ cout << "No"; } cout << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }