CF1849E Max to the Right of Min 题解

KingPowers · 2023-08-19 18:41:09 · 题解

题目链接

这里是线段树题解，其实是个套路题。

类似扫描线的思想，我们可以枚举右端点 r，那么我们的任务就是在 r 向右移动时维护出每个 l 对答案的贡献。

我们记 mx_i 表示 i 左边第一个比 p_i 大的数的位置，mn_i 表示 i 左边第一个比 p_i 小的数的位置，这两个东西显然都可以用单调栈线性求出。

如果 mx_i<i-1，那么当 l\in[mx_i+1,i-1] 时，区间的最大值的位置都在 r，一定在最小值的右边，因此 [mx_i+1,i-1] 的贡献要全部赋成 1。

如果 mn_i<i-1，那么当 l\in[mn_i+1,i-1] 时，区间的最小值的位置都在 r，一定在最大值的右边，因此 [mn_i+1,i-1] 的贡献要全部赋成 0。

事实上，因为 p 是个排列，不难注意到 mx_i 和 mn_i 中一定有且仅有一个小于 i-1。

当 l 在剩下的那些未被考虑到的位置时，r 位置一定既不是最大值也不是最小值，对答案不会有影响，继承之前的结果即可。

时间复杂度：O(n\log n)。

int n,p[N],mx[N],mn[N];
int top,st[N];
namespace DS{
    #define ls(now) now<<1
    #define rs(now) now<<1|1
    int sum[N<<2],tag[N<<2];
    void pushup(int now){
        sum[now]=sum[ls(now)]+sum[rs(now)];
    }
    void cov(int l,int r,int now,int c){
        sum[now]=(r-l+1)*c;tag[now]=c;
    }
    void pushdown(int l,int r,int now){
        if(tag[now]==-1) return;
        int mid=(l+r)>>1;
        cov(l,mid,ls(now),tag[now]);
        cov(mid+1,r,rs(now),tag[now]);
        tag[now]=-1;
    }
    void modify(int x,int y,int c,int l,int r,int now){
        if(x<=l&&r<=y) return cov(l,r,now,c);
        pushdown(l,r,now);
        int mid=(l+r)>>1;
        if(x<=mid) modify(x,y,c,l,mid,ls(now));
        if(y>mid) modify(x,y,c,mid+1,r,rs(now));
        pushup(now);
    }
}
void Main(){
    cin>>n;
    For(i,1,n) cin>>p[i];
    st[top=1]=n;
    Rof(i,n-1,1){
        while(top&&p[st[top]]<p[i]) mx[st[top--]]=i;
        st[++top]=i;
    }
    st[top=1]=n;
    Rof(i,n-1,1){
        while(top&&p[st[top]]>p[i]) mn[st[top--]]=i;
        st[++top]=i;
    }
    ll ans=0;
    For(i,2,n){
        if(mx[i]!=i-1) DS::modify(mx[i]+1,i-1,1,1,n,1);
        if(mn[i]!=i-1) DS::modify(mn[i]+1,i-1,0,1,n,1);
        ans+=DS::sum[1];
    }
    cout<<ans<<'\n';
}