acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(1)讨论(1)提交记录(150)
  • 官方题解|可变数组

    题目解析 线段树;二分查找; 详情参考 ACL|通用「线段树」模板 定义二元运算符 op 和单位元 e。 使用数组 AAA,构建线段树,时间复杂度 O(N)\mathrm{O}(N)O(N)。 1. 对于赋值操作我们直接使用 sgt.set(int p, T x),时间复杂度 O(log⁡N)\mathrm{O}(\log{N})O(logN)。 2. 对于交换操作,和赋值操作类似,先使用 sgt.get(int p) 操作获取 ALA_LAL 和 ARA_RAR 的值,时间复杂度 O(1)\mathrm{O}(1)O(1);然后再使用 sgt.set(int p, T x) 操作,时间复杂度 O(log⁡N)\mathrm{O}(\log{N})O(logN)。 3. 查询区间最大值,使用 sgt.prod(l, r) 操作得出,时间复杂度 O(log⁡N)\mathrm{O}(\log{N})O(logN)。 4. 在线段树上二分查找,使用 sgt.max_right(int l),若返回值大于 RRR 则输出 −1-1−1,否则输出答案。时间复杂度 O(log⁡N)\mathrm{O}(\log{N})O(logN)。 总的时间复杂度 O(N+Qlog⁡N)\mathrm{O}(N + Q\log{N})O(N+QlogN)。 AC代码

    userId_undefined

    アイドル

    73阅读
    0回复
    0点赞
首页