线段树均摊复杂度

GSS4 - Can you answer these queries IV

• 操作 $1$：$a_i=\sqrt{a_i},i\in[l,r]$
• 操作 $2$：询问 $\sum_{i=l}^ra_i$

STL 巧题合集

vector 存图

只要不存反边，点数小于 $10^7$ 就是短！

rope 简要介绍

rope

rope 是 c++ __gnu_pbds 里的一个 STL，实现是可持久化平衡树。

左值，右值

左值（lvalue，即 locator value），是有名字的可以寻址的变量。
右值（rvalue，即 read value），是表达式求值过程中创建的无名临时对象。可以分为纯右值（prvalue，即 pure rvalue，包括临时对象，非引用类型的表达式或非引用类型的表达式）和将亡值（xvalue，即 expiring value，包括非引用类型的非静态数据成员和返回类型是对象的右值引用的函数调用）。

ARC111C Too Heavy 题解

无解的情况：当且仅当一个人手上的物品不是自己的物品，并且这个物品的质量大于自己的体重，这个不是自己的东西就卡手了，换不出去，无解。

ARC120C Swaps 2 题解

设 $a_i=x,a_{i+1}=y$，那么交换后 $a_i\leftarrow y+1,a_{i+1}\leftarrow x-1$，发现交换后就是 $a_i+i$ 和 $a_{i+1}+i+1$ 这两个值进行了交换。

莫比乌斯函数入门

CF1223E Paint the Tree 题解

很有意思的 dp 题。

模拟赛杂题（树，期望）题解

给定一棵有根树，开始每个点是黑色的，每轮操作会随机选一个黑点，然后把这个点到根路径上的所有点染白，问要把所有点全部染白期望需要几轮。
第一行一个 $n$ 表示节点数量。第二行 $n-1$ 个整数，第 $i$ 个整数 $fa_i$ 表示第 $i+1$ 个节点的父亲。$n\le10^7,fa_i<i+1$

CF865B Ordering Pizza 题解

简要题意：有 $n$ 个人去披萨店吃披萨，有两种披萨，每个披萨有 $m$ 片。现在第 $i$ 个人要吃 $c_i$ 片披萨，如果吃一片第一种披萨会获得 $a_i$ 的幸运值，如果吃一片第二种披萨会获得 $b_i$ 的幸运值。现在需要购买最少数量的披萨使得每个人都吃饱并且所有人获得的幸运值之和最大。