jsp购物网站开发教程,上海搬家公司排名第一,电子商城网站如何建设,企业门户网站登录三维偏序
CDQ 分治入门题。
采用分治思想#xff0c;对于编号在 [ l , r ] [l,r] [l,r] 中的点对#xff0c;统计都在 [ l , m i d ] [l,mid] [l,mid] 的#xff0c;都在 [ m i d 1 , r ] [mid1,r] [mid1,r] 的#xff0c;再统计跨两个的。
代码
iai 统计三元组
严…三维偏序
CDQ 分治入门题。
采用分治思想对于编号在 [ l , r ] [l,r] [l,r] 中的点对统计都在 [ l , m i d ] [l,mid] [l,mid] 的都在 [ m i d 1 , r ] [mid1,r] [mid1,r] 的再统计跨两个的。
代码
iai 统计三元组
严格小于的三维偏序。
一般的三维偏序去重是因为相同的元素之间可能产生贡献此题相同元素不会产生贡献不用去重。
SOL1
容斥。
统计第一维小于等于后面两维严格小于的个数时间复杂度 O ( n log 2 n ) O(n \log^2 n) O(nlog2n)。
对于第一维相同的做严格小于的二维数点时间复杂度 O ( n log n ) O(n \log n) O(nlogn)。
时间复杂度 O ( n log 2 n ) O(n \log^2 n) O(nlog2n)。代码
SOL2
在 CDQ 递归的时候改变 mid 的位置使得右区间第一维严格大于左区间。
新划分的 mid 不一定在中间时间复杂度不会证但举不出反例。
[SDOI2011] 拦截导弹
离散化是显然的。 f 1 ( i ) f_1(i) f1(i) 表示 i i i 开始的 LDS f 2 ( i ) f_2(i) f2(i) 表示 i i i 结尾的 LDS。 g 1 ( i ) g_1(i) g1(i) 表示 f 1 ( i ) f_1(i) f1(i) 的方案数 g 2 ( i ) g_2(i) g2(i) 表示 f 2 ( i ) f_2(i) f2(i) 的方案数。 f , g f,g f,g 的转移比较显然。
第一问 max ( f i ) \max(f_i) max(fi)正着反着都行。
第二问
先求总方案数即 f f f 能达到 LDS 的 i i i 的 g g g 的和。
再求 LDS 经过 i i i 的方案数。这个时候从 i i i 开始和以 i i i 结尾的都要是 LDS i i i 应满足 f 1 ( i ) f 2 ( i ) − 1 f_1(i)f_2(i)-1 f1(i)f2(i)−1 为 LDS方案数 g 1 ( i ) × g 2 ( i ) g_1(i) \times g_2(i) g1(i)×g2(i)。概率就是这个除以总方案数。
朴素做显然是 O ( n 2 ) O(n^2) O(n2) 的。
三维偏序 dp CDQ 优化。
以 f 2 f_2 f2 为例 f 2 f_2 f2 的转移编号从小到大。因此先遍历左区间用左区间的值转移更新右区间再遍历右区间。
转移过程为先按一维排序然后就是二维数点求最大值。其中需要维护区间最值单点修改考虑 BIT / 线段树。
正反跑两遍。总时间复杂度 O ( n log 2 n ) O(n \log^2 n) O(nlog2n)。
注意点 一般的 CDQ 在遍历当前区间时可以保证当前区间一维是有序的。 这里的 CDQ 由于左中右的处理顺序遍历右区间时要将右区间排序。 一些分支语句更新的时候要注意先后顺序。
记录
[BalkanOI2007] Mokia 摩基亚
在线的二维数点。 加一维时间变成离线的三维偏序。
一发就过了。记录
[HEOI2016/TJOI2016] 序列
由于是任意一种变化应考虑极值。注意任意时刻只有一种变化。
记 f i f_{i} fi 表示以 i i i 结尾的合法子序列长度。 f i max f j 1 f_i \max f_j 1 fimaxfj1其中 j i , a j ≤ m i n ( a i ) , max ( a j ) ≤ a i j i,a_j \le min(a_i), \max(a_j)\le a_i ji,aj≤min(ai),max(aj)≤ai。
三维偏序的 dp 问题考虑 CDQ 优化。
代码
