2017-07-04

【51nod算法马拉松】连续区间

本文为博主原创，未经许可不得转载

AC通道

直接粘题解：（懒得写了

nlogn的复杂度跑得飞快

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1000100
using namespace std;
int n,a[MAXN],maxx[MAXN],minn[MAXN],cnt[MAXN<<1];
long long ans;
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getc();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getc();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getc();}
	return x*f;
}
void solve(int l,int r){
	if(l==r){++ans; return;}
	int mid=(l+r)>>1;  
	solve(l,mid);  solve(mid+1,r);
	maxx[mid]=minn[mid]=a[mid];
	maxx[mid+1]=minn[mid+1]=a[mid+1];
	for(int i=mid-1;i>=l;--i){
		maxx[i]=max(maxx[i+1],a[i]);
		minn[i]=min(minn[i+1],a[i]);
	}
	for(int i=mid+2;i<=r;++i){
		maxx[i]=max(maxx[i-1],a[i]);
		minn[i]=min(minn[i-1],a[i]);
	}
	for(int i=l;i<=mid;++i){
		int j=maxx[i]-minn[i]+i;
		if(j<=mid||j>r||maxx[j]>maxx[i]||minn[j]<minn[i]) continue;
		++ans;
	}
	for(int i=mid+1;i<=r;++i){
		int j=minn[i]-maxx[i]+i;
		if(j>mid||j<l||maxx[j]>maxx[i]||minn[j]<minn[i]) continue;
		++ans;
	}
	int L=mid+1,R=mid+1;
	for(int i=mid;i>=l;--i){
		while(maxx[R]<maxx[i]&&R<=r)  ++cnt[minn[R]+R],++R;
		while(minn[L]>minn[i]&&L<=r)  --cnt[minn[L]+L],++L;
		if(R>L) ans+=cnt[maxx[i]+i];
	}
	while(R<=r) ++cnt[minn[R]+R],++R;
	while(L<=r) --cnt[minn[L]+L],++L;
	L=R=mid;
	for(int i=mid+1;i<=r;++i){
		while(maxx[L]<maxx[i]&&L>=l) ++cnt[minn[L]-L+n],--L;
		while(minn[R]>minn[i]&&R>=l) --cnt[minn[R]-R+n],--R;
		if(R>L) ans+=cnt[maxx[i]-i+n];
	}
	while(L>=l) ++cnt[minn[L]-L+n],--L;
	while(R>=l) --cnt[minn[R]-R+n],--R;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i) a[i]=read(); 
	solve(1,n);
	printf("%lld\n",ans);
	return 0;
}

本文标题:【51nod算法马拉松】连续区间

文章作者:chty

发布时间:2017年07月04日 - 21时02分

最后更新:2018年07月25日 - 21时32分

许可协议:本文为博主原创，未经许可不得转载。