题意

给定一个长度为\(n\)的区间\(a_i\)与\(m\)个询问，每次询问给出\(l,r\)，求

\[\sum_{i=l}^r\sum_{j=l}^r(max_{k=i}^ja_k)\times(min_{k=i}^{j}a_k) \]

\(n,m\leq10^5\)

sol

考虑分治。

对于每个区间我们只维护所有跨过了\(mid\)的区间\([i,j]\)对答案的，对于其他多于此的询问的其他区间我们继续下放处理。

对于一个区间，我们枚举右端点，根据\([l,mid]\)中每个点与右端点间\(min,max\)分别是在\([l,mid]\)或是\([mid+1,r]\)上分成四种情况，即\(min/max\)在或不在\([l,mid]\)区间内。容易发现这样的划分方式将\([l,mid]\)划分成了至多四段（可能有重），则该段答案即为四种情况之和。

对于这四种情况，我们建四棵线段树，维护区间和，支持区间加,来维护其系数。（其实显然可以树状数组，考场上脑子抽了）

具体的，我们预处理出整个大区间\([1,n]\)分治的答案，为方便下传询问，将询问打包成个\(vector\)，一起下放即可。

但是这码\(T\)了(((

所以还是用树状数组吧\(QAQ\)

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define N 100005
#define M N<<3
#define lid (id<<1)
#define rid (id<<1|1)
#define mid ((l+r)>>1)
int s[N],maxx[N],minn[N],ans[N],f[M],n,m;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
    return x*f;
}
inline void add1(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline int add2(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
struct seg_tr{
	int lz[M],sum[M],siz[M],num[N];
	void build(int id,int l,int r){
		sum[id]=lz[id]=0;
		if(l==r) siz[id]=num[l];
		else{
			build(lid,l,mid),build(rid,mid+1,r);
			siz[id]=add2(siz[lid],siz[rid]);
		}
	}
	inline void pushdown(int id){
		lz,add1(lz[rid],lz[id]);
		add1(sum[lid],1LL*lz[id]*siz[lid]%mod);
		add1(sum[rid],1LL*lz[id]*siz[rid]%mod);
		lz[id]=0;
	}
	inline void add(int id,int l,int r,int x,int y,int z){
		if(l==x&&r==y) add1(lz[id],z),add1(sum[id],1LL*z*siz[id]%mod);
		else{
			if(lz[id]) pushdown(id);
			if(y<=mid) add(lid,l,mid,x,y,z);
			else if(x>mid) add(rid,mid+1,r,x,y,z);
			else add(lid,l,mid,x,mid,z),add(rid,mid+1,r,mid+1,y,z);
			sum[id]=add2(sum[lid],sum[rid]);
		}
	}
	inline int qry(int id,int l,int r,int x,int y){
		if(l==x&&r==y) return sum[id];
		if(lz[id]) pushdown(id);
		if(y<=mid) return qry(lid,l,mid,x,y);
		if(x>mid) return qry(rid,mid+1,r,x,y);
		return add2(qry(lid,l,mid,x,mid),qry(rid,mid+1,r,mid+1,y));
	}
}tr[5];

struct query{int l,r,id;};
vector<query >qry[M];
inline bool cmpr(query x,query y){return x.r<y.r;}
inline void solve(int id,int l,int r){
	int cnt=qry[id].size();
	if(l==r){
		f[id]=1LL*s[l]*s[l]%mod;
		for(int i=0;i<cnt;i++) add1(ans[qry[id][i].id],1LL*s[l]*s[l]%mod);
		return;
	}
	sort(qry[id].begin(),qry[id].end(),cmpr);
	int lsw=0;while(lsw<cnt&&qry[id][lsw].r<=mid) lsw++;
	maxx[mid]=minn[mid]=s[mid];
	for(int i=mid-1;i>=l;--i){
		maxx[i]=max(maxx[i+1],s[i]);
		minn[i]=min(minn[i+1],s[i]);
	}
	for(int i=l;i<=mid;i++){
		tr[0].num[i]=1;
		tr[1].num[i]=maxx[i];
		tr[2].num[i]=minn[i];
		tr[3].num[i]=1LL*maxx[i]*minn[i]%mod;
	}
	int ma,mi;
	ma=mi=s[mid+1];
	int x,y,z;x=y=z=mid+1;
	for(int i=0;i<4;i++) tr[i].build(1,l,mid);
	for(int i=mid+1;i<=r;i++){
		ma=max(ma,s[i]),mi=min(mi,s[i]);
		
		while(l<x&&minn[x-1]>=mi&&maxx[x-1]<=ma)x--;
		while(l<y&&minn[y-1]>=mi)y--;
		while(l<z&&maxx[z-1]<=ma)z--;
		
		if(x<=mid)tr[0].add(1,l,mid,x,mid,1LL*ma*mi%mod);
		if(y<x){
			tr[1].add(1,l,mid,y,x-1,mi);
			if(l<y)tr[3].add(1,l,mid,l,y-1,1);
		}
		if(z<x){
			tr[2].add(1,l,mid,z,x-1,ma);
			if(l<z)tr[3].add(1,l,mid,l,z-1,1);
		}
		while(lsw<cnt&&qry[id][lsw].r==i){
			if(qry[id][lsw].l>mid||qry[id][lsw].l==l&&qry[id][lsw].r==r){lsw++;continue;}
			for(int t=0;t<4;t++) add1(ans[qry[id][lsw].id],tr[t].qry(1,l,mid,qry[id][lsw].l,mid));
			lsw++;
		}
	}
	for(int i=0;i<4;i++) add1(f[id],tr[i].qry(1,l,mid,l,mid));
	for(int i=0;i<cnt;i++){
		if(qry[id][i].l==l&&qry[id][i].r==r) continue;
		if(qry[id][i].r<=mid) qry[lid].push_back(qry[id][i]);
		else if(qry[id][i].l>mid) qry[rid].push_back(qry[id][i]);
		else{
			qry[lid].push_back((query){qry[id][i].l,mid,qry[id][i].id});
			qry[rid].push_back((query){mid+1,qry[id][i].r,qry[id][i].id});
		}
	}
	solve(lid,l,mid),solve(rid,mid+1,r);
	add1(f[id],add2(f[lid],f[rid]));
	for(int i=0;i<cnt;i++)if(qry[id][i].l==l&&qry[id][i].r==r) add1(ans[qry[id][i].id],f[id]);
}
inline void file(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
}
int main(void){
	//file();
	n=read(),m=read();
	for(int i=1;i<=n;i++) s[i]=read();
	for(int i=1;i<=m;i++){
		qry[1].push_back((query){read(),read(),i});
	}
	solve(1,1,n);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

``