bzoj3745: [Coci2015]Norma 分治，单调队列

链接

bzoj

思路

首先(sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}sumlimits_{k=i}^{j}max(a_k))可以用单调队列求解。参见?
求解此题目，我们分治。计算([l,mid])对([mid+1,r])的贡献。
我们从后向前枚举(mid)到(l)，定义为(x)。（(A)为([x,mid])中的最小值，(B)为([x,mid])中的最大值）
得到(p)(([mid+1,r])中大于等于(A)的位置)和(q)(([mid+1,r])中小于等于(B)的位置)
然后根据p，q的位置四种情况讨论，处理前缀和O1得到贡献。
显然p，q类似于单调队列是(O(n))求得
代码有种简单但是恶心的感觉
复杂度(O(nlogn))

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7,inf=0x3f3f3f3f,mod=1e9;
int read() {
	int x=0,f=1;char s=getchar();
	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
	return x*f;
}
int n,a[N],ans;
int ma[N],mi[N],sum_mi[N],sum_ma[N],sum_mimai[N],sum_mima[N],sum_mii[N],sum_mai[N];
int jan(int a,int b) {
	int ans=(a-b);
	if(ans<0) ans+=mod;
	return ans;
}
void add(int &x,int y) {
	x+=y;
	if(x>=mod) x-=mod;
}
void cdq(int l,int r) {
	if(l>r) return;
	if(l==r) {ans=(1LL*a[l]*a[l]%mod+ans)%mod;return;}
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);

	sum_mi[mid]=sum_ma[mid]=sum_mima[mid]=sum_mimai[mid]=sum_mii[mid]=sum_mai[mid]=0;
	mi[mid]=inf,ma[mid]=0;
	for(int i=mid+1;i<=r;++i) {
		mi[i]=min(mi[i-1],a[i]);
		ma[i]=max(ma[i-1],a[i]);
		sum_mi[i]=(sum_mi[i-1]+mi[i])%mod;
		sum_ma[i]=(sum_ma[i-1]+ma[i])%mod;
		sum_mii[i]=(sum_mii[i-1]+1LL*mi[i]*i%mod)%mod;
		sum_mai[i]=(sum_mai[i-1]+1LL*ma[i]*i%mod)%mod;
		sum_mima[i]=(sum_mima[i-1]+1LL*mi[i]*ma[i]%mod)%mod;
		sum_mimai[i]=(sum_mimai[i-1]+1LL*mi[i]*ma[i]%mod*i%mod)%mod;
	}
	long long L,R;
	int p=mid,q=mid,A=a[mid],B=a[mid];
	int tot=ans;
	for(int i=mid;i>=l;--i) {
		A=min(A,a[i]),B=max(B,a[i]);
		while(p<r&&A<=a[p+1]) p++;
		while(q<r&&B>=a[q+1]) q++;
		L=mid+1,R=min(p,q);
		if(L<=R) 
			add(ans,1LL*A*B%mod*((L+R+2-2LL*i)*(R-L+1)/2%mod)%mod);
		L=p+1,R=q;
		if(L<=R)
			add(ans,1LL*B*jan(sum_mii[R],sum_mii[L-1])%mod),
			add(ans,1LL*jan(1,i)*B%mod*jan(sum_mi[R],sum_mi[L-1])%mod);
		L=q+1,R=p;
		if(L<=R)
			add(ans,1LL*A*jan(sum_mai[R],sum_mai[L-1])%mod),
			add(ans,1LL*jan(1,i)*A%mod*jan(sum_ma[R],sum_ma[L-1])%mod);
		L=max(p+1,q+1),R=r;
		if(L<=R)
			add(ans,jan(sum_mimai[R],sum_mimai[L-1])),
			add(ans,1LL*jan(1,i)*jan(sum_mima[R],sum_mima[L-1])%mod);
	}
}
int main() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	cdq(1,n);
	printf("%d",ans);
	return 0;
}