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

luogu P1719 最大加权矩形

题目大意

需要支持在一个序列中插入等差数列
需要插入\(O(1)\) 最终统计答案\(O(n)\)
\(1\leq n\leq 1e7\)

Sol

对于一个序列如下:

0 0 4 6 8 10 12 0 0

我们将其进行一次差分,可以得到:

0 0 4 2 2 2 2 -12 0

可以发现中间出现了一串公差,在差分一次:

0 0 4 -2 0 0 0 -14 12

应该可以看出来,给定的四个数 \(l\),\(r\),\(s\),\(e\)以及公差\(d=\frac{e-s}{r-l}\)
其实就是在差分数组\(d\)中将

  • \(d_l\)\(s\)
  • \(d_{l+1}\)\(d-s\)
  • \(d_{r+1}\)\(d+e\)
  • \(d_{r+2}\)\(e\)

最后进行两次差分即可

Code

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1e7+10;int n , m;
LL sum1[N] , sum2[N];int main() {scanf("%d%d" , &n , &m);for(int i = 1 ; i <= m ; i ++) {LL l , r , s , e , d = 0;scanf("%lld%lld%lld%lld" , &l , &r , &s , &e);if(r != l) d = (e-s)/(r-l);sum1[l] += s; sum1[l+1] += d-s;sum1[r+1]-=d+e; sum1[r+2]+=e;}LL res1 = 0 , res2 = 0;for(int i = 1 ; i <= n ; i ++) {sum1[i] += sum1[i-1];sum2[i] = sum2[i-1] + sum1[i];res1 ^= sum2[i];if(sum2[i] > res2) res2 = sum2[i];}printf("%lld %lld\n" , res1 , res2);return 0;
}
http://www.hskmm.com/?act=detail&tid=19277

相关文章:

  • CF2065D Skibidus and Sigma
  • 微信二次开发个人号api
  • 课后作业2(动手动脑,课后实验性问题)
  • 从零开始构建图注意力网络:GAT算法原理与数值实现详解
  • 关于Leetcode 812题的简单思考
  • Laravel5.8 利用 snappyPDF 生成PDF文件
  • 25秋周总结4
  • Python 潮流周刊#121:工程师如何做出高效决策?
  • 饥荒联机版
  • iSCSI网络存储——基于VM17下麒麟V10SP1与SP2的共享配置
  • 微信二次开发文档
  • CSP-S1 2025
  • 金币
  • 课后作业2
  • 加密货币技术革命:揭秘数字复兴时代
  • 详细介绍:CTFshow系列——PHP特性Web113-115(123)
  • 第六篇
  • 6378:删除数组中的元素(链表)
  • DiffDock 环境安装和启用教程
  • [题解]P11533 [NOISG 2023 Finals] Topical
  • day20_修改 删除功能
  • [题解]P10231 [COCI 2023/2024 #4] Putovanje
  • # Windows CMD 基本指令参考手册
  • P13019 [GESP202506 八级] 树上旅行
  • 完整教程:负载均衡式的在线OJ项目编写(二)
  • Java语法基础课程动手动脑及课后实验问题整理文档
  • 安装包制作流程-final
  • 让YOLO飞起来:从CPU到GPU的配置指南
  • 记录这辈子见到的第一道从上到下的树上倍增
  • 06.容器存储 - 教程