极差

C++(g++ 7.5.0) 解法, 执行用时: 844ms, 内存消耗: 26292K, 提交时间: 2023-06-25 14:58:15

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int M=1e6;
const long long mod=(1LL<<32);
const int INF=0x3f3f3f3f;
int n,a[4][N+5];
long long tree[(N+5)<<2][8],lazy[(N+5)<<2][4];
int mn[4][N+5],tn[4];
int mx[4][N+5],tx[4];
void work(int x,int val,int len,int idx){
	if(idx==1){
		tree[x][1]+=1LL*len*val;
		tree[x][4]+=tree[x][2]*val;
		tree[x][5]+=tree[x][3]*val;
		tree[x][7]+=tree[x][6]*val;
	}
	else if(idx==2){
		tree[x][2]+=1LL*len*val;
		tree[x][4]+=tree[x][1]*val;
		tree[x][6]+=tree[x][3]*val;
		tree[x][7]+=tree[x][5]*val;
	}
	else if(idx==3){
		tree[x][3]+=1LL*len*val;
		tree[x][5]+=tree[x][1]*val;
		tree[x][6]+=tree[x][2]*val;
		tree[x][7]+=tree[x][4]*val;
	}
	lazy[x][idx]=(lazy[x][idx]+val)%mod;
	for(int i=1;i<=7;i++)tree[x][i]%=mod;
}
void pushdown(int x,int l,int r){
	for(int i=1;i<=3;i++)
		if(lazy[x][i]){
			int mid=(l+r)/2;
			work(x<<1,lazy[x][i],mid-l+1,i);
			work(x<<1|1,lazy[x][i],r-mid,i);
			lazy[x][i]=0;
		}
}
void pushup(int x){
	for(int i=1;i<=7;i++)
		tree[x][i]=(tree[x<<1][i]+tree[x<<1|1][i])%mod;
}
void update(int x,int l,int r,int L,int R,int val,int idx){
	if(L<=l && r<=R){
		work(x,val,r-l+1,idx);
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)/2;
	if(L<=mid)update(x<<1,l,mid,L,R,val,idx);
	if(R>mid)update(x<<1|1,mid+1,r,L,R,val,idx);
	pushup(x);
}
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=3;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	long long ans=0;
	for(int r=1;r<=n;r++){
		for(int i=1;i<=3;i++){
			while(tn[i] && a[i][mn[i][tn[i]]]>=a[i][r]){
				update(1,1,n,mn[i][tn[i]-1]+1,mn[i][tn[i]],a[i][mn[i][tn[i]]],i);
				tn[i]--;
			}
			mn[i][++tn[i]]=r;
			update(1,1,n,mn[i][tn[i]-1]+1,r,-a[i][r],i);
			
			while(tx[i] && a[i][mx[i][tx[i]]]<=a[i][r]){
				update(1,1,n,mx[i][tx[i]-1]+1,mx[i][tx[i]],-a[i][mx[i][tx[i]]],i);
				tx[i]--;
			}
			mx[i][++tx[i]]=r;
			update(1,1,n,mx[i][tx[i]-1]+1,r,a[i][r],i);
		}
		ans=(ans+tree[1][7])%mod;
		ans=(ans+mod)%mod;
	}
	cout<<ans;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 756ms, 内存消耗: 17368K, 提交时间: 2018-07-13 18:21:53

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int P=1e9+7;
const int N=1e5+9;
int z[N<<2][2][3],lazy[N<<2][3],sum[N<<2];
int n,ans,a[3][N];
void pw(int x,int num,int fr,int len){
	lazy[x][fr]=num;
	z[x][0][fr]=num*len;
	int a=fr,b=(fr+1)%3,c=(fr+2)%3;
	z[x][1][a]=num*z[x][0][b];
	z[x][1][c]=num*z[x][0][c];
	sum[x]=num*z[x][1][b];
}
void pd(int x,int l,int r){
	int m=(l+r)>>1;
	for(int i=0;i<3;++i) if(lazy[x][i])
	pw(x<<1,lazy[x][i],i,m-l+1),
	pw(x<<1|1,lazy[x][i],i,r-m),
	lazy[x][i]=0;
}
void up(int x){
	for(int i=0;i<2;++i) for(int j=0;j<3;++j)
	z[x][i][j]=z[x<<1][i][j]+z[x<<1|1][i][j];
	sum[x]=sum[x<<1]+sum[x<<1|1];
}
void mdy(int x,int l,int r,int ql,int qr,int num,int fr){
	if(ql<=l&&r<=qr){
		pw(x,num,fr,r-l+1);
		return ;
	}
	int m=(l+r)>>1;
	pd(x,l,r);
	if(ql<=m) mdy(x<<1,l,m,ql,qr,num,fr);
	if(qr>m)  mdy(x<<1|1,m+1,r,ql,qr,num,fr);
	up(x);
}
void clr(){
	memset(z,0,sizeof(z));
	memset(lazy,0,sizeof(lazy));
	memset(sum,0,sizeof(sum));
}
static int tp[3],sta[3][N];
void sol(int x,int y,int z){
	int f[3]={x,y,z};
	clr();
	for(int i=0;i<3;++i) tp[i]=0;
	for(int i=1;i<=n;++i) {
		for(int j=0;j<3;++j){
			if(!f[j]) while(tp[j]&&a[j][sta[j][tp[j]]]>=a[j][i]) --tp[j];
			else while(tp[j]&&a[j][sta[j][tp[j]]]<=a[j][i]) --tp[j];
			int l=sta[j][tp[j]]+1;
			mdy(1,1,n,l,i,f[j]?a[j][i]:-a[j][i],j);
			sta[j][++tp[j]]=i;
		}
		ans+=sum[1];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<3;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]);
	for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k)
	sol(i,j,k);
	printf("%u\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 348ms, 内存消耗: 19552K, 提交时间: 2018-06-22 22:21:24

#include<bits/stdc++.h>
typedef unsigned int u32;
const int N=1e5+7,K=3;
int n,_l,_r,_t,_x;
struct node{
	u32 v[1<<K],a[K];
	node*lc,*rc;
	int L,R,M;
	void dn(){
		for(int i=0;i<K;++i)if(a[i]){
			lc->add(i,a[i]);
			rc->add(i,a[i]);
			a[i]=0;
		}
	}
	void add(int w,u32 x){
		a[w]+=x;
		for(int i=0,b=1<<w;i<(1<<K);++i)if(i&b)v[i]+=v[i-b]*x;
	}
	void up(){
		for(int i=0;i<(1<<K);++i)v[i]=lc->v[i]+rc->v[i];
	}
	void op(){
		if(_l<=L&&R<=_r)return add(_t,_x);
		dn();
		if(_l<=M)lc->op();
		if(_r>M)rc->op();
		up();
	}
}ns[N*2],*np=ns,*rt;
node*build(int L,int R){
	node*w=np++;
	w->L=L,w->R=R,w->v[0]=R-L+1;
	if(L<R){
		int M=w->M=(L+R)>>1;
		w->lc=build(L,M);
		w->rc=build(M+1,R);
	}
	return w;
}
struct seq{
	int a[N],s[N],sp,sgn;
	void init(int _sgn){
		sgn=_sgn;
		a[0]=sgn>0?1e9+1:-1;
		s[0]=sp=0;
	}
	void cal(int w,int t){
		_l=_r=w,_t=t,_x=a[w]*sgn,rt->op();
		while((_x=(a[w]-a[s[sp]])*sgn)>0){
			_l=s[sp-1]+1,_r=s[sp],rt->op();
			--sp;
		}
		s[++sp]=w;
	}
}mx[K],mn[K];
int main(){
	assert(scanf("%d",&n)==1&&1<=n&&n<=100000);
	rt=build(1,n);
	for(int t=0;t<K;++t){
		mx[t].init(1);
		mn[t].init(-1);
		for(int i=1,x;i<=n;++i){
			assert(scanf("%d",&x)==1&&1<=x&&x<=1000000000);
			mx[t].a[i]=mn[t].a[i]=x;
		}
	}
	u32 ans=0;
	for(int i=1;i<=n;++i){
		for(int t=0;t<K;++t){
			mx[t].cal(i,t);
			mn[t].cal(i,t);
		}
		ans+=rt->v[(1<<K)-1];
	}
	printf("%u\n",ans);
	return 0;
}

详情