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

CF1824D 题解

\(\sum\limits _ {i = l} ^ r \sum\limits _ {j = x} ^ y g(i,j)\)

离线询问,扫描线 \(j\),线段树维护 \(g(i)\),那么,转换为求解 \(x\) 时刻到 \(y\) 时刻,线段树区间 \([l,r]\) 的区间和的历史和。

考虑扫描线 \(j \leftarrow j + 1\) 时,会如何变化。

我们设一个辅助数组 \(s_i\) 表示一个位置是否是这个值的最后一次出现。那么 \(g(i)\) 相当于说 \(\ge i\)\(s = 1\) 的最小下标。

而我们 \(j\) 移动时,\(s_{pre_j}\leftarrow 0, s_j \leftarrow 1\)

然后,我们就要在 \(g\) 的这个线段树上对本身 \(pre_{a_j}\) 到上一个 \(1\) 的位置中这些值都变成 \(pre_{a_j}\) 的后一个 \(1\),并且把 \(j\) 的位置修改成 \(j\)

其中 \(pre_i\) 表示满足 \(a_j = i\) 的最大的 \(j\)

线段树要支持:区间推平,区间查询历史和。

维护一个向量 \(\begin {bmatrix} hsum, sum, len\end{bmatrix}\)

修改矩阵:

\[\begin{bmatrix}1 & 0 & 0\\0 & 0 & 0\\0 & v & 1\\\end{bmatrix} \]

更新历史和矩阵:

\[\begin{bmatrix}1 & 0 & 0\\1 & 1 & 0\\0 & 0 & 1\end{bmatrix} \]

我们需要查询当前某个数前面/后面第一个 \(s=1\) 的位置,那么我们需要维护下标集合,用一个 std::set 即可。

http://www.hskmm.com/?act=detail&tid=33350

相关文章:

  • 单目深度估计 - MKT
  • CF1059 Codeforces Round 1059 (Div. 3) 游记
  • newDay12
  • PyTorch与卷积神经网络读书报告
  • QOJ857 Social Distancing
  • 142. 环形链表 II
  • 10.17日学习笔记
  • KV缓存(Key-Value Cache)
  • 模型验证
  • Transformer
  • 面试题 02.07. 链表相交
  • 10月17日记
  • 带高度多边形,生成3D建筑模型,支持多种颜色或纹理的OBJ、GLTF、3DTiles格式
  • aaaaaa
  • 突然发现,越研究越没意思
  • 无需重新训练即可为语音识别器添加新词
  • 思科关键漏洞警报:TACACS+认证缺陷可导致网络完全暴露
  • ysyx学习:移植rt-thread
  • 综合性题目
  • 实用指南:从入门到精通:Django的深度探索之旅
  • UML中9中数据流图总结
  • 两种树状数组
  • 斑马日记2025.10.17
  • CF Global Round 29(#2147) 总结
  • 详细介绍:C语言中#pragma的用法
  • JAVA 中断处理
  • 第十五天
  • 软件工程学习日志2025.10.17
  • 天黑了,睡觉
  • 升鲜宝生鲜配送供应链管理系统---- 门店收银 POS 离线工作设计文档(支持线上线下一体化)---02