「HEOI2016/TJOI2016」序列-CDQ分治优化dp

佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。

现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可 。

注意:每种变化最多只有一个值发生变化。

「SDOI2011」拦截导弹-CDQ分治优化dp

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹,但是以后每一发炮弹都不能高于前一发的高度,其拦截的导弹的飞行速度也不能大于前一发。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下,我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个,如果有多个最优方案,那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度,你的任务是计算出在执行上述决策时,每枚导弹被拦截掉的概率。

「BOI2007」Mokia-CDQ分治套CDQ分治

在定位系统中,世界被认为是一个 $W \times W$ 的正方形区域,由 $1 \times 1$ 的方格组成。每个方格都有一个坐标 $(x,y)$ , $1 \leq x,y \leq W$。

有三种命令,意义如下:

  • 0 W 初始化一个全零矩阵。本命令仅开始时出现一次。
  • 1 x y A 向方格(x,y)中添加A个用户。A是正整数。
  • 2 X1 Y1 X2 Y2 查询 $X1 \leq x \leq X_2$ , $Y_1 \leq y \leq Y_2$ 所规定的矩形中的用户数量
  • 3 无参数 结束程序。本命令仅结束时出现一次。

「CQOI2011」动态逆序对-CDQ分治

对于序列 $A$ ,它的逆序对数定义为满足 $i<j$ ,且 $A_i>A_j$ 的数对 $(i,j)$ 的个数。
给出一个 $1$ 到 $n$ 的排列,按照某种顺序依次删除 $m$ 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

「模板」陌上花开-CDQ分治+树状数组

有 $n$ 朵花,每朵花有三个属性:花形( $s$ )、颜色( $c$ )、气味( $m$ ),用三个整数表示。显然,两朵花可能有同样的属性。

定义一朵花 $A$ 比另一朵花 $B$ 要美丽,当且仅当 $S_a\geq S_b$ , $C_a\geq C_b$ , $M_a \geq M_b$ 。定义一朵花的等级是它拥有的美丽能超过的花的数量。

求出每个等级的花的数量。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×