#1295E. Permutation Separation

Summarize

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

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

#1295D. Same GCDs

Summarize

给定正整数 $a$，$m$（$a<m$）。计算符合条件的 $x\in[0,m)$ 的个数，使得 $\text{gcd}(a,m)=\text{gcd}(a+x,m)$。

$a\le 1e10,m\le 1e10$

#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$

#43129. 创造

Summarize

题目概括征集中~

#43128. 灭绝

Summarize

题目概括征集中~

#3110. 「SDOI2019」快速查询

Summarize

震惊！tth37 竟自己写题目概括

给定一个长度为 $n$ 的整数数列，执行 $q$ 次操作：

• 将 $a_i$ 赋值为 $val$
• 将所有元素同时加上 $val$
• 将所有元素同时乘上 $val$
• 将所有元素同时赋值为 $val$
• 询问第 $i$ 个元素 $a_i$ 的值
• 询问所有元素的和

$1\le n \le 1e9,1\le q \le 1e7$