hk_cnyali's Blog

最近做的一点点CF上的题

并不全

一开始，你有序列$[1, n]$的一棵线段树，有$m$次操作/询问

• 1 l r：在操作队列里加上l, r这个操作。
• 2：询问当前操作队列，每个操作是否执行，总共$2^{k}$（$k$为操作数）种方案中， 线段树上tag为$1$ 的节点个数的总和。答案对$998244353$取模

在线段树上的一次操作$[l, r]$，就是把线段树上所有被$[l, r]$完全覆盖的极大区间的tag设为$1$

$n, m\le 10^5$

一棵 $n$ 个点的树，点权最初为 $1 \sim n$ 的排列。

定义一个删点过程: 每次找到权值最小的叶子,删去它以及连接的边，重复这个过程直到剩下一个点，然后删去最后的点。

处理 $q$ 个询问:

• 将一个点$x$ 的权值赋为当前最大权值 $+1$
• 查询在删点过程中，$x$ 会是第几个被删除的

$n, q \le 2 *10^5$

平面上有若干条线段，有红蓝两种颜色。红色线段与$X$轴平行，蓝色线段与$Y$ 轴平行，同色线段均不相交

已知这些线段之间形成了$n$个交点（在端点相交也算相交）

给出这些交点，求平面上至少有多少条线段，并输出任意一种方案。线段长度允许为$0$

$n \le 10^3 , x_i , y_i \le 10^9$

有一个只包含小写字母，长度为$n$ 的字符串$S$。有一些字母是好的，剩下的是坏的。

定义一个子串$S_{l..r}$是好的，当且仅当这个子串包含不超过$k$个坏的字母。

求有多少个不同的满足以下要求的字符串$T$：

• $T$作为$S$的子串出现过。
• 存在一个$T$出现的位置$[l, r]$，满足$S_{l..r}$是好的

$n, k\le 10^5$

二分图的最大匹配，最小点覆盖，最小边覆盖，最大独立集

DAG的最小路径覆盖，最小链覆盖（可相交路径覆盖），最大独立集，最长反链

一棵$n$个节点带边权的树，边权可能为负

你可以割掉树上恰好$k$条边，然后任意连上边权为$0$的边

求链上边权最大和

$k < n\le 3*10^5$

理解图像意义理解了大半天