原题是给 $a\{n\},L,R,n\le 10^5a{n},L,R,n≤10^5$ , 求

$\sum_{l=L}^R\sum_{r=l}^{R}\min_{l\le i\le r} a_{i}\max_{l\le i\le r} a_{i}$

我的做法是分治，计算左端点小于 mid，右端点会分成三段区间可以 log n 二分计算。

然后应该是 $\mathcal{O}(n\log^2n)$。然后交上去 $n\le100$ 的点都没过。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> 
#include <vector>
using namespace std;
#define int long long 
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAX=1e5+5,P=1e9+7;
int n,m,a[MAX];
int f[MAX][22],g[MAX][22],pma[MAX],pmi[MAX];
int pre[MAX],suf[MAX],pree[MAX];
inline void init(){
	for(register int i=1;i<=n;++i)f[i][0]=g[i][0]=a[i];
	for(register int j=1;j<=21;++j){
		for(register int i=1;i+(1<<j)-1<=n;++i){
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
			g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]);
		}
	}
}
inline int Min(int l,int r){
	int k=log2(r-l+1);
	return min(g[l][k],g[r-(1<<k)+1][k]);
}
inline int Max(int l,int r){
	int k=log2(r-l+1);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
inline int sol(int Mi,int Ma,int L,int R){
	int mid=0,l=L,r=R,x=-1,y=-1,ret=0;
	while(l<=r){// 小于 Mi 的最小位置 
		mid=l+r>>1; 
		if(pmi[mid]<Mi)r=mid-1,x=mid;
		else l=mid+1;
	}
	l=L,r=R;
	while(l<=r){//大于 Ma 的最小位置 
		mid=l+r>>1;
		if(pma[mid]>Ma)r=mid-1,y=mid;
		else l=mid+1;
	}
	if(x==-1&&y==-1)return 1ll*(R-L+1)*Mi%P*Ma%P;
	else if(x==-1)return (1ll*Mi*Ma%P*(y-L)%P+1ll*(suf[R]-suf[y-1]+P)%P*Mi%P)%P;
	else if(y==-1)return (1ll*Mi*Ma%P*(x-L)%P+1ll*(pre[R]-pre[x-1]+P)%P*Ma%P)%P;
	else if(x<=y)return ((1ll*(x-L)*Mi%P*Ma%P+1ll*(pre[y-1]-pre[x-1]+P)*Ma%P)%P+(pree[R]-pree[y-1]+P)%P)%P;//1~x-1,x~y-1,y~R 
	else return ((1ll*(y-L)*Mi%P*Ma%P+1ll*(pre[x-1]-pre[y-1]+P)*Mi%P)%P+(pree[R]-pree[x-1]+P)%P)%P;
	
} 
int work(int l,int r){
	if(l==r)return 1ll*a[l]*a[l]%P;
	int mid=l+r>>1,ret=0;
	ret+=(work(l,mid)+work(mid+1,r))%P;ret%=P;
	pre[mid]=pree[mid]=suf[mid]=0;
	pmi[mid]=1e9+1,pma[mid]=0;
	for(register int i=mid+1;i<=r;++i){
		pmi[i]=min(pmi[i-1],a[i]);
		pre[i]=(pre[i-1]+pmi[i])%P;
		pma[i]=max(pma[i-1],a[i]);
		suf[i]=(suf[i-1]+pma[i])%P;
		pree[i]=(pree[i-1]+1ll*pmi[i]*pma[i]%P)%P;
	}
	int Mi=0,Ma=0;
	for(register int i=l,t;i<=mid;++i){
		Mi=Min(i,mid),Ma=Max(i,mid);
		ret+=sol(Mi,Ma,mid+1,r);
		ret%=P;
//		printf("%lld %lld %lld %lld %lld\n",Mi,Ma,mid+1,r,sol(Mi,Ma,mid+1,r));
	}
	return ret;
}
signed main(){
	n=read(),m=read();
	for(register int i=1;i<=n;++i)a[i]=read();
	init();
	while(m--){
		int l=read(),r=read();
		printf("%lld\n",work(l,r));
	}
	return 0;
}