当前位置: 首页 > news >正文

luogu P6503 [COCI 2010/2011 #3] DIFERENCIJA

题目大意

题面
让我们求一个序列中的

\[\sum^{n}_{i=1}\sum^{n}_{j=i}(\max_{i\leq k\leq j} a_k-\min_{i\leq k \leq j} a_k) \]

Sol

由于暴力是\(O(n^2)\)的,所以我们需要优化
我们先看暴力的流程:

  • 每次选取一段区间求出其中的最大最小值(可以使用滑动窗口控制右端点)
  • 随后计算答案

复杂度瓶颈主要在于对于每一个右端点都要处理一次
我们把原式拆开:

\[\sum^{n}_{i=1}\sum^{n}_{j=i}\max_{i\leq k\leq j} a_k-\sum^{n}_{i=1}\sum^{n}_{j=i}\min_{i\leq k \leq j} a_k \]

看起来求最大值和最小值的方法是一致的,所以我们先考虑求最大值
对于每一个\(a_i\),我们一定能找到一个最大的区间\([l,r]\)满足\(\max_{l\leq k\leq r} a_k=a_i\)
这个时候就存在\((i-l+1)(r-i+1)\)个区间最大值为\(a_i\) (可以参考左边选几个 右边选几个理解,左右可以不选)
如果要直接维护一个数的区间,复杂度依然不对
转换一下,既然这个区间是最大的,那么说明\(a_{l-1}\)\(a_{r+1}\)一定是大于等于\(a_i\)的 (至于为什么大于等于待会说)
这个时候就变成了单调栈的模板,维护一个数左边第一个比他大的数的位置
上面个区间个数就可以变成\((i-L)(R-i)\) ,其中\(L\)为左边第一个大于它的数,\(R\)为右边第一个大于等于它的数
一边取等于一边不取是因为不会产生重复贡献 (考虑一下 \(1,0,1,0,1\)的情况)
(也可以左边取右边不取)

最小值同理,整体复杂度是\(O(n)\),可以AC

Code

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 3e5+10;int n;
LL a[N];
LL ss[N] , hh , tt;
LL lmax[N] , rmax[N] , lmin[N] , rmin[N];int main() {scanf("%d" , &n);for(int i = 1 ; i <= n ; i ++)scanf("%lld" , &a[i]);hh = 0; tt = -1;for(int i = 1 ; i <= n ; i ++) {while(hh <= tt && a[ss[tt]] <= a[i]) tt --;if(hh <= tt) lmax[i] = ss[tt];ss[++ tt] = i;}hh = 0; tt = -1;for(int i = 1 ; i <= n ; i ++) {while(hh <= tt && a[ss[tt]] >= a[i]) tt --;if(hh <= tt) lmin[i] = ss[tt];ss[++ tt] = i;}hh = 0; tt = -1;for(int i = n ; i >= 1 ; i --) {while(hh <= tt && a[ss[tt]] < a[i]) tt --;if(hh <= tt) rmax[i] = ss[tt];else rmax[i] = n+1;ss[++ tt] = i;}hh = 0; tt = -1;for(int i = n ; i >= 1 ; i --) {while(hh <= tt && a[ss[tt]] > a[i]) tt --;if(hh <= tt) rmin[i] = ss[tt];else rmin[i] = n+1;ss[++ tt] = i;}LL res = 0;for(int i = 1 ; i <= n ; i ++) {res += a[i] * (i - lmax[i]) * (rmax[i] - i);res -= a[i] * (i - lmin[i]) * (rmin[i] - i);}printf("%lld\n" , res);return 0;
}
http://www.hskmm.com/?act=detail&tid=22089

相关文章:

  • 详细介绍:自动化接口框架搭建分享-pytest第三部分
  • Solon Plugin 自动装配机制详解
  • 2025宅基地纠纷律所权威推荐榜:专业调解与胜诉保障实力之选
  • 2025上海骨灰盒哪里买优质厂家权威推荐榜:匠心工艺与品质服务之选
  • 实用指南:华为 HCIA-Datacom 备考:VRP 通用路由平台原理-实操
  • Voice Agent Camp 结营!完整项目名单公布丨超音速计划 2025
  • 2025上海寿衣哪里买权威推荐:优质供货商与暖心服务之选
  • AI 真能胜任专业工程师的工作吗?
  • 容器中与内存相关的几个参数
  • 第一次软工作业
  • OpenWRT中备份多个docker容器的脚本 -
  • 动态分区分配算法
  • 上海殡葬一条龙服务权威推荐:寿衣、骨灰盒购买定制服务暖心陪伴与专业仪式之选
  • potplayer截图
  • OpenAI发布提示词集
  • 303、杂诗
  • 完整教程:第三方软件测试公司:【Gatling基于Scala的开源高性能负载测试工具】
  • 微信小程序开发 - MrFlySand
  • 电脑性能优化综合指南:从网络到硬件的不全面解答
  • 连续分配管理方式
  • 验证码破解:机器学习辅助电商爬虫 - 教程
  • 【光照】[PBR][几何遮蔽]实现方法对比
  • 完整教程:C++设计模式之结构型模式:适配器模式(Adapter)
  • 网页访问速度很慢,远程仓库调用很慢
  • 深入解析:【项目】Vision Master OpenCV 3.0 版本(预)发行说明
  • 2025木方厂家权威推荐榜:实力工厂与优质供应之选
  • 10 月做题记录
  • LoRa/LoRaWAN技术手册
  • 便宜的 VPS
  • 2025南通宠物医院权威推荐榜:专业诊疗与暖心服务口碑之选