首页 > 代码库 > Educational Codeforces Round 23 D. Imbalanced Array(单调栈)

Educational Codeforces Round 23 D. Imbalanced Array(单调栈)

2024-10-09 08:49:39   215人阅读

题目链接：Educational Codeforces Round 23 D. Imbalanced Array

题意：

给你n个数，定义一个区间的不平衡因子为该区间最大值-最小值。

然后问你这n个数所有的区间的不平衡因子和

题解：

对每一个数算贡献，a[i]的贡献为 当a[i]为最大值时的 a[i]*(i-l+1)*(r-i+1) - 当a[i]为最小值时的a[i]*(i-l+1)*(r-i+1)。

计算a[i]的l和r时，用单调栈维护。具体看代码，模拟一下就知道了。

然后把所有的贡献加起来。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 typedef long long ll;
 5 typedef pair<int,int> P;
 6 
 7 const int N=1e6+7;
 8 int n,a[N],l[N],r[N],top;
 9 ll ans;
10 P S[N];
11 void work()
12 {
13     top=1,S[1]=P(N,0);
14     F(i,1,n)
15     {
16         while(S[top].first<=a[i])top--;
17         l[i]=S[top].second+1;
18         S[++top]=P(a[i],i);
19     }
20     top=1,S[1]=P(N,n+1);
21     for(int i=n;i;i--)
22     {
23         while(S[top].first<a[i])top--;
24         r[i]=S[top].second-1;
25         S[++top]=P(a[i],i);
26     }
27     F(i,1,n)ans+=1ll*a[i]*(i-l[i]+1)*(r[i]-i+1);
28 }
29 
30 int main(){
31     scanf("%d",&n);
32     F(i,1,n)scanf("%d",a+i);
33     work();
34     F(i,1,n)a[i]*=-1;
35     work();
36     printf("%lld\n",ans);
37     return 0;
38 }
View Code

 

Educational Codeforces Round 23 D. Imbalanced Array(单调栈)


联系
我们