Summarize

给定 $n$ 种原材料，每种材料有一个特征值 $a_i$ 和强度 $b_i$。有 $q$ 次查询或修改，询问是给出一段区间 $[l,r]$，要求在 $l,l+1..r-1,r$ 的原材料中选出一个特征值线性无关的子集，是强度值之和最大；修改是修改某种原材料的特征值和强度。

$n\le 100000,q\le 10000,1\le a_i,b_i\le 1000000000$

#3097. 「SNOI2019」通信

Summarize

题目概括咕咕咕（这个好写！）

#1295E. Permutation Separation

Summarize

给定一个 $1-n$ 的排列。将该排列划分为非空的前后缀，要求在两个集合间移动一些元素，其中移动第 $i$ 个元素的代价为 $a_i$，使得在前缀集合中的所有元素均小于后缀集合中的任意元素。

$n\le 2e5,a_i\le 1e9$

#3113. 「SDOI2019」热闹的聚会与尴尬的聚会

Summarize

震惊！tth37居然……

给定一个图 $G$， 要求在图中选出一些点组成两个互不相关的子图 $P$，$Q$，其中子图 $Q$ 为原图的一个独立集。记 $P$ 中的节点最小度数为 $p$，$q=|Q|$。要求 $\lfloor\frac{n}{p+1}\rfloor\le q$ 且 $\lfloor\frac{n}{q+1}\rfloor\le p$，输出一种可行方案。

$n\le 1e5,m\le 1e5$

#3227. 「USACO 2019.12 Platinum」Bessie’s Snow Cow

Summarize

给定$n$个节点的一棵有根树，$q$次操作，每次操作可以令一个节点的子树的所有节点增加一个颜色$i$,或查询一个节点的颜色数

$1 \le n,q \le 10^5$

感谢@oy的贡献

在一条直线上有 $n$ 个炸弹，每个炸弹给定其坐标和爆炸半径；求出引爆每个炸弹时，共有多少炸弹被连锁引爆。

$n\le 500000$

我感谢我自己