MnZn袜子刚学分治114514ms,分治45pts求条
查看原帖
MnZn袜子刚学分治114514ms,分治45pts求条
649611
Zelensky楼主2025/7/3 21:26
#include<bits/stdc++.h>
using namespace std;
int a[(int)2e5],n,M,ans,mx[(int)5e6],mn[(int)5e6],t[(int)5e6];
void solve(int l,int r){
	if(l==r)return ans++,void();
	int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	mx[mid]=mn[mid]=a[mid],mx[mid+1]=mn[mid+1]=a[mid+1];
	for(int i=mid-1;i>=l;i--)mx[i]=max(mx[i+1],a[i]),mn[i]=min(mn[i+1],a[i]);
	for(int i=mid+2;i<=r;i++)mx[i]=max(mx[i-1],a[i]),mn[i]=min(mn[i-1],a[i]);
	int L=mid+1,R=mid;
	for(int i=mid+1;i<=r;i++){
		while(L>l&&mn[L-1]>mn[i])L--,t[mx[L]+L]++;
		while(R>=L&&mx[R]<mx[i])t[mx[R]+R]--,R--;
		ans+=t[mn[i]+i];
	}
	for(int i=l;i<=mid;i++)t[mx[i]+i]=0;
	L=mid+1,R=mid;
	for(int i=mid+1;i<=r;i++){
		while(L>l&&mx[L-1]<mx[i])L--,t[mn[L]-L+M]++;
		while(R>=L&&mn[R]>mn[i])t[mn[R]-R+M]--,R--;
		ans+=t[mx[i]-i+M];
	}
	for(int i=l;i<=mid;i++)t[mn[i]-i+M]=0;
}
int main(){
	cin>>n;M=n;for(int i=1;i<=n;i++)cin>>a[i];
	solve(1,n);cout<<ans;return 0;
}
2025/7/3 21:26
加载中...