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\)
后面的游戏结果会影响前面的概率 = =
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\)
在有些dp中，转移可以用一种具有结合律的变换描述，并且可以快速合并
因此我们使用数据结构维护，来支持修改并快速得到全局或某个子结构的dp值
你有一棵\(n\)个点的树，边有权，有两种操作
CHANGE x y，表示修改第\(x\)条边的边权为\(y\)
QUERY x y，表示询问点\(x\)到\(y\)路径上的边权最大值
在数轴上有\(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\)