#C240812C.「NOIP2023」双序列拓展

网址（Website）

洛谷，SPOJ

题目（Problem）

题目描述

称某个序列 $B = {b_1,b_2,\cdots,b_n}$ 是另一个序列 $A = {a_1,a_2,\cdots,a_m}$ 的拓展当且仅当存在正整数序列 $L = {l_1,l_2,\cdots,l_m}$，将 $a_i$ 替换为 $l_i$ 个 $a_i$ 后得到序列 $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$ 的一个长度为 $l_0 = 10^{100}$ 的拓展 $F = {f_i}$ 以及 $Y$ 的一个长度为 $l_0$ 的拓展 $G = {g_i}$，使得任意 $1 \le i , j \le l_0$ 都有 $(f_i - g_i)(f_j - g_j) > 0$。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。

为了避免你扔硬币蒙混过关，小 R 还给了 $q$ 次额外询问，每次额外询问中小 R 会修改 $X$ 和 $Y$ 中若干元素的值。你需要对每次得到的新的 $X$ 和 $Y$ 都进行上述的判断。

询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。

输入格式

输入的第一行包含四个整数 $c, n, m, q$，分别表示测试点编号、序列 $X$ 的长度、序列 $Y$ 的长度和额外询问的个数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

输入的第二行包含 $n$ 个整数 $x_1,x_2,\cdots, x_n$，描述序列 $X$。

输入的第三行包含 $m$ 个整数 $y_1,y_2,\cdots, y_m$，描述序列 $Y$。

接下来依次描述 $q$ 组额外询问。对于每组额外询问：

• 输入的第一行包含两个整数 $k_x$ 和 $k_y$，分别表示对序列 $X$ 和 $Y$ 产生的修改个数。
• 接下来 $k_x$ 行每行包含两个整数 $p_x, v_x$，表示将 $x_{p_x}$ 修改为 $v_x$。
• 接下来 $k_y$ 行每行包含两个整数 $p_y, v_y$，表示将 $y_{p_y}$ 修改为 $v_y$。

输出格式

输出一行，其中包含一个长度为 $(q+1)$ 的 01 序列，序列的第一个元素表示初始询问的答案，之后 $q$ 个元素依次表示每组额外询问的答案。对于每个询问，如果存在满足题目条件的序列 $F$ 和 $G$，输出 1，否则输出 0。

样例 #1

样例输入 #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$ 太长，用省略号表示重复最后一个元素直到序列长度为 $l_0$。如 ${1,2,3,3,\cdots}$ 表示序列从第三个元素之后都是 $3$。

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

1. $A = {8,6,9}$，$B = {1,7,4}$，取 $F = {8,8,6,9,\cdots}, G = {1,7,4,4,\cdots}$；
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,\cdots}, G = {7,7,4,\cdots}$。

【样例解释 #2】

该组样例满足测试点 $4$ 的条件。

【样例解释 #3】

该组样例满足测试点 $7$ 的条件。

【样例解释 #4】

该组样例满足测试点 $9$ 的条件。

【样例解释 #5】

该组样例满足测试点 $18$ 的条件。

【数据范围】

对于所有测试数据，保证：

• $1 \le n, m \le 5 \times 10 ^ 5$；
• $0 \le q \le 60$；
• $0 \le x_i, y_i < 10 ^ 9$；
• $0 \le k_x, k_y \le 5 \times 10 ^ 5$，且所有额外询问的 $(k_x+k_y)$ 的和不超过 $5 \times 10 ^ 5$；
• $1 \le p_x \le n$，$1 \le p_y \le m$，$0 \le v_x, v_y < 10 ^ 9$；
• 对于每组额外询问，$p_x$ 两两不同，$p_y$ 两两不同。

测试点编号	$n, m \le$	特殊性质
$1$	$1$	否
$2$	$2$	否
$3, 4$	$6$	否
$5$	$200$	否
$6, 7$	$2000$	否
$8, 9$	$4 \times 10 ^ 4$	是
$10, 11$	$1.5 \times 10 ^ 5$	是
$12 \sim 14$	$5 \times 10 ^ 5$	是
$15, 16$	$4 \times 10 ^ 4$	否
$17, 18$	$1.5 \times 10 ^ 5$	否
$19, 20$	$5 \times 10 ^ 5$	否

