求助弱化动态二维数点
  • 板块学术版
  • 楼主Yorg
  • 当前回复8
  • 已保存回复8
  • 发布时间2025/6/19 19:47
  • 上次更新2025/6/19 20:43:43
查看原帖
求助弱化动态二维数点
617130
Yorg楼主2025/6/19 19:47

初始时 AA 数组全为 \infty 大小为 n×n(n2000)n \times n (n \leq 2000)

只考虑 AA 的上三角 (xy)(x \leq y)
操作有两种
1 x y wAx,ywA_{x, y} \gets w
2 l r 统计当前

minx=lnminy=xrAx,y\min_{x = l}^{n} \min_{y = x}^{r} A_{x, y}

其中 11 操作恰好 n(n+1)2\frac{n(n + 1)}{2} 次填满上三角
22 操作 3×105\leq 3 \times 10^5

有没有什么简单方法处理这种问题?

2025/6/19 19:47
加载中...