[CF2163C] Monopati 题解

· · 题解

一条 (1,1)\to (2,n) 的路径形如先在第一行走一个前缀，然后往下走一格，然后在第二行走一个后缀。

枚举往下走一格的位置 x，则可以通过预处理前后缀最大最小值得到一个限制 [L,R]，表示能够走出 (1,1)\to(1,x)\to(2,x)\to(2,n) 时 f(l,r) 需要满足 l\le L\le R\le r，即 [l,r] 需要包含 [L,R]。

于是得到 n 对这样的区间 [L_i,R_i]，现在需要统计有多少个区间 [l,r] 至少包含其中一个 [L_i,R_i]。

枚举 l，维护当前满足 L_i\ge l 的 [L_i,R_i] 中，R_i 的最小值 c，则 [l,r] 合法，当且仅当 r\ge c，于是这个 l 的贡献即为 2n-c+1。

把 R_i 挂在 L_i 上，从大到小枚举 l，每次把 l 上面挂的点算入 c 中，可以做到 \mathcal{O}(n)。

:::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=1000007,ee=1e18,p=998244353;
ll n,a[2][maxn],mx[2][maxn],mn[2][maxn],val[maxn],ans;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n,ans=0;
        for(ll i=1;i<=n;i++) cin>>a[0][i];
        for(ll i=1;i<=n;i++) cin>>a[1][i];
        mx[0][0]=-ee,mn[0][0]=ee;
        for(ll i=1;i<=n;i++){
            mx[0][i]=max(mx[0][i-1],a[0][i]);
            mn[0][i]=min(mn[0][i-1],a[0][i]);
        }
        mx[1][n+1]=-ee,mn[1][n+1]=ee;
        for(ll i=n;i>=1;i--){
            mx[1][i]=max(mx[1][i+1],a[1][i]);
            mn[1][i]=min(mn[1][i+1],a[1][i]);
        }
        for(ll i=1;i<=2*n;i++) val[i]=2*n+1;
        for(ll i=1,L,R;i<=n;i++){
            L=min(mn[0][i],mn[1][i]);
            R=max(mx[0][i],mx[1][i]);
            val[L]=min(val[L],R);
        }
        for(ll i=2*n,cur=2*n+1;i>=1;i--){
            cur=min(cur,val[i]);
            ans+=2*n-cur+1; 
        }
        cout<<ans<<"\n";
    }
    return 0;
}

:::