2017-03-30

【bzoj3745】Norma

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

AC通道

这题梓轩学长讲过线段树做法，但是写起来过于糟心，所以考场上果断暴力

然后题解上给出了单调队列的做法，依旧糟心

然后去膜拜神犇的题解，发现分治可做，虽然写起来依旧糟心。。。。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FILE "xnum"
#define MAXN 500010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const ll mod=(ll)1e9;
ll n,ans,a[MAXN],mx[MAXN],mn[MAXN],f[MAXN],g[MAXN],c[MAXN],d[MAXN],p[MAXN],q[MAXN];
inline ll read(){
	ll x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
ll get(ll x,ll y){return ((x+y)*(y-x+1)>>1)%mod;}
void solve(ll l,ll r){
	if(l==r)  {ans=(ans+a[l]*a[l]%mod)%mod;  return;}
	ll mid=(l+r)>>1;
	solve(l,mid);  solve(mid+1,r);
	mx[mid]=mn[mid]=a[mid];
	for(ll i=mid-1;i>=l;--i){
		mx[i]=max(mx[i+1],a[i]);
		mn[i]=min(mn[i+1],a[i]);
	}
	ll maxx=-mod,minn=mod;
	f[mid]=g[mid]=c[mid]=d[mid]=p[mid]=q[mid]=0;
	for(ll i=mid+1;i<=r;++i){
		cmax(maxx,a[i]);  cmin(minn,a[i]);
		f[i]=(f[i-1]+minn*maxx*(i-mid)%mod)%mod;
		g[i]=(g[i-1]+minn*maxx%mod)%mod;
		c[i]=(c[i-1]+minn*(i-mid)%mod)%mod;
		d[i]=(d[i-1]+maxx*(i-mid)%mod)%mod;
		p[i]=(p[i-1]+minn)%mod;
		q[i]=(q[i-1]+maxx)%mod;
	}
	ll j=mid,k=mid;
	for(ll i=mid;i>=l;--i){
		while(j<r&&a[j+1]>mn[i])  ++j;
		while(k<r&&a[k+1]<mx[i])  ++k;
		ans+=mx[i]*mn[i]%mod*get(mid+2-i,min(j,k)-i+1)%mod;ans%=mod;
		ans+=(g[r]-g[max(j,k)])*(mid-i+1)%mod+f[r]-f[max(j,k)];ans%=mod;
		if(j<k) ans+=((p[k]-p[j])*(mid-i+1)%mod+c[k]-c[j])*mx[i]%mod;
		else ans+=((q[j]-q[k])*(mid-i+1)%mod+d[j]-d[k])*mn[i]%mod;
		ans%=mod;
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  for(ll i=1;i<=n;++i)  a[i]=read();
	solve(1,n);  
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}

本文标题:【bzoj3745】Norma

文章作者:chty

发布时间:2017年03月30日 - 20时53分

最后更新:2018年03月02日 - 17时21分

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