《双序列拓展》

描述

称某个序列 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。

以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问：

1. A={8,6,9}，B={1,7,4}，取 F={8,8,6,9,⋯},G={1,7,4,4,⋯}；
2. A={8,6,0}，B={1,7,4}，可以证明不存在满足要求的方案；
3. A={8,6,9}，B={8,7,5}，可以证明不存在满足要求的方案；
4. 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​ 两两不同。

特殊性质：对于每组询问（包括初始询问和额外询问），保证 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;
}