专栏文章

[CF2163C] Monopati 题解

aaeiouaoeiu
CF2163C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0on4i
此快照首次捕获于
2025/12/01 18:39
3 个月前
此快照最后确认于
2025/12/01 18:39
3 个月前
查看原文
一条 (1,1)→(2,n)(1,1)\to (2,n) 的路径形如先在第一行走一个前缀，然后往下走一格，然后在第二行走一个后缀。
枚举往下走一格的位置 xx，则可以通过预处理前后缀最大最小值得到一个限制 [L,R][L,R]，表示能够走出 (1,1)→(1,x)→(2,x)→(2,n)(1,1)\to(1,x)\to(2,x)\to(2,n) 时 f(l,r)f(l,r) 需要满足 l≤L≤R≤rl\le L\le R\le r，即 [l,r][l,r] 需要包含 [L,R][L,R]。
于是得到 nn 对这样的区间 [Li,Ri][L_i,R_i]，现在需要统计有多少个区间 [l,r][l,r] 至少包含其中一个 [Li,Ri][L_i,R_i]。
枚举 ll，维护当前满足 Li≥lL_i\ge l 的 [Li,Ri][L_i,R_i] 中，RiR_i 的最小值 cc，则 [l,r][l,r] 合法，当且仅当 r≥cr\ge c，于是这个 ll 的贡献即为 2n−c+12n-c+1。
把 RiR_i 挂在 LiL_i 上，从大到小枚举 ll，每次把 ll 上面挂的点算入 cc 中，可以做到 O(n)\mathcal{O}(n)。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...