首页 > 代码库 > P2866 糟糕的一天

P2866 糟糕的一天

糟糕的一天

洛谷链接

挺水的一道题,也就是看每个数后面有多少数比它小,最后把总数加起来。

我们可以用单调栈来实现,并用一个数组来保存每个数现在的状态。

代码:

技术分享
 1 #include<cstdio>
 2 long long n,a[80010],stack[80010],top,ans=0;
 3 int main(){
 4     scanf("%lld",&n);
 5     for(long long i=1;i<=n;i++)
 6         scanf("%lld",&a[i]);
 7     a[n+1]=1<<30;
 8     for(long long i=1;i<=n+1;i++){
 9         while(top&&a[stack[top]]<=a[i]){
10             ans+=i-stack[top]-1;
11             top--;
12         }
13         stack[++top]=i;
14     }
15     printf("%lld",ans);
16     return 0;
17 }
View Code

 

P2866 糟糕的一天