终于在nowcoder爆发了的懒惰

题目

这类题目我实在忍不了了

Emma，随便做个nowcode比赛题吧,我在oj上也没找到

题意

求\(\sum_{L=1}^{n}\sum_{R=i}^{n}a[k](L<=k<=R)\)，使得和最大

就是求所有区间的最大值之和

思路

我们用一个tot维护 \(\sum_{1}^{i}\)的前缀最大值之和

\(tot<=>\sum_{1}^{i}\)的前缀最大值之和\(
update 12.21（tot是右段点是i的最大值之和）
我们容易发现，数组中的值都是单调递增的
然后我们就维护这个数组，使他每次转移的时候更新个答案ans就ok了
\)ans<=>前i个数的答案$

维护的时候用单调栈就ok了

一开始我理解为单调队列，其实他是个单调栈

他只有一个指针，也就是栈顶在移动

你也可以想象成左边不动的单调队列

对蒟蒻的我来说用语言是很难理解的

举个例子(这里我们只求子串最大值)

1 3 2

队列为空,1进栈 tot[1]=1，ans[1]=1

1弹栈,3进栈 tot[2]=2*3, ans[2]=ans[1]+tot[2]=7;

2进栈 tot[3]=tot[2]+2=8, ans[3]=ans[2]+tot[3]=15;

(这里包含了长度为1的子串)

需要注意的地方

这里5w*5w是炸longlong的

所以

tot+=a[i]*(q[t]-q[t-1]);

这句话后半句是已经炸longlong的，炸longlong无处不在，还是随手开longlong的稳啊

代码

#include <iostream>

#include <cstdio>

#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int maxn=1e5+7;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=(x<<1)+(x<<3)+s-'0';

	return x*f;

}

ll n,a[maxn],q[maxn];

ll solve() {

	ll ans=0,tot=0,t=0;

	FOR(i,1,n) {

		while(t>=1 && a[i]>=a[q[t]]) tot-=a[q[t]]*(q[t]-q[t-1]),t--;

		q[++t]=i;

		tot+=a[i]*(q[t]-q[t-1]);

		ans+=tot;

	}

	return ans;

}

int main() {

	int T=read();

	FOR(kkk,1,T) {

		n=read();

		FOR(i,1,n) a[i]=read();

		ll ans1=solve();

		FOR(i,1,n) a[i]=-a[i];

		ll ans2=solve();

		cout<<ans1+ans2<<"\n";

	}

	return 0;

}