「Codeforces 1060G」Balls and Pockets
Codeforces 1060G. Balls and Pockets
有一个从 $0$ 到 $\infty$ 的序列，第 $a_1,a_2,\dotsc,a_n$ 个位置上各有一个口袋
每秒每个口袋会吃掉当前位置上的数，较大的数会向较小的方向移动以填补空位
$m$ 次询问在 $k_i$ 秒后一个位置 $x_i$ 上的数是什么
$a_1< a_2< \cdots< a_n$
$n,m\le 10^5, a_i,k_i,x_i\le 10^9$
给定一个长为 $n$ 的序列 $A_1,\dotsc,A_n$，求一个长为 $n$ 的不下降序列 $B_1,\dotsc,B_n$，使得 $\sum_{i=1}^n (A_i-B_i)^2$ 最小，只需要输出最小值
以及 $m$ 次互相独立的修改，每次会更改一个位置的值，要求输出修改后的答案
模 $998244353$
$n,m\le 10^5$
小 R 和小 B 玩了 $n$ 局游戏，第一局小 R 获胜的概率是 $p_1$，对于第 $i(1<i\le n)$ 局，若第 $i-1$ 局小 R 获胜，则小 R 获胜的概率为 $p_i$，否则为 $q_i$
现在已经知道了若干局的胜负情况，求小 R 获胜次数的期望，在 $m$ 次增加或删除已知条件后都输出答案
$n,m\le 2\times 10^5$
后面的游戏结果会影响前面的概率 = =
「Codeforces 1034D」Intervals of Intervals
zx2003说多 log 过不去，不然就去写了
你有 $n$ 个区间 $[a_i, b_i]$，定义区间的区间 $[l,r]$ 的价值是第 $l$ 个区间到第 $r$ 个区间的并的总长度
你需要找出 $k$ 个不同的区间的区间，使得它们的总价值最大
输出总价值
$1\le n \le 3 * 10^5,1 \le k \le \min{\frac{n(n+1)}{2},10^9}$
给你一张 $n$ 个点 $m$ 条边的无向图，每个点有点权，$q$ 次操作
C a w，将第 $a$ 个点的权值改为 $w$
A a b，询问 $a$ 到 $b$ 所有可能的简单路径上的点权最小值
简单路径即不经过一个点超过一次的路径
$n,m,q\le 10^5$
平面上有$n$个圆，编号$1..n$
重复如下操作直到不存在圆
选择一个半径最大的圆，如果有多个，选择编号最小的
把所有与第1步选出的圆有交的圆删除
其中两个圆有交当且仅当存在一个点，这个点同时被两个圆包含，包含定义为点在圆内或者圆上
$n\le 3*10^5$
你有一棵$n$个点的树，点$y$有一个$[0,m)$内的整数权值$a_u$
定义一棵树的权值是点权的异或和
有$q$次操作
Change x y，表示把第$x$个点的权值改成$y$
Query x，表示询问有多少个非空的联通子树的权值是$x$，模$10007$
$n,q\le30000,m\le128$
在数轴上有$n$家商店，第$i$个商店有坐标$x_i$，种类$t_i\in[1..k]$，出现时间$[a_i,b_i]$
有$q$组询问$l_i,y_i$，表示询问在时间$y_i$，离坐标$l_i$最远的商店类型到$l_i$的距离
类型$t$的商店到一个点的距离定义为所有存在的$t$类商店到这个点的距离的最大值
$1\le n,q\le 3*10^5,1\le k\le n$
$1\le x_i,a_i,b_i\le 10^9$
$1\le l_i,y_i\le 10^8$