求助前几天洛谷CSP-S模拟赛D思路
  • 板块学术版
  • 楼主2020kanade
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/17 13:10
  • 上次更新2023/11/2 13:18:42
查看原帖
求助前几天洛谷CSP-S模拟赛D思路
456724
2020kanade楼主2023/10/17 13:10

rt,根据一堆性质可以对每个点求出序列推平成它时合法区间的起点区间 [sl,sr][sl,sr] 和终点区间 [el,er][el,er],然后我有一个比较抽象的思路不知可行性:

二维平面分别以起点轴和终点轴建系,则每个点可以表示为一个左下顶点为 (sl,el)(sl,el),右上顶点为 (sr,er)(sr,er) 的矩形,每个询问可以抽象为:选中一个左下顶点为 (ql,ql)(ql,ql),右上顶点为 (qr,qr)(qr,qr) 的正方形,将这个正方形内的所有矩形与这个正方形求交后找所有矩形中左下顶点与右上顶点的曼哈顿距离的最大值。

直接结果就是,维护这东西的数据结构过于抽象:需要维护区间 aa 的 checkmincheckmin,区间 max⁡i=lr{ai+min{bi,x}}\max_{i=l}^{r}\{a_i+min\{b_i,x\}\},请问下这个还有救吗,或者说这个思路不太对。

2023/10/17 13:10
加载中...