Codeforces Beta Round #5
好久没写题解了真是忧桑,估计以后遇到水题大概也懒得写了吧,大学生活真尼玛忙啊,以后遇到好题写题解好了= =。。虽说懒得写题解但是题还是做的,代码均在github.com/mlz000上可以看到= =废话+广告完毕
ABCD跳过~>_<
E:首先将最高的移到第一个,再结尾再加一个最高元素变环为链,令r[i]为第i个元素右边开始第一个严格大于a[i]的元素,c[i]为i~r[i]之间和i高度相等的个数,代码如下:
for(int i=0;i<n;++i){ans+=c[i];if(a[i]==a[0])continue;l[i]=i-1;while(l[i]>0 && a[l[i]]<=a[i])l[i]=l[l[i]];ans+=2;if(l[i]==0 && r[i]==n)--ans;}