题目
题目链接：https://codeforces.com/contest/1548/problem/E
一个 \(n\times m\) 的网格，其中 \((i,j)\) 的权值为 \(a_i+b_j\)。
把所有权值不超过 \(X\) 的格子全部染成白色，大于 \(X\) 的染成黑色，求最后白色连通块的数量。
\(n,m,X,a_i,b_i\leq 2\times 10^5\)。
思路
基本上就是 CF 官方题解抄过来的(
如果存在 \(i,j(i<j)\) 满足 \(a_i=a_j\)，那么我们就当做 \(a_j>a_i\)。\(b\) 同理。
这样的话，对于每一个连通块，就必然有恰好一个格子的权值是最小的。首先每一个连通块必然至少有一个格子的权值最小，然后考虑这个权值最小的格子 \((i,j)\)。假设 \(i‘\in[l1,r1]\) 都满足 \(a_{i‘}+b_j\leq X\)，\(j‘\in[l2,r2]\) 都满足 \(a_i+b_{j‘}\leq X\)，那么一定有 \(a_i=\min_{k\in[l1,r1]}a_k\)，\(b_j=\min_{k\in[l2,r2]}b_k\)。且该连通块一定在 \((l1,l2),(r1,r2)\) 这个矩形内。所以每一个连通块也就可以恰好找到一个最小值。
那么我们只需要找有多少个这样的格子就行了。记 \(pre_i\) 为最大的 \(j(j<i)\) 满足 \(a_j<a_i\)，\(nxt_i\) 为最小的 \(j(j>i)\) 满足 \(a_j<a_i\)；记 \(c_i=\min(\max_{j\in(pre_i,i]}a_j,\max_{j\in[i,nxt_i)}a_j)\)。同理 \(d\) 就是在 \(b\) 上搞这个玩意，那么若一个格子 \((i,j)\) 是一个连通块内最小的格子，必然有：
- \(a_i+b_j\leq X\)
- \(c_i+b_j>X\)
- \(a_i+d_j>X\)
也就是 \((i,j)\) 的权值不超过 \(X\)，且第 \(i\) 行往上往下找到第一个小于 \(a_i\) 的那一行中间必然有一行连不过去；且第 \(j\) 列往左往右找第一个小于 \(b_j\) 的那一列中间必然有一列连不过去。
可以通过 ST 表 + 单调栈来求出 \(c,d\)，那么接下来就是需要统计有多少 \((i,j)\) 满足上述条件。
将所有二元组 \((a_i,c_i),(b_i,d_i)\) 扔进一个数组里，把所有二元组 \((x,y)\) 按照 \(y-x\) 从大到小排序。
维护 \(a,b\) 两个树状数组，然后对于一个二元组，假设它是 \((a_i,c_i)\) 的形式，那么就在 \(b\) 的树状数组内查询 \((X-c_i,X-a_i]\) 的和。这样就统计了同时满足条件 \(1,2\)，且满足 \(c_i-a_i\leq d_j-b_j\) 的二元组数量。
而 \(c_i-a_i\leq d_j-b_j\) 等价于 \(c_i+b_j\leq a_i+d_j\)，而条件 \(2\) 中已经满足 \(c_i+b_j>X\)，所以也就必然有 \(c_i+b_j> X\)。而对于 \(X<c_i+b_j\leq a_i+d_j\) 的部分，则会在形如 \((b_i,d_i)\) 的二元组中计算。
这样所有情况很巧妙的恰好被计算了一次。
再在 \(a\) 的树状数组中下标 \(a_i\) 加 \(1\) 即可。
时间复杂度 \(O(n\log n+m\log m)\)。
代码
#include <bits/stdc++.h>
#define mp(x,y,z) make_pair(x,make_pair(y,z))
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=200010,LG=18,Inf=1e9;
int n,m,k,a[N],b[N],c[N],d[N],lg[N],st[N][LG+1];
ll ans;
pair<int,pair<int,int> > qry[N*2];
stack<int> s;
void buildst(int n,int *a)
{
for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for (int i=1;i<=n;i++) st[i][0]=a[i];
for (int i=n;i>=1;i--)
for (int j=1;i+(1<<j)-1<=n;j++)
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
int query(int l,int r)
{
int k=lg[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
void work(int n,int *a,int *c)
{
for (int i=1;i<=n;i++)
{
c[i]=Inf;
while (s.size() && a[s.top()]>=a[i]) s.pop();
if (s.size()) c[i]=query(s.top()+1,i);
s.push(i);
}
while (s.size()) s.pop();
for (int i=n;i>=1;i--)
{
while (s.size() && a[s.top()]>a[i]) s.pop();
if (s.size()) c[i]=min(c[i],query(i,s.top()-1));
s.push(i);
}
while (s.size()) s.pop();
}
struct BIT
{
int c[N];
void add(int x,int v)
{
for (int i=x;i<N;i+=i&-i)
c[i]+=v;
}
int query(int x)
{
int ans=0;
for (int i=x;i>0;i-=i&-i)
ans+=c[i];
return ans;
}
}bit[2];
bool cmp(pair<int,pair<int,int> > x,pair<int,pair<int,int> > y)
{
return x.se.fi-x.fi>y.se.fi-y.fi;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=m;i++) scanf("%d",&b[i]);
buildst(n,a); work(n,a,c);
buildst(m,b); work(m,b,d);
for (int i=1;i<=n;i++) qry[i]=mp(a[i],c[i],0);
for (int i=1;i<=m;i++) qry[i+n]=mp(b[i],d[i],1);
sort(qry+1,qry+1+n+m,cmp);
for (int i=1;i<=n+m;i++)
{
int x=qry[i].fi,y=qry[i].se.fi,typ=qry[i].se.se;
if (x<=y) ans+=bit[typ^1].query(k-x)-bit[typ^1].query(k-y);
bit[typ].add(x,1);
}
cout<<ans;
return 0;
}