很好的题!
题意:给出每行权值 \(a_i\),每列权值 \(b_j\),定义点 \((i,j)\) 权值为 \(a_i+b_j\),问权值 \(\le x\) 的点组成的连通块个数。
做法:
这个题需要用到一个数连通块的技巧,我们对于每个连通块钦定一个代表元,那么我们就只用数有多少个代表元就可以了。这个题中,我们令连通块中权值最小且尽量靠左,如果相同靠左那么就靠上,这样的点为代表元。
那么考虑一个点 \((i,j)\) 如何才能成为代表元,首先要求他肯定权值要 \(\le x\),其次我们考虑 \(la_i,ra_i\),分别代表 \(a\) 序列 \(i\) 前面第一个小于等于 \(a_i\) 的位置,\(ra_i\) 是后面第一个小于的位置,类似定义 \(lb_i,rb_i\),那么为了让 \((i,j)\) 走不到 \((la_i,j),(ra_i,j),(i,lb_j),(i,rb_j)\)。可能你会疑惑为什么只需要这四个点,手完一下发现 \(x\in[la_i+1,ra_i-1],y\in[lb_i+1,rb_i-1]\) 这样的点一定不会比 \((i,j)\) 优,而这四个点是比 \((i,j)\) 优且最容易得到的。
以 \((la_i,j)\) 举例,我们就得要求 \(mxla = \max\limits_{t=la_i}^ia_t+b_j>x\),否则就越过去了,同理写出来四个限制,当然对于 \(a,b\) 的两个限制完全可以合在一起,这样就只有两个限制,即假设 \(va_i = \min(\max\limits_{t=la_i}^ia_t,\max\limits_{t=i}^{ra_i}a_t)\),\(vb_j\) 类似定义,那么就要求:
把 \(j\) 相关的全部扔到右边去,然后就是一个二位偏序,复杂度 \(O(n\log n)\)。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 5, inf = 2e9;
int n, m, x, a[maxn], b[maxn], nw;
int st[maxn][21], lg[maxn];
void init(int v[], int n) {for (int i = 1; i <= n; i++)st[i][0] = v[i];for (int j = 1; (1 << j) <= n; j++)for (int i = 1; i + (1 << j) - 1 <= n; i++)st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);lg[0] = -1;for (int i = 1; i <= n; i++)lg[i] = lg[i >> 1] + 1;
}
int query(int l, int r) {if(l == 0 || r == nw + 1)return inf;int k = lg[r - l + 1];return max(st[l][k], st[r - (1 << k) + 1][k]);
}
struct node {int x, y, id;friend bool operator<(node x, node y) {return (x.x != y.x ? x.x > y.x : x.id > y.id);}
} t[maxn];
int stk[maxn], l[maxn], r[maxn], top, tot;
void solve1() {top = 0;nw = n;stk[0] = 0;for (int i = 1; i <= n; i++) {while(top && a[stk[top]] > a[i])top--;l[i] = stk[top];stk[++top] = i;}top = 0;stk[0] = n + 1;for (int i = n; i >= 1; i--) {while(top && a[stk[top]] >= a[i])top--;r[i] = stk[top];stk[++top] = i;}for (int i = 1; i <= n; i++) {int val = min(query(l[i], i), query(i, r[i]));// cout << i << " " << val << " " << r[i] << endl;t[++tot] = {val, a[i], 0};}
}
void solve2() {stk[0] = 0;nw = m;top = 0;for (int i = 1; i <= m; i++) {while(top && b[stk[top]] > b[i])top--;l[i] = stk[top];stk[++top] = i;}top = 0;stk[0] = m + 1;for (int i = m; i >= 1; i--) {while(top && b[stk[top]] >= b[i])top--;r[i] = stk[top];stk[++top] = i;}for (int i = 1; i <= m; i++) {int val = min(query(l[i], i), query(i, r[i]));// cout << i << " " << val << " " << l[i] << " " << r[i] << " " << query(i, r[i]) << endl;t[++tot] = {x - b[i], x - val, 1};}
}
#define lowbit(x) (x & (-x))
struct Tree_array {int tr[maxn], n;void add(int x, int val) {while(x <= n)tr[x] += val, x += lowbit(x);}int query(int x) {int ans = 0;while(x > 0)ans += tr[x], x -= lowbit(x);return ans;}int queryseg(int l, int r) {return query(r) - query(l - 1);}
} tree;
int ans = 0;
void solve() {tree.n = x;sort(t + 1, t + tot + 1);for (int i = 1; i <= tot; i++) {// cout << t[i].x << " " << t[i].y << " " << t[i].id << endl;if(t[i].id == 1)ans += tree.queryseg(t[i].y + 1, t[i].x);elsetree.add(t[i].y, 1);}
}
signed main() {cin >> n >> m >> x;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= m; i++)cin >> b[i];init(a, n);solve1();init(b, m);solve2();solve();cout << ans << endl;return 0;
}