分块求优化

#include<bits/stdc++.h>
#define gc() getchar_unlocked()
using namespace std;
int n,q,c,lg[200006],a[200006],t[200006],ll[200006],rr[200006],s[200006],l[200006],r[200006],st[200005],dp[200005][36];
long long ans[200006],d[200006];
int mxx(int x,int y){
	return ((x<y)?y:x);
}
int qu(int l,int r){
	int cc=r-l+1;
	cc=lg[cc];
	return mxx(dp[l][cc],dp[r-(1<<cc)+1][cc]);
}
inline int kd(){
	int z=0;
	char c=gc();
	while(c<'0'||c>'9') c=gc();
	while(c>='0'&&c<='9') z=(z<<1)+(z<<3)+(c^48),c=gc();
	return z;
}
inline void kc(long long x){
	if(x>=10) kc(x/10);
	putchar_unlocked(x%10+'0');
}
signed main(){
	n=kd(),q=kd();
	lg[0]=-1;
	for(register int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;
	int cnt=sqrt(n),gs=n/cnt+(n%cnt!=0);
	for(register int i=1;i<=gs;++i) l[i]=(i-1)*cnt+1,r[i]=i*cnt;
	r[gs]=n;
	for(register int i=1;i<=n;++i) a[i]=kd(),s[i]=(i-1)/cnt+1,dp[i][0]=a[i];
	for(register int i=1;i<=18;++i)
		for(register int j=1;j+(1<<i)-1<=n;j++) dp[j][i]=mxx(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
	for(register int i=1;i<=q;++i) t[i]=kd(),ll[i]=kd(),rr[i]=kd();
	for(register int i=n;i;--i){
		while(c&&a[st[c]]<a[i]) c--;
		st[c]=i;
	}
	for(register int i=1;i<=gs;++i){
		for(register int j=0;j<=n;++j) d[j]=0;
		int w=l[i]-1;
		for(register int j=l[i];j<=r[i];++j){
			int mx=0;
			st[++w]=qu(mxx(1,j-cnt),j);
			for(register int k=0;k<=cnt;++k){
				if(j-k>0) mx=mxx(mx,a[j-k]);
				d[k]=d[k]+mx;
			}
		}
		int gl=-1,gr=-1;
		for(register int j=l[i];j<w;j++)
			if(st[j]<st[j+1]){
				gl=j,gr=j+1;
				break;
			}
		if(gl==-1) gl=w,gr=w+1;
		int mx=qu(mxx(1,l[i]-cnt),l[i]),ww=l[i];
		for(register int j=cnt+1;j<=n;++j){
			if(j<l[i]) mx=mxx(mx,a[l[i]-j]),st[--ww]=mx;
			d[j]=d[j-1];
			if(gr>w)
				if(gl==ww) continue;
				else d[j]=d[j]+(st[ww]-st[gl--]);
			else
				if(st[gl]<st[gr])
					if(gl==ww) continue;
					else d[j]=d[j]+(st[ww]-st[gl--]);
				else d[j]=d[j]+(st[ww]-st[gr++]);
		}
		for(register int j=1;j<=q;++j) if(ll[j]<l[i]&&r[i]<rr[j])  ans[j]=ans[j]+d[t[j]];
	}
	for(register int i=1;i<=q;++i){
		if(s[ll[i]]==s[rr[i]]) for(int j=ll[i];j<=rr[i];++j) ans[i]=ans[i]+qu(mxx(j-t[i],1),j);
		else{
			for(register int j=ll[i];j<=r[s[ll[i]]];++j) ans[i]=ans[i]+qu(mxx(1,j-t[i]),j);
			for(register int j=l[s[rr[i]]];j<=rr[i];++j) ans[i]=ans[i]+qu(mxx(1,j-t[i]),j);
		}
		kc(ans[i]),putchar_unlocked('\n');
	}
}