莫队好题啊

莫队来做这个题的难点就是考虑如何在\(O(1)\)时间内由\([l,r]\)转移到\([l,r+1]\)

显然加入\(r+1\)这个数之后会和之前所有的位置都产生一个区间，就是要去快速求出这个区间的和

我们先利用单调栈，扫出每个点往左往右都能扩展到哪里，在处理出一个数组\(dp[i]\)表示从\(1\),\(2\),\(3\)$$...$ \(i-1\),\(i\)与\(i\)形成的所有区间最小值的和

有了这个单调栈处理出来的东西就很好处理了

之后我们考虑添加\(r+1\)这个点，我们先用\(st\)查出\([l,r+1]\)的最小值\(x\)和最小值的位置\(t\),之后就分成了两段

1. \([l,t]\)都是按照整个区间的最小值来算的，于是直接就是\((t-l+1)\times x\)

2. \([t+1,r+1]\)是有所不同的，但是这个时候我们直接用\(dp[r+1]-dp[t]\)就可以表示出来了

之后有几个坑点

1. 莫队转移的之后要时刻保证\(l<r\)

2. \(add(i++)\)，尽管穿进去的值是\(i\)，但是如果再调用全局变量会是\(i+1\)

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define re register

#define LL long long

#define maxn 100005

inline int read()

{

	re char c=getchar();int x=0,r=1;

	while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x*r;

}

struct Ask{int x,y,rk;}a[maxn];

LL Ans[maxn];

int St[maxn][18],log_2[maxn],t[maxn][18];

int ls[maxn],rs[maxn],st[maxn],top;

LL dp[maxn],f[maxn];

LL ans;

int n,m,sz,l,r;

inline std::pair<int,int> ask(int L,int R)

{

	int k=log_2[R-L+1];

	if(St[L][k]<St[R-(1<<k)+1][k]) return std::make_pair(t[L][k],St[L][k]);

	return std::make_pair(t[R-(1<<k)+1][k],St[R-(1<<k)+1][k]);

}

inline int cmp(Ask A,Ask B){if(A.x/sz==B.x/sz) return A.y<B.y;return A.x<B.x;}

inline void solve_r(int x,LL opt)

{

	LL now=dp[x]; std::pair<int,int> pii=ask(l,x);

	now=now-(LL)dp[pii.first]+(LL)pii.second*(LL)(pii.first-l+1);ans+=opt*now;

}

inline void solve_l(int x,LL opt)

{

	LL now=f[x]; std::pair<int,int> pii=ask(x,r);

	now=now-(LL)f[pii.first]+(LL)pii.second*(LL)(r-pii.first+1);ans+=opt*now;

}

int main()

{

	n=read(),m=read();memset(St,20,sizeof(St));

	for(re int i=1;i<=n;i++) St[i][0]=read(),t[i][0]=i;

	for(re int i=2;i<=n;i++) log_2[i]=1+log_2[i>>1];

	for(re int j=1;j<=17;j++)

		for(re int i=1;i+(1<<j)-1<=n;i++)

			if(St[i][j-1]<St[i+(1<<(j-1))][j-1]) St[i][j]=St[i][j-1],t[i][j]=t[i][j-1];

				else St[i][j]=St[i+(1<<(j-1))][j-1],t[i][j]=t[i+(1<<(j-1))][j-1];

	sz=std::sqrt(n);

	for(re int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(),a[i].rk=i;

	std::sort(a+1,a+m+1,cmp);

	for(re int i=1;i<=n;i++) {while(top&&St[st[top]][0]>St[i][0]) rs[st[top]]=i,top--;st[++top]=i;}

	while(top) rs[st[top]]=n+1,top--;

	for(re int i=n;i;--i) {while(top&&St[st[top]][0]>St[i][0]) ls[st[top]]=i,top--;st[++top]=i;}

	while(top) ls[st[top]]=0,top--;

	for(re int i=1;i<=n;i++) dp[i]=(LL)St[i][0]*(LL)(i-ls[i])+dp[ls[i]];

	for(re int i=n;i;--i) f[i]=(LL)St[i][0]*(LL)(rs[i]-i)+f[rs[i]];

	l=1,r=1,ans=St[1][0];

	for(re int i=1;i<=m;i++)

	{

		while(l>a[i].x) solve_l(--l,1);

		while(r<a[i].y) solve_r(++r,1);

		while(l<a[i].x) solve_l(l++,-1);

		while(r>a[i].y) solve_r(r--,-1);

		Ans[a[i].rk]=ans;

	}

	for(re int i=1;i<=m;i++) printf("%lld\n",Ans[i]);

	return 0;

}