特殊性质：对于每组询问（包括初始询问和额外询问），保证 $x_1 < y_1$，且 $x_n$ 是序列 $X$ 唯一的一个最小值，$y_m$ 是序列 $Y$ 唯一的一个最大值。

题解（Solution）

讲题视频： #C240812C.「NOIP2023」双序列拓展 | WolfDeer

大致讲一下这道题：

1. 将这道题转换为二维 $\text{dp}$ ，把两个序列当成 $x$ 轴和 $y$ 轴，并且令 $f_1>g_1$ （如果满足条件，则 一定满足 $f_n>g_m$ ），画成矩阵，对于位置 $(x,y)$ ，这个位置能走当且仅当 $f_x>g_y$ ，很容易就转换成了求能否从位置 $(1,1)$ 走到 $(n,m)$ ，可以直接暴力扫，可以拿 $\text{35pts}$ ；
2. 根据题目提示，我们发现如果最终有解， $f$ 的最大值所在的纵行和 $g$ 最小值所在的横行一定都可以走，问题就转化成了判断能否从 $(1,1)$ 走到这个横行和纵行交叉的十字，再从这个十字上走到 $(n,m)$ ，很明显只需要判断其中一种，剩下的可以直接反转区间来处理。
3. 考虑出现多个最值的情况，因为这些最值的行或者列都是可以走的位置，因此只需要考虑能否从 $(1,1)$ 走到最近的十字即可，$(n,m)$ 同理，令 $an,bm$ 分别表示数组 $f $ 的最大值和 $g$ 的最小值所在的位置。
4. 容易判断出题目是要求我们有 $O(q(n+m))$ 的做法，考虑模拟。观察性质，发现对于 $f_i<f_j$ ，$f_j$ 在纵行上的可以走的点的数量一定大于等于 $f_i$ 能走的点。根据这个性质写一个模拟即可（实现见代码）。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++) 
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 501234;
bool ST;
int tid,T;

P ca[N],cb[N];
int a[N],b[N];
int n,m,q;

#define fail {if(flag) Swap(),flag=0;cout<<'0';return;}
#define win {if(flag) Swap(),flag=0;cout<<'1';return;}

void Swap(){swap(n,m), swap(a,b);}

bool can_walk(int n,int m){
	int mx = 0;
	for(int i=1,j=1;i<=n;i++){
		if(b[j] < a[i]){
			mx = a[mx]>a[i] ? mx : i; 
		}else{
			while(j<=m && b[j]<a[mx] && b[j]>=a[i]) j++;
			if(j>=m) return true;
			if(b[j]>=a[mx]) return false;
		}
	}return true;
}

bool flag = false;
void calc(){
	if(a[1] == b[1]) fail;
	if(a[1] < b[1]) Swap(),flag=1;//保证 a>b
	if(a[n] < b[m]) fail;
	if(*max_element(b+1,b+m+1) >= *max_element(a+1,a+n+1)) fail;
	if(*min_element(a+1,a+n+1) <= *min_element(b+1,b+m+1)) fail;
	
	int al=0,ar=0,mx=0;For(i,1,n){
		if(a[i] > mx) mx=a[i], al = ar = i;
		else if(a[i]==mx) ar=max(ar,i);
	}ar = n-ar+1;
	int bl=0,br=0,mn=inf;For(j,1,m){
		if(b[j] < mn) mn=b[j], bl = br = j;
		else if(b[j]==mn) br=min(br,j);
	}br = m-br+1;
	
	bool fatal = false;
	if(!fatal && !can_walk(al,bl)) fatal=true; reverse(a+1,a+n+1), reverse(b+1,b+m+1);
	if(!fatal && !can_walk(ar,br)) fatal=true; reverse(a+1,a+n+1), reverse(b+1,b+m+1);
	if(fatal) fail else win
}

void Solve(){
	n=rd(),m=rd(),q=rd();For(i,1,n) a[i]=rd();For(j,1,m) b[j]=rd();
	calc();
	For(_,1,q){
		int kx=rd(),ky=rd();
		For(i,1,kx){int x=rd(), y=rd();ca[i] = {x, a[x]},a[x] = y;}
		For(i,1,ky){int x=rd(), y=rd();cb[i] = {x, b[x]},b[x] = y;}
		calc();
		For(i,1,kx) a[ca[i].x] = ca[i].y;
		For(i,1,ky) b[cb[i].x] = cb[i].y; 
	}cout<<'\n';
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	tid=rd(),T=1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}