描述
称某个序列 B={b1,b2,⋯,bn} 是另一个序列 A={a1,a2,⋯,am} 的拓展当且仅当存在正整数序列 L={l1,l2,⋯,lm}，将 ai 替换为 li 个 ai 后得到序列 B。例如，
{1,3,3,3,2,2,2} 是 {1,3,3,2} 的拓展，取 L={1,1,2,3} 或 {1,2,1,3}；
而 {1,3,3,2} 不是 {1,3,3,3,2} 的拓展，{1,2,3} 不是 {1,3,2} 的拓展。
小 R 给了你两个序列 X 和 Y，他希望你找到 X 的一个长度为 l0=10100 的拓展 F={fi} 以及 Y 的一个长度为 l0 的拓展 G={gi}，使得任意 1≤i,j≤l0 都有 (fi−gi)(fj−gj)>0。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。
为了避免你扔硬币蒙混过关，小 R 还给了 q 次额外询问，每次额外询问中小 R 会修改 X 和 Y 中若干元素的值。你需要对每次得到的新的 X 和 Y 都进行上述的判断。
询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。
输入描述
输入的第一行包含四个整数 c,n,m,q，分别表示测试点编号、序列 X 的长度、序列 Y 的长度和额外询问的个数。对于样例，c 表示该样例与测试点 c 拥有相同的限制条件。
输入的第二行包含 n 个整数 x1,x2,⋯,xn，描述序列 X。
输入的第三行包含 m 个整数 y1,y2,⋯,ym，描述序列 Y。
接下来依次描述 q 组额外询问。对于每组额外询问：
输入的第一行包含两个整数 kx 和 ky，分别表示对序列 X 和 Y 产生的修改个数。
接下来 kx 行每行包含两个整数 px,vx，表示将 xpx 修改为 vx。
接下来 ky 行每行包含两个整数 py,vy，表示将 ypy 修改为 vy。
输出描述
输出一行，其中包含一个长度为 (q+1) 的 01 序列，序列的第一个元素表示初始询问的答案，之后 q 个元素依次表示每组额外询问的答案。对于每个询问，如果存在满足题目条件的序列 F 和 G，输出 1，否则输出 0。
样例输入 1
3 3 3 3
8 6 9
1 7 4
1 0
3 0
0 2
1 8
3 5
1 1
2 8
1 7
样例输出 1
1001
提示
【样例解释 #1】
由于 F 和 G 太长，用省略号表示重复最后一个元素直到序列长度为 l0。如 {1,2,3,3,⋯} 表示序列从第三个元素之后都是 3。
以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问：
A={8,6,9}，B={1,7,4}，取 F={8,8,6,9,⋯},G={1,7,4,4,⋯}；
A={8,6,0}，B={1,7,4}，可以证明不存在满足要求的方案；
A={8,6,9}，B={8,7,5}，可以证明不存在满足要求的方案；
A={8,8,9}，B={7,7,4}，取 F={8,8,9,⋯},G={7,7,4,⋯}。
【样例解释 #2】
该组样例满足测试点 4 的条件。
【样例解释 #3】
该组样例满足测试点 7 的条件。
【样例解释 #4】
该组样例满足测试点 9 的条件。
【样例解释 #5】
该组样例满足测试点 18 的条件。
【数据范围】
对于所有测试数据，保证：
1≤n,m≤5×105；
0≤q≤60；
0≤xi,yi<109；
0≤kx,ky≤5×105，且所有额外询问的 (kx+ky) 的和不超过 5×105；
1≤px≤n，1≤py≤m，0≤vx,vy<109；
对于每组额外询问，px 两两不同，py 两两不同。
测试点编号 n,m≤ 特殊性质
1 1 否
2 2 否
3,4 6 否
5 200 否
6,7 2000 否
8,9 4×104 是
10,11 1.5×105 是
12∼14 5×105 是
15,16 4×104 否
17,18 1.5×105 否
19,20 5×105 否
特殊性质：对于每组询问（包括初始询问和额外询问），保证 x1<y1，且 xn 是序列 X 唯一的一个最小值，ym 是序列 Y 唯一的一个最大值。
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 10;
int n, m, q, x[N], y[N], tx[N], ty[N];
bool flag;
struct Node {
int pre, suf;
void operator=(const int &x) {pre = suf = x;}
} X[N], Y[N];
bool check(const int x[], const int y[]) {
if (x[1] == y[1]) return 0;
else if (x[1] > y[1]) swap(x, y), swap(n, m), flag = 1;
int mx = x[1]; X[1] = x[1], X[n] = x[n];
for (int i = 2; i <= n; i++) mx = max(mx, x[i]), X[i].pre = min(X[i - 1].pre, x[i]);
for (int i = n - 1; i; i--) X[i].suf = min(X[i + 1].suf, x[i]);
int mn = y[1]; Y[1] = y[1], Y[m] = y[m];
for (int i = 2; i <= m; i++) mn = min(mn, y[i]), Y[i].pre = max(Y[i - 1].pre, y[i]);
for (int i = m - 1; i; i--) Y[i].suf = max(Y[i + 1].suf, y[i]);
if (mx >= Y[1].suf || mn <= X[1].suf) return 0;
for (int i = 1, j = 1; i <= n; i++) {
while (j <= m && y[j] > X[i].pre) j++;
if (j == m + 1) break;
if (x[i] >= Y[j].pre) return 0;
}
for (int i = n, j = m; i; i--) {
while (j && y[j] > X[i].suf) j--;
if (!j) break;
if (x[i] >= Y[j].suf) return 0;
}
return 1;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> n >> m >> q;
for (int i = 1; i <= n; i++) cin >> x[i];
for (int i = 1; i <= m; i++) cin >> y[i];
cout << check(x, y);
while (q--) {
if (flag) swap(n, m), flag = 0;
memcpy(tx, x, sizeof(tx)), memcpy(ty, y, sizeof(ty));
int kx, ky, p, v; cin >> kx >> ky;
while (kx--) cin >> p >> v, tx[p] = v;
while (ky--) cin >> p >> v, ty[p] = v;
cout << check(tx, ty);
}
return 0;
}