CF2137F题解

· · 题解

题目

思路

以样例5为例，分析一下样例，对于 x=[5,1,2,6,3,4],y=[3,1,6,2,5,4]，z 的第一位只能填 5，第二位的 1 不是前缀最大值，于是第二位可填任意一个不超过 5 的数，类似地，第三位可填任意一个不超过 5 的数，第四位只能填 6，第五、第六位可填任意一个不超过 6 的数，于是第二、第五、第六位可对 f(x,y) 有贡献，即 f(x,y)=3。

对于一个位置 i 和固定的区间左端点 l，如果区间右端点 r=i 时，i 对该区间有贡献，那么对于 r>i 的区间 i 也对当前区间有贡献，即如果区间右端点 r=i 时，i 对该区间有贡献，则 i 对最后答案的贡献为 n-i+1。

接着考虑对于每个 i 有哪些左端点 l 能使 i 对区间 [l,i] 有贡献。如果 [l,i) 中的最大值小于 a_i，那么只有满足 a_i=b_i 时 i 有贡献；否则，满足 [l,i) 中的最大值不小于 b_i 时 i 有贡献。对于第一种情况，可以预处理出每个 i 前第一个大于等于 a_i 的数的位置 pos_i；对于第二种情况，可以用二分和线段树解决。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,n,a[200005],pos[200005],st[200005],top,b[200005],ans,maxn[200005];
ll tr[800005];
void build(int k,int l,int r){
    if(l==r){
        tr[k]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
ll query(ll k,ll l,ll r,ll x,ll y){
    if(x<=l&&r<=y)return tr[k];
    ll mid=(l+r)>>1,ret=0;
    if(x<=mid)ret=max(ret,query(k<<1,l,mid,x,y));
    if(mid<y)ret=max(ret,query(k<<1|1,mid+1,r,x,y));
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        top=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            maxn[i]=max(maxn[i-1],a[i]);
            while(top&&a[st[top]]<a[i])top--;
            pos[i]=st[top];
            while(top&&a[st[top]]<=a[i])top--;
            st[++top]=i;
        }
        build(1,1,n);
        ans=0;
        for(int i=1;i<=n;i++){
            cin>>b[i];
            if(maxn[pos[i]]<b[i]);
            else{
                int l=1,r=pos[i],mid=pos[i],c=pos[i];
                while(l<=r){
                    mid=(l+r)>>1;
                    if(query(1,1,n,mid,pos[i])>=b[i])l=mid+1,c=mid;
                    else r=mid-1;
                }
                ans+=1ll*c*(n-i+1);
            }
            ans+=1ll*(i-pos[i])*(a[i]==b[i])*(n-i+1);
        }
        cout<<ans<<"\n";
    }
    return 0;
}