题解：CF2163C Monopati

· · 题解

官解怎么在双指针，不会啊呜呜。

首先一个很自然的想法是，因为 down-right path 只有 n 种，那么直接枚举这 n 条路线，不妨设第 i 条路线为 (1,1)\to(1,i)\to(2,i)\to(2,n)，路线上的点的点权的最大值为 y_i，最小值为 x_i，则符合题意的数对集合为 \{(l,r)|1\leqslant l\leqslant x_i,y_i\leqslant r\leqslant 2n\}，显然对于第 i 条路线数对个数为 x_i(2n+1-y_i)。

实现部分，设 pre_{1,i,0/1} 存储第一行每个前缀的最小值/最大值，suf_{2,i,0/1} 存储第二行每个后缀的最小值/最大值，那么可以直接求出 x_i=\min(pre_{1,i,0},suf_{2,i,0}),y_i=\max(pre_{1,i,1},suf_{2,i,1})，是很简单的前/后缀和应用。

但是你很快会发现，一个 (l,r) 数对可能可以走两种以上不同路线，但是计数时只能被计入一次，怎么办呢？难道容斥吗？n\leqslant 2\cdot10^5，肯定不能直接容斥。重新审视我们需要求的柿子：\left|\bigcup\limits_{i=1}^n\{(l,r)|1\leqslant l\leqslant x_i,y_i\leqslant r\leqslant 2n\}\right|，我们注意到每一个集合在二维平面上都是一个矩形的形式！啊？矩形面积并？div2C 出线段树加扫描线？真的假的？

其实不需要。发现实际上矩形的左边界和上边界实际上是固定的，我们只需要记录右下角 (x_i,y_i) 的露尖（代表这个矩形），如果出现了一个矩形 (x^\prime,y^\prime) 被另一个矩形 (x,y) 全包含的情况（即 x^\prime\leqslant x,y^\prime\geqslant y），那么直接忽略掉 (x^\prime,y^\prime) 即可。于是剩下来的矩形（设有 m 个）按照右下尖的横坐标排序，右下尖的纵坐标就是递增的，每个矩形的实际贡献就是这个矩形减去下一个矩形即 \{(l,r)|1\leqslant l\leqslant x_i,y_i\leqslant r< y_{i+1}\}（不妨 y_{m+1}=2n+1），即最终答案为 \sum\limits_{i=1}^mx_i(y_{i+1}-y_i)。

不是我想要的矩形，直接去掉。去掉被包含矩形的实现与去掉被包含区间（去掉子集和去掉超集都考的很多，甚至下一题就又考一遍）类似，可以直接用单调栈维护，先对横坐标排序，栈顶元素小于等于当前元素就一直弹出栈顶，然后当前元素入栈。具体实现可以参考 AC Code。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i = (x); i <= (y); i++)
#define x first
#define y second
typedef long long ll;
typedef std::pair<int, int> pii;
ll read() {ll x; scanf("%lld", &x); return x;}
using std::min, std::max;
const int N = 214514;
int n, a[2][N];
pii pre[N], suf[N], p[N];
int main() {
    int T = read(); while(T--) {
        n = read();
        rep(i, 0, 1) rep(j, 1, n) a[i][j] = read();
        pre[1] = {a[0][1], a[0][1]};
        rep(i, 2, n) {
            pre[i].x = min(a[0][i], pre[i - 1].x);
            pre[i].y = max(a[0][i], pre[i - 1].y);
        }
        suf[n] = {a[1][n], a[1][n]};
        for(int i = n - 1; i; i--) {
            suf[i].x = min(a[1][i], suf[i + 1].x);
            suf[i].y = max(a[1][i], suf[i + 1].y);
        }
        rep(i, 1, n) {
            p[i].x = min(suf[i].x, pre[i].x),
            p[i].y = max(suf[i].y, pre[i].y);
        }
        std::sort(p + 1, p + n + 1);
        ll ans = 0;
        std::stack<pii> st;
        rep(i, 1, n) {
            while(!st.empty() && st.top().y >= p[i].y) st.pop();
            st.push(p[i]);
        }
        int r = 2 * n + 1;
        while(!st.empty()) {
            auto [x, y] = st.top(); st.pop();
            ans += x * /**/1ll * (r - y);
            r = y;
        }
        printf("%lld\n", ans);
    }
}