题目链接
Codeforces 1548E Gregor and the Two Painters
题目大意
有两个序列 \(\{a\}\) 和 \(\{b\}\)，长度分别为 \(n\) 和 \(m\)，由此构造 \(n\times m\) 的网格，\((i,j)\) 处的权值为 \(a_i+b_j\)，称格子 \((i,j)\) 是坏的若格子的权值 \(\leq X\)。求图中坏格子的连通块数量。
\(1\leq n,m,a_i,b_i,X\leq 2\times 10^5\)
思路
思维性相当强的有趣题。
\(2e5\times2e5\) 的网格非常大，同时容易构造出答案为 \(\frac{nm}{4}\) 的数据，不可能用并查集之类的东西去维护，于是东碰西撞研究单调性包含性想不出来*去看 Hint 后能发现这样一个思路，我们尝试给每个连通块选出一个标记点，这样只需要快速统计标记点的个数即可。
通过形状属性来选标记点是困难的，因为连通块的形状几乎是任意的，很难快速确定点是否满足要求，于是通过点自身属性来选，容易想到挑权值最小的。对于最小的点，连通块其它部分都比它大，而不是坏的格子显然也比它大，那么我们在连通块周围框一个矩形出来（外切），可以证明，标记点即矩形内最小的点，这个命题等价于矩形中不会存在别的坏格子连通块，但是注意到对于网格中的相邻两行，他们拥有的坏格子集合必然是包含的关系（单调性），而若存在别的连通块便会违反这个性质，出现这边连不上，而本应是被包含的地方反而连上的情况。
从而标记点 \((i,j)\) 的 \(a_i\) 和 \(b_i\) 都是矩形对应区间里的最小值，所以要判定一个点是否是标记点，只需要分别看在横向和纵向上，第一个权值比其小的格子是否和它在一个连通块里即可，然后再根据行行（以及列列）之间的包含性，可以再将其简化为：到比其小的格子之间的一条上，是否有权值 \(>X\) 的格子。
有了这个性质，便可以着手开始统计了。对于 \(\{a\}\) 序列，用单调栈维护出 \(a_i\) 往左往右遇到的第一个 \(<a_i\) 的位置，记为 \(l_i,r_i\)，然后记 \(na_i=\min(\max_{i\in[l_i,i-1]}\{a_i\},\max_{i\in[i+1,r_i]}\{a_i\})\)，表示若第 \(i\) 行的点要成为非标记点，则这个连通块需要包含 \(a_j=na_i\) 的行，\(na_i\) 可以在单调栈时顺带维护出，类似地处理出 \(nb_i\)。现在可以得到，一个点为标记点，当且仅当：
- \(a_i+b_j\leq X\)
- \(a_i+nb_j>X\)
- \(na_i+b_j>X\)
这是一个简洁的偏序问题！对于后两个限制，只需要求 \(a_i+nb_i,\;na_i+b_i\) 中较小的 \(>X\) ，移一下项，检查 \(na_i-a_i,\;nb_i-b_i\) 较大的那个对应的式子即可。于是我们维护两棵树状数组 \(T_a,T_b\)，将 \((na_i-a_i,a_i)\) 和 \((nb_i-b_i,b_i)\) 二元组一起从大到小处理，若当前是 \((na_i-a_i,a_i)\)，便将答案加上 \(T_b\) 中 \((X-na_i,X-a_i]\) 的权值，然后 \(T_a\) 中 \(a_i\) 的位置加 \(1\)，\((nb_i-b_i,b_i)\) 类似。
时间复杂度 \(O(n\log n)\)
Code
#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 200021
#define PII pair<int, int>
#define PIP pair<int, PII>
#define fr first
#define sc second
#define lowbit(x) (x&-x)
#define ll long long
#define Inf 0x3f3f3f3f
using namespace std;
int n, m, x;
int a[N], b[N];
int l[N], r[N], na[N], nb[N];
stack<PII> s;
vector<PIP> vec;
struct Fenwick{
int t[N];
void update(int pos, int k){
while(pos < N) t[pos] += k, pos += lowbit(pos);
}
int get(int pos){
int ret = 0;
while(pos) ret += t[pos], pos -= lowbit(pos);
return ret;
}
} T[2];
void prework(int n, int *a, int *na){
a[0] = a[n+1] = x+1;
s.push({0, x+1});
rep(i,1,n){
int mx = a[i];
while(!s.empty() && a[s.top().fr] >= a[i]) mx = max(mx, s.top().sc), s.pop();
l[i] = mx, s.push({i, mx});
}
while(!s.empty()) s.pop();
s.push({n+1, x+1});
per(i,n,1){
int mx = a[i];
while(!s.empty() && a[s.top().fr] > a[i]) mx = max(mx, s.top().sc), s.pop();
r[i] = mx, s.push({i, mx});
}
while(!s.empty()) s.pop();
rep(i,1,n) na[i] = min(l[i], r[i]);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>x;
rep(i,1,n) cin>>a[i];
rep(i,1,m) cin>>b[i];
prework(n, a, na), prework(m, b, nb);
ll ans = 0;
rep(i,1,n) vec.push_back({na[i]-a[i], {a[i], 0}});
rep(i,1,m) vec.push_back({nb[i]-b[i], {b[i], 1}});
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for(PIP p : vec){
ans += T[p.sc.sc^1].get(max(x-p.sc.fr, 0)) - T[p.sc.sc^1].get(max(x - (p.fr+p.sc.fr), 0));
T[p.sc.sc].update(p.sc.fr, 1);
}
cout<< ans <<endl;
return 0;
}