Posts
「CQOI2011」动态逆序对-CDQ分治
· ✏️ 973 words · ☕ 2 mins read

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


「ZJOI2013」K大数查询-整体二分
· ✏️ 941 words · ☕ 2 mins read

有 $N$ 个位置, $M$ 个操作。

操作有两种:

  • 如果是 1 a b c 的形式表示在第 $a$ 个位置到第 $b$ 个位置,每个位置加入一个数 $c$ ;
  • 如果是 2 a b c 形式,表示询问从第 $a$ 个位置到第 $b$ 个位置,第 $c$ 大的数是多少。

「模板」陌上花开-CDQ分治+树状数组
· ✏️ 1469 words · ☕ 3 mins read

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

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

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


「HAOI2009」毛毛虫-树形dp
· ✏️ 380 words · ☕ 1 mins read

对于一棵树,我们可以将某条链和与该链相连的边抽出来,称其为一个“毛毛虫”。求在这个树中点数最多的毛毛虫的点数。

$n < 300000$


「LNOI2014」LCA-树链剖分-差分
· ✏️ 933 words · ☕ 2 mins read

给出一个 $n$ 个节点的有根树。有 $q$ 次询问,每次询问给出 $l,r,z$ ,求 $\sum _ {l \leq i \leq r}dep[LCA(i,z)]$ 。


「SCOI2013」多项式的运算-Splay
· ✏️ 1023 words · ☕ 3 mins read

维护一个动态的关于 $x$的无穷多项式 ,这个多项式初始时对于所有 $i$ 有 $a_i = 0$

$$
f(x)=a_0x^0+a_1x^1+a_2x^2…
$$

操作者可以进行四种操作:

  • mul L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数乘上某个定值 $v$ ;

  • add L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数加上某个定值 $v$ ;

  • mulx L R 表示将 $x^L$ 到 $x^R$ 这些项乘上x变量;

  • query V 求 $f(v)$ 的值。

操作集中在前三种,第四种操作不会出现超过 $10$ 次。


「SDOI2014」旅行-树链剖分+动态开点线段树
· ✏️ 827 words · ☕ 2 mins read

给定一棵 $n$ 个节点的树,对于每个点都有两个权值 $w_i,c_i$ 。

存在 $m$ 个操作,分为4类。

  • CC x c”:将 $c_x$ 更改为 $c$ ;

  • CW x w”:将 $w_x$ 更改为 $w$ ;

  • QS x y”:对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$,求 $\sum w_i$ ;

  • QM x y”:对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$ ,求 $\max(w_i)$ ;

对于后两个操作,保证 $c_x = c_y$ 。


可持久化线段树学习笔记
· ✏️ 1204 words · ☕ 3 mins read

可持久化线段树,是一种可以进行可持久化操作的线段树,具有优越的时间复杂度。


「SDOI2011」消防-树的直径+单调队列
· ✏️ 731 words · ☕ 2 mins read

某个国家有 $n$ 个城市,这 $n$ 个点之间的边构成一棵树。

现求一条边长度和不超过 $S$ 的路径(两端都是城市,可以只为一个城市),使得所有城市到这条路径的距离的最大值最小,并输出这个最小值。


「SDOI2013」森林-主席树+LCA+启发式合并
· ✏️ 903 words · ☕ 2 mins read

小Z有一片森林,含有 $N$ 个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有 $M$ 条边。

小Z希望执行 $T$ 个操作,操作有两类:

  • Q x y k 查询点 $x$ 到点 $y$ 路径上所有的权值中,第 $k$ 小的权值是多少。此操作保证点 $x$ 和点 $y$ 连通,同时这两个节点的路径上至少有 $k$ 个点。

  • L x y 在点 $x$ 和点 $y$ 之间连接一条边。保证完成此操作后,仍然是一片森林。

强制在线。

对于所有的数据 $n,m,T \leq 8 \times 10^4$ 。


「HNOI2009」梦幻布丁-set-启发式合并
· ✏️ 597 words · ☕ 2 mins read

$n$ 个布丁摆成一行,每个布丁最开始都有一个颜色 $c_i$ ,进行 $m$ 次操作。

操作格式:

  • 1 c d :将所有的 $c$ 颜色替换为$d$

  • 2 :查询当前布丁序列一共有多少段颜色。例如颜色分别为 $1,2,2,1$ 的四个布丁一共有3段颜色。


「HNOI2010」弹飞绵羊-动态树
· ✏️ 773 words · ☕ 2 mins read

游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每个装置设定初始弹力系数 $K_i$ ,当绵羊达到第 $i$ 个装置时,它会往后弹 $K_i$ 步,达到第 $i+K_i$ 个装置,若不存在第 $i+K_i$ 个装置,则绵羊被弹飞。

存在两种操作:

  • 查询在第 $i$ 个装置起步时,再经多少次会被弹飞。

  • 修改第 $i$ 个装置的弹力系数为 $K’$ 。

保证任何时候,任何装置弹力系数均为正整数。


「HAOI2007」理想的正方形-单调队列
· ✏️ 567 words · ☕ 2 mins read

有一个 $a \times b$ 的整数组成的矩阵,现请你从中找出一个 $n\times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小,输出这个最小的差值。


「CQOI2015」任务查询系统-可持久化线段树
· ✏️ 636 words · ☕ 2 mins read

超级计算机中的任务用三元组 $(S_i,E_i,P_i)$ 描述, $(S_i,E_i,P_i)$ 表示任务运行区间为 $[S_i,E_i]$ ,其优先级为 $P_i$ 。

给出 $n$ 个任务。随后给出 $m$ 个询问,第 $X_i$ 秒正在运行的任务中,优先级最小的 $K_i$ 个任务的优先级之和是多少。特别的,如果 $K_i$ 大于第 $X_i$ 秒正在运行的任务总数,则直接回答第 $X_i$ 秒正在运行的任务优先级之和。

强制在线。