考虑如何判定。从小到大考虑每个值 \(v\)，考察所有 \(i\) 使得 \(a_i\leq v<b_i\)，这些 \(i\) 需要 \(+1\)，如果此时不存在 \(i\) 使得 \(b_i=v\)，那么显然会剩下一个需要 \(+1\) 的 \(i\) 被留在当前层，这时候就不合法了。同时不难证明反过来必然合法。这样我们就得到了判定条件：
\[\bigcup_{i=l}^r [a_i,b_i)=\bigcup_{i=l}^r\{b_i\}
\]
注意到左边的式子变成 \(\bigcup\limits_{i=l}^r [a_i,b_i]\) 并不影响判定，此时右侧集合必定是左侧集合的子集，我们只需要判定集合大小是否相等即可。
右侧集合大小相当于区间数颜色，这是经典二维偏序问题。
左侧集合大小相当于求第 \(l\sim r\) 个区间的并集大小。考虑对右端点 \(r\) 扫描线，对于每个值 \(i\)，维护 \(id_i\) 表示编号最大的区间使得 \(i\in [a_{id_i},b_{id_i}]\)，那么查询就是求有多少 \(i\) 满足 \(id_i\geq l\)。对 \(id\) 维护一个权值树状数组，使用 ODT 维护 \(id\) 的连续段，每次增删连续段时在树状数组上单点修即可，查询就是求后缀和。时间复杂度为 \(\mathcal{O}((n+q)\log{n})\)。
代码很好写。
代码
#include <bits/stdc++.h>using namespace std;using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int N = 2.5e5 + 5;template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T> inline void chk_min(T &x, T y) { x = y < x ? y : x; }
template<typename T> inline void chk_max(T &x, T y) { x = x < y ? y : x; }int n, q, ans[N];
pii p[N];struct Query {int id, l, r;
} qr[N];struct BIT {int c[N];void init() { fill(c + 1, c + n + 1, 0); }int query(int x) {int res = 0;for (; x <= n; x += lowbit(x)) res += c[x];return res;}void add(int x, int v) {for (; x; x -= lowbit(x)) c[x] += v;}
} ft;struct ODT {struct Node {int l, r, id;friend bool operator<(const Node &lhs, const Node &rhs) { return lhs.l < rhs.l; }};set<Node> s;auto split(int x) {auto it = s.lower_bound({x});if (it != s.end() && it->l == x) return it;auto [l, r, v] = *--it;return s.erase(it), s.insert({l, x - 1, v}), s.insert({x, r, v}).first;}void assign(int l, int r, int v) {auto itr = split(r + 1), itl = split(l);for (auto it = itl; it != itr; ++it) {auto [x, y, id] = *it;ft.add(id, -(y - x + 1));}s.erase(itl, itr);ft.add(v, r - l + 1), s.insert({l, r, v});}
} odt;vector<int> array_operation(vector<int> A, vector<int> B, vector<int> L, vector<int> R) {n = A.size(), q = L.size();for (int i = 1; i <= q; ++i) qr[i] = {i, L[i - 1] + 1, R[i - 1] + 1};unordered_map<int, int> pos;for (int i = 1; i <= n; ++i) p[i] = {pos[B[i - 1]], i}, pos[B[i - 1]] = i;sort(p + 1, p + n + 1);sort(qr + 1, qr + q + 1, [](const Query &lhs, const Query &rhs) { return lhs.l < rhs.l; });for (int i = 1, j = 1; i <= q; ++i) {auto [id, l, r] = qr[i];while (j <= n && p[j].first < l) ft.add(p[j++].second, 1);ans[id] = ft.query(l) - ft.query(r + 1);}ft.init();sort(qr + 1, qr + q + 1, [](const Query &lhs, const Query &rhs) { return lhs.r < rhs.r; });odt.s.insert({1, (int)1e9, 0});for (int i = 1, j = 1; i <= n; ++i) {odt.assign(A[i - 1], B[i - 1], i);while (j <= q && qr[j].r == i) ans[qr[j].id] -= ft.query(qr[j].l), ++j;}for (int i = 1; i <= q; ++i) ans[i] = !ans[i];return vector<int>(ans + 1, ans + q + 1);
}