题目大意

给定一个 $n\times m$ 的图和长度为 $n,m$ 的序列 $a,b$，将 $\forall i\in[1,n],j\in[1,m]$ 满足 $a_i+b_j\le x$ 的点设为黑色，求黑色连通块数量。

数据范围满足，$n,m,a_i,b_i\le 2\times 10^5$。

思路

将所有的 $(i,j)$ 按照 $\{a_i+b_j,i,j\}$ 三个元素依次关键字进行排序，记排序后的位置为 $id_{i,j}$。

如果满足 $\nexists (i',j')$ 使得 $(i',j')<(i,j)$ 且 $(i,j),(i',j')$ 在同一个连通块内，那么记 $(i,j)$ 为关键点。

容易发现一个连通块中有且仅有 $1$ 个关键点，所以答案就是关键点的数量。证明很简单，如果 $(i,j),(i',j')$ 同时在一个连通块中必然有 $(i',j')<(i,j),(i,j)<(i',j')$，与定义相矛盾。

定义 $La_i$ 表示 $\max\{j\mid a_i\ge a_j\wedge i>j\}$，$Ra_i$ 表示 $\min\{j\mid a_i>a_j\wedge i<j\}$，$Lb_i,Rb_i$ 同理。

先考虑一个性质：如果从 $(i,j)$ 可以走到 $La_i$ 这一行那么一定可以走到 $(La_i,j)$。

如果可以到达，那么行进的方法一定是先在第 $i$ 行移动，找到可以到达的 $b_{k}$ 最小的点 $(i,k)$。接着移动到 $(La_i,k)$ 再移动到 $(La_i,j)$。

这样的行动一定是最优的，证明如下：

• 如果在向 $(La_i,k)$ 纵向移动的过程中还需要横向移动才能到达 $(r,w)$，那么肯定满足 $a_r\ge a_i\wedge b_w\le b_{k}$。那么如果可以通过就说明 $a_r+b_w\le x$，所以有 $a_i+b_w\le x$，那么 $(i,w)$ 显然是可以到达且 $b$ 值更小的，与假设相矛盾。
• 如果 $(La_i,k)$ 无有到达 $(La_i,j)$，那么因为从 $(i,k)$ 可以到达 $(i,j)$，所以必然有 $a_{La_i}>a_i$，这与定义相矛盾。

容易发现如果 $(i,j)$ 是关键点，那么一定满足 $j=k$，因为如果 $(i,j)$ 不是在第 $i$ 行可以到达的 $b$ 值最小的，那么一定满足 $a_i+b_j>a_i+b_{k}$，所以 $(i,k)$ 显然更优秀与假设相矛盾。

如果 $(i,j)$ 可以到达 $(La_i,j)$，那么 $(i,j)$ 显然不是关键点。因为在共用相同的 $b_j$ 的情况下，必然满足 $(i,j)$ 大于 $(La_i,j)$，所以 $(i,j)$ 定然不是关键点。

所以如果 $(i,j)$ 是关键点就需要满足 $\max\limits_{k=La_i}^{i} a_k+b_j>x$。

同样的，对于其他的 $3$ 个方向也需要满足类似要求就可以了。

综上所述，如果 $(i,j)$ 满足以下条件，那么 $(i,j)$ 就是关键点：

• $a_i+b_j\le x$
• $\min(\max\limits_{k=La_i}^i a_k,\max\limits_{k=i}^{Ra_i}a_k)+b_j>x$
• $\min(\max\limits_{k=Lb_j}^{j}b_k,\max\limits_{k=j}^{Rb_j} b_k)+a_i>x$

不妨设 $c_i=\min(\max\limits_{k=La_i}^i a_k,\max\limits_{k=i}^{Ra_i}a_k),d_i=\min(\max\limits_{k=Lb_j}^{j}b_k,\max\limits_{k=j}^{Rb_j} b_k)$，那么可以通过移项可以得到：

$\left\{\begin{matrix} x-c_i<b_j\le x-a_i \\ d_j>x-a_i \end{matrix}\right.$

提供一种不需要使用线段树的做法：维护一个树状数组做二维偏序。

通过排序可以使第 $2$ 项满足，考虑怎么满足第一项。如果遇到 $b_j$ 那么在这个位置增加 $1$，否则答案增加 $(x-c_i,x-a_i]$ 中数的和。

AC Code

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m,a[N],b[N],lg[N],X,c[N],d[N],sck[N];
struct node{int x,y,op;};
vector<node>g;
stack<int>s;
struct st_max{
	int f[N][21],n;
	void init(int nn,int a[]){
		n=nn;
		for(int i=1;i<=n;i++) f[i][0]=a[i];
		for (int j=1;j<=lg[n];j++){
            for (int i=1;i<=n-(1<<j)+1;i++){
                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            }
        }
	}
	int ask(int x,int y){
		if(x>y) return inf;
		int l=lg[y-x+1];
		return max(f[x][l],f[y-(1<<l)+1][l]);
	}
}s1,s2;
struct BIT{
	int s[N];
	int lowbit(int x){return x&-x;}
	void updata(int x,int v=1){
		for(int i=x;i<N;i+=lowbit(i)) s[i]+=v;
	}
	int sum(int x){
		int ans=0;
		for(int i=x;i>=1;i-=lowbit(i)) ans+=s[i];
		return ans;
	}
}tree;
bool cmp(node x,node y){
	int s1=x.y,s2=y.y;
    if(!x.op) s1=X-x.x+1;
    if(!y.op) s2=X-y.x+1;
    return (s1>s2)||((s1==s2)&&(x.op>y.op));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m>>X;
	lg[1]=0;
	for(int i=2;i<N;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	s1.init(n,a),s2.init(m,b);
    memset(c,0x3f,sizeof(c));
    memset(d,0x3f,sizeof(d));
	for (int i=1;i<=n;i++){
		while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
		if (!s.empty()) c[i]=min(c[i],s1.ask(s.top()+1,i));
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for (int i=n;i>=1;i--){
		while(!s.empty()&&a[s.top()]>a[i]) s.pop();
		if(!s.empty()) c[i]=min(c[i],s1.ask(i,s.top()-1));
        s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=1;i<=m;i++){
		while(!s.empty()&&b[s.top()]>=b[i]) s.pop();
		if (!s.empty()) d[i]=min(d[i],s2.ask(s.top()+1,i));
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=m;i>=1;i--){
		while(!s.empty()&&b[s.top()]>b[i]) s.pop();
		if (!s.empty()) d[i]=min(d[i],s2.ask(i,s.top()-1));
		s.push(i);
	}
	for(int i=1;i<=n;i++) g.push_back({a[i],c[i],0});
	for(int i=1;i<=m;i++) g.push_back({b[i],d[i],1});
	sort(g.begin(),g.end(),cmp);
	long long ans=0;
	for(node i:g){
		if(!i.op) ans+=tree.sum(X-i.x)-tree.sum(X-i.y);
		else tree.updata(i.x);
	}
	cout<<ans<<'\n';
	return 0;
}