10590: 阿卡分糖果

时间限制: 10 Sec  内存限制: 128 MB

提交: 48  解决: 15

[] [] [] [命题人:]

题目描述

阿卡的冬眠营马上要结束啦，他正在为这次活动筹办一场闭幕式。闭幕式上他策划了许多精彩的小游戏，并且打算用糖果作为这些小游戏的奖品。但是分糖果成为了一个难题。

阿卡一共让大家玩了M轮小游戏，每一轮都有一个胜出者，阿卡要给他们其中的每个人分一些糖果。

给每个人分相同数量的糖果虽然公平，但这太不符合阿卡的作风了，于是阿卡写了一个随机的小程序，为每个人随机出了一个糖果数量，准备下发。

阿瓦这时走到了阿卡的后面，看到他列出的分糖果的方案，吃了一惊，提醒阿瓦这样分糖果可能有人会报警。

原来阿瓦给了1号胜利者10

⁵个糖果，却只给了2号胜利者1个糖果。

为了科学而有趣地制定分糖果的方案，阿卡设计了一个胜利者们不开心程度的函数。这个函数是这样计算的：

假设第i位胜利者获得了Ai颗糖果。对于每个连续的区间[l,r](1≤l≤r≤n)，设其中Ai的最大值为Max，Ai的最小值为Min，那么就将Max−Min累积到答案当中。

请你帮阿卡计算一下胜利者们不开心的程度，即

 

输入

第一行，一个整数n，表示胜利者的人数。

第二行，n个整数，第i个数Ai，表示第i位胜利者分到的糖果数。

 

输出

共一行，一个整数，表示胜利者们不开心的程度。

 

样例输入

复制样例数据

33 3 2

样例输出

2

 

提示

对于50%的数据，n≤3000。

对于100%的数据，n≤10⁵ 0<Ai≤10⁶。

Solution:

滑动窗口的思想，当前区间的后一个元素如果小于当前区间的最大值，则当前区间可以后移得到相同长度的区间，且最大值不变，但是出现更大的则要减去，维护一个单调队列即可，最小值与最大值同理。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include
          
           #define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)typedef long long ll;using namespace std;const int maxn=1e5+5;template 
           
            inline void rd(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9'){ ret = ret * 10 + (c - '0'), c = getchar(); }}int p[maxn],q[maxn],n,c[maxn];ll ans,cur,t;int main(){ scanf("%d",&n); REP(i,1,n)scanf("%d",&p[i]); REP(i,1,n){ while(t>0&&p[q[t]]
            
             0&&p[c[t]]>p[i]){ cur-=p[c[t]]*(c[t]-c[t-1]); t--; } c[++t]=i; cur+=p[i]*(c[t]-c[t-1]),ans-=cur; } cout<
             
              <