noteskey

介绍一种复杂度错误然鹅在随机数据下跑得贼快的算法：笛卡尔树

方法就是 (O~ n) 构造一个笛卡尔树，然后同在线做法一样，就是每个点处理出 (fr[i],fl[i]) 表示以 i 为终止的前缀贡献和后缀贡献，并用 (gr[i],gl[i]) 表示其前/后缀和

然后每次笛卡尔树找到区间最小值的位置，然后这个点会把整个区间分成两份，这样的话我们只要处理两份区间内的答案就好了

对于两份区间我们用 (fl~ fr~ gl~ gr) 四个数组就可以处理出分别的贡献了

code

这份代码在洛咕 4 是怎么也跑不进 150 ms 的

//by Judge
#include<cstdio>
#include<cstring>
#include<iostream>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define ll long long
using namespace std;
const int M=1e5+3;
typedef int arr[M];
typedef ll ARR[M];
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){ int x=0,f=1; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int CCF=-1,Z;
inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}
inline void print(ll x,char chr='
'){
	if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;
	while(z[++Z]=x%10+48,x/=10);
	while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;
} int n,m,rt,top; arr a,s,lc,rc,pre,suf; ARR fl,fr,gl,gr;
inline int query(int l,int r){ //找到这个区间内的最小值位置 
	for(Rg int x=rt;;x=x>r?lc[x]:rc[x])
		if(l<=x&&x<=r) return x;
}
int main(){ n=read(),m=read(),a[0]=a[n+1]=2e9;
	fp(i,1,n){ a[i]=read();
		while(top&&a[s[top]]>=a[i]) lc[i]=s[top--]; 
        	rc[s[top]]=i,s[++top]=i;
	} rt=s[1],top=0;
	fp(i,1,n){
		while(top&&a[s[top]]>a[i]) suf[s[top--]]=i;
		pre[i]=s[top],s[++top]=i;
	}
	while(top) pre[s[top]]=s[top-1],suf[s[top--]]=n+1;
	fp(i,1,n) fr[i]=fr[pre[i]]+1ll*a[i]*(i-pre[i]),gr[i]=gr[i-1]+fr[i];
	fd(i,n,1) fl[i]=fl[suf[i]]+1ll*a[i]*(suf[i]-i),gl[i]=gl[i+1]+fl[i];
	fp(i,1,m){ Rg int l=read(),r=read(),p=query(l,r); //和在线时一样的思路 
		print(1ll*(p-l+1)*(r-p+1)*a[p]+gr[r]-gr[p]-fr[p]*(r-p)+gl[l]-gl[p]-1ll*fl[p]*(p-l));
	} return Ot(),0;
}