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=300005; __int64 a[N]; int L[N],R[N]; int main() { int n; while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) { scanf("%I64d",&a[i]); L[i]=i; R[i]=i; } a[0]=-1; a[n+1]=-1; for(int i = 1; i <= n; i++) { while(a[i] <= a[L[i] - 1]) L[i] = L[L[i] - 1]; } for(int i = n; i >= 1; i--) { while(a[i]< a[R[i] + 1]) R[i] = R[R[i] + 1]; } __int64 sum=0; for(int i = 1; i <= n; i++) { sum-=a[i]*(i-L[i]+1)*(R[i]-i+1); } a[0]=1<<30; a[n+1]=1<<30; for(int i=1; i<=n; i++) { L[i]=i; R[i]=i; } for(int i = 1; i <= n; i++) { while(a[i] >= a[L[i] - 1]) L[i] = L[L[i] - 1]; } for(int i = n; i >= 1; i--) { while(a[i] > a[R[i] + 1]) R[i] = R[R[i] + 1]; } for(int i = 1; i <= n; i++) { sum+=a[i]*(i-L[i]+1)*(R[i]-i+1); } printf("%I64d\n",sum); } return 0; }
相关文章
- ORA-30455: summary contains VARIANCE without corresponding SUM & COUNT ORACLE 报错 故障修复 远程处理
- ORA-14056: partition number string: sum of PCTUSED and PCTFREE may not exceed 100 ORACLE 报错 故障修复 远程处理
- MongoDB 中聚合统计计算–$SUM表达式
- MySQL 中的 SUM 函数:快速实现数据统计(mysqlsum统计)
- Subarray Sum K详解编程语言
- 函数MySQL中 Sum函数的好处(mysql的sum)
- MySQL数据相加技巧——利用Sum函数(mysql数据相加)
- MySQL SUM 条件下的计算结果分析(mysql sum 条件)
- MySQL中sum函数的作用(mysql中sum的功能)
- 汇总统计数据MySQL中如何使用sum按条件筛选数据(mysql中sum按条件)
- MySQL中如何使用SUM函数(mysql中sum怎么用)
- MySQL中如何使用SUM计算并赋值(mysql中sum并赋值)
- MySQL中的Sum函数统计数据总和(mysql 中sum函数)
- Oracle总和运算从入门到精通(oracle中使用sum)
- 使用Oracle灵活性求和Sum计算(oracle中sum计算)
- Oracle SUM函数计算精度把它化整为零(oracle sum精度)
- php数组函数序列之array_sum()-计算数组元素值之和