TOJ 4244: Sum
4244: Sum
Total Submit: 63 Accepted:10
Description
Given a sequence, we define the seqence's value equals the difference between the largest element and the smallest element in the sequence. As an example, the value of sequence (3, 1, 7, 2) = 7-1 = 6.
Now, given a sequence S, output the sum of all value of consecutive subsequences.
Input
The first line has an integer N (2 ≤ N ≤ 300000) indicating the number of elements of the sequence. Then follows N lines, each line has a positive integer no larger than 108 indicating an element of the sequence.
Output
Output the requested sum.
Sample Input
4
3
1
7
2
Sample Output
31
Hint
The consecutive subsequence of the sequence (3, 1, 7, 2) has:
(3, 1), (1, 7), (7, 2), (3, 1, 7), (1, 7, 2), (3, 1, 7, 2)
The sum of all values equals 2+6+5+6+6+6=31
这题看起来很简单啊,然后自然而然就想到了朴素的O(n^2)做法,然而TLE,仔细一想要不用dp做,保存当前最大值,可是不还是O(n^2),虽然循环次数少点,堆排序TLE同理。那天坐CF做完了无聊了就又在想这道题,想不出来就在群里问了问,大神给了我单调栈的做法和sort排序找位置的方法
sort大法来自010大神 点我获得代码
我的单调栈就是向左向右找到其可以左延伸右延伸的位置,排列组合就好了(左边包括他自己有n个,右侧包括他自己有m个,他的贡献就是(mn-1)个)
然后最大值来一次,最小值来一次,over
和普通的单调栈一样,这个的话就是检查扩展,可以扩展就去和前面那个值一个位置,其实求的就是最多扩展到哪里。一个值最多被访问两次,和单调栈一样都是2*n
单调栈也是,访问这个值,进队,可能还要出队。虽然是for套while但是复杂度还是n
#include <cstdio>
const int N=;
__int64 a[N];
int L[N],R[N];
int main() {
int n;
while(~scanf("%d",&n)) {
for(int i=; i<=n; i++) {
scanf("%I64d",&a[i]);
L[i]=i;
R[i]=i;
}
a[]=-;
a[n+]=-;
for(int i = ; i <= n; i++) {
while(a[i] <= a[L[i] - ])
L[i] = L[L[i] - ];
}
for(int i = n; i >= ; i--) {
while(a[i]< a[R[i] + ])
R[i] = R[R[i] + ];
}
__int64 sum=;
for(int i = ; i <= n; i++) {
sum-=a[i]*(i-L[i]+)*(R[i]-i+);
}
a[]=<<;
a[n+]=<<;
for(int i=; i<=n; i++) {
L[i]=i;
R[i]=i;
}
for(int i = ; i <= n; i++) {
while(a[i] >= a[L[i] - ])
L[i] = L[L[i] - ];
}
for(int i = n; i >= ; i--) {
while(a[i] > a[R[i] + ])
R[i] = R[R[i] + ];
}
for(int i = ; i <= n; i++) {
sum+=a[i]*(i-L[i]+)*(R[i]-i+);
}
printf("%I64d\n",sum);
}
return ;
}
最新文章
- Web Api中的get传值和post传值
- Codeforces Round #246 (Div. 2) A. Choosing Teams
- [zt]java synchronized详解
- C#与数据库访问技术总结(十)之添加&;删除
- 无法创建spool文件
- search help 概述
- DEDECMS采集规则,过滤,替换文章内的部分内容
- hadoop2.2.0+hive-0.10.0完全分布式安装方法
- mac 卸载 XCode
- split
- bzoj 1085: [SCOI2005]骑士精神 IDA*
- 外网訪问内网应用实现之无公网IP、多port、固定port、UDP等应用的实现方法
- 从涂鸦到发布——理解API的设计过程(转)
- 洛谷P5155 [USACO18DEC]Balance Beam(期望,凸包)
- .net 支付宝接口小小误区
- enum &; json 之间的转换
- spring boot 中添加mongodb支持
- /proc文件系统(一):cpuinfo
- uva11552
- pygame小记