专栏文章

CF2137F题解

PPenguinJ
CF2137F题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minrg25q
此快照首次捕获于
2025/12/02 07:08
3 个月前
此快照最后确认于
2025/12/02 07:08
3 个月前
查看原文
题目

思路

以样例5为例，分析一下样例，对于 x=[5,1,2,6,3,4],y=[3,1,6,2,5,4]x=[5,1,2,6,3,4],y=[3,1,6,2,5,4]，zz 的第一位只能填 55，第二位的 11 不是前缀最大值，于是第二位可填任意一个不超过 55 的数，类似地，第三位可填任意一个不超过 55 的数，第四位只能填 66，第五、第六位可填任意一个不超过 66 的数，于是第二、第五、第六位可对 f(x,y)f(x,y) 有贡献，即 f(x,y)=3f(x,y)=3。
对于一个位置 ii 和固定的区间左端点 ll，如果区间右端点 r=ir=i 时，ii 对该区间有贡献，那么对于 r>ir>i 的区间 ii 也对当前区间有贡献，即如果区间右端点 r=ir=i 时，ii 对该区间有贡献，则 ii 对最后答案的贡献为 n−i+1n-i+1。
接着考虑对于每个 ii 有哪些左端点 ll 能使 ii 对区间 [l,i][l,i] 有贡献。如果 [l,i)[l,i) 中的最大值小于 aia_i，那么只有满足 ai=bia_i=b_i 时 ii 有贡献；否则，满足 [l,i)[l,i) 中的最大值不小于 bib_i 时 ii 有贡献。对于第一种情况，可以预处理出每个 ii 前第一个大于等于 aia_i 的数的位置 posipos_i；对于第二种情况，可以用二分和线段树解决。

代码

CPP
#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;
}

评论

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

正在加载评论...