[NOISG 2023 Finals] Curtains
给定 \(m\) 个区间 \([l_i, r_i]\)，\(q\) 次询问，回答是否存在若干区间的并恰好为 \([u_i, v_i]\)。
\(1 \le n, m,q \le 5 \times 10^5\)，\(1 \le l_i \le r_i \le n\)
离线进行扫描线是显然的。把询问挂在 \(r\) 上，处理 \(l\) 的答案。
显然，对于询问 \([L,R]\)，所有满足 \(L \le l_i \le R\) 的区间的并必须恰好为 \([L, R]\)，有两个方向：
第一种
考虑把区间填满：如果有位置 \(L \le i \le R\) 没有任何区间覆盖到，则该询问 NO。所以考虑对于每一个位置 \(i\) 记录覆盖该点的区间中 \(l\) 的最大值：
那么就要求 \(\forall L \le i \le R\)，\(f_i \ge L\)，即 \(\min \limits_{L \le i \le R} f_i \ge L\)（实际上由于 \(f_i \le i\)，此处 \(\min \limits_{L \le i \le R} f_i=L\)）。
得出为 YES 的充要条件。
那么 \(f\) 怎么维护呢，这显然是一个区间取 \(\max\)，区间求 \(\min\) 的问题，线段树可以直接维护。
第二种
考虑让区间相连接。维护 \(g_i\) 表示左端点为 \(i\)，最远能覆盖到哪里。询问 \([l,r]\) 为 YES 的充要条件是 \(g_l = r\)。
加入一个区间 \([l,r]\)，会使满足 \(i \le l\) 且 \(g_i \ge l\) 的 \(g_i \gets r\)。这个看似不好维护，实际上可以维护 min，在所有 \(g_i\) 都满足的区间上做区间赋值，其余暴力到叶子，复杂度不高于双 log。听说还能直接打标记维护。