当前位置: 首页> 教育> 高考 > 施工企业管理制度_哪里有免费电影网站_石家庄seo代理商_舆情分析网站

施工企业管理制度_哪里有免费电影网站_石家庄seo代理商_舆情分析网站

时间:2025/7/12 2:45:38来源:https://blog.csdn.net/Xixiangrui/article/details/147543299 浏览次数:0次
施工企业管理制度_哪里有免费电影网站_石家庄seo代理商_舆情分析网站

Kinetic tournament tree 简称 KTT 下文中全部简写。

KTT 用于解决类以下问题:

  1. 已知 N N N 条一次函数,求解一段区间内函数最大值。
  2. 支持修改操作可以修改 x i x_i xi 或者 b i b_i bi 的值。

具体做法:

我们考虑线段树来维护一个类似 Δ \Delta Δ 的东西,我们令当前线段树区间 u u u 中函数值最大的线段是 y = k x + b y=kx+b y=kx+b 的,线段树还维护一个 t h r u thr_u thru 表示当前线段树节点下,如果讲 x i x_i xi 加超过 Δ \Delta Δ 这个最大值就会改变。

所以我们实际就是维护 t h r u thr_u thru 的东西。

首先,求当前区间中函数值最大值直接将两个儿子最大值取个 max ⁡ \max max 即可,但是 Δ \Delta Δ 显然可以取到 min ⁡ \min min 但是取到那些的 min ⁡ \min min 呢,首先是 k = min ⁡ ( t h r l s u , t h r r s u ) k=\min(thr_{ls_u},thr_{rs_u}) k=min(thrlsu,thrrsu) 然后就是 Δ u = min ⁡ ( t , 两条线段的交点 ) \Delta u=\min(t,两条线段的交点) Δu=min(t,两条线段的交点) 因为这个时候肯定最大值会变。

然后修改的时候如果此时要加的值是 ≤ t h r u \le thr_u thru 的那就最大值不会发生变化,否则把标记修改下传,势能分析得均摊 O ( log ⁡ 3 n ) O(\log^3n) O(log3n) 的。

然后这就做完了基本操作。

[ROI 2018] Innophone

看到这个题,首先第一眼就是 ( a , b ) (a,b) (a,b) 肯定是原序列中某个 ( x i , y j ) (x_i,y_j) (xi,yj) 的组合,因为这样才不会浪费,就是可以把等于贡献算进去。

然后按照 X X X 为第一关键字排序,这样我们钦定 a = X i a=X_i a=Xi 那么这部分贡献就是 a × ( n − i + 1 ) a\times (n-i+1) a×(ni+1) 然后考虑 i i i 前面的最大的 b = Y j b=Y_j b=Yj 满足 b × ( ∑ k = 1 i − 1 [ Y k ≥ Y j ] ) b\times (\sum_{k=1}^{i-1} [Y_k\ge Y_j]) b×(k=1i1[YkYj]) 这个东西最大,然后显然这个东西形如 y = k × x y=k\times x y=k×x 并且 k k k 固定,每次加入一个 Y i Y_i Yi 只会让那些 k ∈ [ 1 , Y i ] k\in [1,Y_i] k[1,Yi] x k x_k xk 加一,这是个类似权值线段树就能干的东西,我们按照 Y i Y_i Yi 从小到大的顺序来建线段树,然后直接前缀加,全局查找最大值,即可。

时间复杂度是 O ( n log ⁡ 2 n ) O(n\log ^2n) O(nlog2n) 的但是显然跑不满。

代码

关键字:施工企业管理制度_哪里有免费电影网站_石家庄seo代理商_舆情分析网站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: