题解 P6503 【[COCI2010-2011#3] DIFERENCIJA】
sukimo
2020-07-23 20:53:48
这题其实和$P1950$有异曲同工之妙。
最开始，我想到的是单调队列滑动窗口来做，滑$n$次出答案，时间$n^2$。但看看数据规模。$n$可达 $3×10^5$，看来只要和“序列两端点枚举”“分界性明确，一个一个求”扯上关系的方法，都不大可行。于是只能使用其他更快的类似“同时进行”的方法。于是考虑单调栈。题目中的式子可转化为：$\sum_{i=1}^n \sum_{j=i}^nmax\ a_k(i\le k\le j)-\sum_{i=1}^n \sum_{j=i}^nmin\ a_k(i\le k\le j)$
于是跑两遍单调栈，分别求出以每个元素作为最小值，最大值所带来的区间个数贡献。例如，若有$x$个以$a_i$为最大值的区间，则最终结果一定会加$x\times a_i$。最小值则减去。单调队列是以滑动为中心，走到哪里累积到哪里；而单调栈则可以以每一个元素为中心，一次就把该元素带来的贡献扩张完毕，自然效率大增。
最后别忘开$long\ long$！
代码：
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MX=300005;
int n,le_cnt[MX],array[MX];ll tot;struct STR{int pos,num;};stack<STR>stk;
STR pack(int pos,int num){STR a;a.pos=pos;a.num=num;return a;}
void stk_push1(){
for(int i=1;i<=n;i++){
while(!stk.empty()&&stk.top().num<array[i]){
tot+=(ll)(array[stk.top().pos])*(ll)(i-stk.top().pos)*(ll)(le_cnt[stk.top().pos]+1);stk.pop();
}
le_cnt[i]=i-(stk.empty()?1:stk.top().pos+1);stk.push(pack(i,array[i]));
}
while(!stk.empty()){
tot+=(ll)(array[stk.top().pos])*(ll)(n-stk.top().pos+1)*(ll)(le_cnt[stk.top().pos]+1);stk.pop();
}
}
void stk_push2(){
for(int i=1;i<=n;i++){
while(!stk.empty()&&stk.top().num>array[i]){
tot-=(ll)(array[stk.top().pos])*(ll)(i-stk.top().pos)*(ll)(le_cnt[stk.top().pos]+1);stk.pop();
}
le_cnt[i]=i-(stk.empty()?1:stk.top().pos+1);stk.push(pack(i,array[i]));
}
while(!stk.empty()){
tot-=(ll)(array[stk.top().pos])*(ll)(n-stk.top().pos+1)*(ll)(le_cnt[stk.top().pos]+1);stk.pop();
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&array[i]);
stk_push1();stk_push2();printf("%lld",tot);
return 0;
}
```