单调栈求调
查看原帖
单调栈求调
753818
wang_freedom楼主2023/3/13 21:35
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--) 
typedef long long ll;
typedef unsigned long long ull;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+48);
}
bool is_prime(ull x){
	if(x<2)return 0;
	if(x==2)return 1;
	rep(i,1,sqrt(i))
		if(x%i==0)return 0;
	return 1;
}
int gcd(int a,int b){
	return !b?a:gcd(a,a%b);
}
int lcm(int a,int b){
	return a*b/gcd(a,b);
}
using namespace std;
char ch[1005][1005];
int n,m,top,h[1005],l[1005],r[1005],st[1005];
ll ans;
signed main(){
	n=read();m=read();
	rep(i,1,n)
		rep(j,1,m)
			ch[i][j]=getchar();
	rep(i,1,n){
		rep(j,1,m)
			h[j]=ch[i][j]=='*'?0:h[j]+1;
		top=0;
		rep(j,1,m){
			while(top>0&&h[j]<h[st[top]]){
				r[st[top]]=j;
				top--;
			}
			top++;
			st[top]=i;
		}
		while(top>0){
			r[st[top]]=m+1;
			top--;
		}
		top=0;
		per(i,m,1){
			while(top>0&&h[i]<=h[st[top]]){
				l[st[top]]=i;
				top--;
			}
			top++;
			st[top]=i;
		}
		while(top>0){
			l[st[top]]=0;
			top--;
		}
		rep(i,1,m)
			ans+=(i-l[i])*(r[i]-i)*h[i];
	}
	cout<<ans;
	return 0;
}
/*

*/

几乎照着深进敲的,样例输出60,和书上已经对过114514遍了

2023/3/13 21:35
加载中...