思路
treap 的妙用。
从 1 到 C 扫描整个矩阵,若当前扫描到了第 i 行,设 $t_j (1\leq j\leq R)$ 为 $(i, j)$ 向上第一个资源点,即 $t_j = \max \\{k | 1\leq k\leq i, (k, j) \in S\\}$ (S 为资源点集合)。
若矩阵最底下一行为 i,最左段一列为 l,最右端一列为 r,则满足如上要求的合法矩阵个数为 $\max_{i\leq k\leq j} t_k$ 个。
用一颗 treap 维护 $t_i$,满足父节点的 $t$ 小于儿子节点,树的中序遍历为 $1$ 到 $n$ 的顺序排列。
重新按上述要求,则满足的合法矩阵个数表示为 $t_{lca(l, r)}$。
所以最底下一行为 i 的矩阵个数为 $\sum_{1\leq l\leq R}\sum_{1\leq r\leq R} t_{lca(l, r)}$。
若先枚举 $lca(l, r)$ 得到 $\sum_{1\leq k\leq R} t_k \times (siz_{ls_{k}} + 1) \times (siz_{rs_k} + 1)$,这个式子可以用平衡树维护。
由于点的位置随机,所以平衡树复杂度正确,为 $O(n\log n)$。
代码
这里使用 FHQ-Treap。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
class FHQ {
protected :
int root = 1, tot;
int val[N], ls[N], rs[N], siz[N];
ll w[N];
int newnode(int x) {
siz[++ tot] = 1, w[tot] = val[tot] = x;
return tot;
} void pushup(int x) {
siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
w[x] = w[ls[x]] + w[rs[x]] + 1ll * val[x] * (siz[ls[x]] + 1) * (siz[rs[x]] + 1);
} int merge(int x, int y) {
if (!x || !y) return x | y;
if (val[x] > val[y]) {rs[x] = merge(rs[x], y); pushup(x); return x;}
else {ls[y] = merge(x, ls[y]); pushup(y); return y;}
} void split(int x, int k, int &l, int &r) {
if (!x) return l = r = 0, void();
if (siz[ls[x]] + 1 <= k) {l = x; split(rs[x], k - siz[ls[x]] - 1, rs[x], r);}
else {r = x; split(ls[x], k, l, ls[x]);}
pushup(x);
}
public :
int size() {return siz[root];}
int build(int l, int r) {
int t = newnode(0);
int mid = l + r >> 1;
if (l == r) return t;
if (l > r) return 0;
ls[t] = build(l, mid - 1), rs[t] = build(mid + 1, r);
pushup(t);
return t;
} void modify(int x, int y) {
int a, b, c;
split(root, x, b, c);
split(b, x - 1, a, b);
root = merge(merge(a, newnode(y)), c);
} ll query() {return w[root];}
} T;
int main() {
int r, c, n;
scanf("%d%d%d", &r, &c, &n);
vector<vector<int>> g(r + 1);
for (int i = 1; i <= n; i ++ ) {
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
}
T.build(1, c);
ll ans = 0;
for (int i = 1; i <= r; i ++ ) {
for (int j : g[i]) T.modify(j, i);
ans += T.query();
}
printf("%lld\n", ans);
return 0;
}