CSU 1838 Water Pump(单调栈)

Water Pump

【题目链接】Water Pump

【题目类型】单调栈

&题解：

这题可以枚举缺口,共n-1个,之后把前缀面积和后缀面积用O(n)打一下表,最后总面积减去前缀的i个和后缀的n-1-i个面积就是现在第i+1给缺口漏水的面积

&代码：

#include <cstdio>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f3f3f3f3f

using ll=long long;

const int maxn= 1e5 +9;

int n,a[maxn];

ll le[maxn],ri[maxn];

stack<pair<int,int> > sti;

ll sol(int t[],ll an[])

{

	sti.emplace(t[0],0);

	for(int i=1;i<n;i++){

		while(sti.size()>1&&sti.top().first<=t[i]) sti.pop();

		int fi=sti.top().first,se=sti.top().second;

		if(sti.size()==1){

			if(t[i]<fi){

				an[i]=min(fi,t[i])*(i-se)+an[se];

			}

			else{

				an[i]=min(fi,t[i])*(i-se)+an[se];

				sti.pop();

			}

		}

		else{

			an[i]=min(fi,t[i])*(i-se)+an[se];

		}

		sti.emplace(t[i],i);

	}

}

int main()

{

//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	freopen("E:1.txt","r",stdin);

	int T;scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		for(int i=0;i<n;i++)

			scanf("%d",a+i);

		while(sti.size()) sti.pop();

		sol(a,le);

		reverse(a,a+n);

		while(sti.size()) sti.pop();

		sol(a,ri);

		reverse(ri,ri+n);

//		for(int i=1;i<n;i++){

//			cout<<le[i]<<" ";

//		}cout<<endl;

//		for(int i=1;i<n;i++){

//			cout<<ri[i]<<" ";

//		}cout<<endl;

		ll ans=0;

		for(int i=1;i<n;i++){

//			printf("%lld====\n",le[n-1]-le[i]-ri[i+1]);

			ans=max(ans,abs(le[n-1]-(le[i]+ri[i+1])));

		}

		printf("%lld\n",ans);

		memset(a,0,sizeof(a));

		for(int i=0;i<n;i++){

			le[i]=ri[i]=0;

		}

	}

	return 0;

}