#3097. 「SNOI2019」通信

Summarize

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

题目链接

给定一个$n \times m$的矩阵，每个点编号为$(i - 1) \times m + j$每次抽取一个点，然后让队列先向左再向前，最后将这个点放在$(n,m)$的位置，告知每次离队点的位置，求离队点的编号

$1 \le n,m,q \le 3 \times 10^5$

感谢@oy的贡献

题目链接

给定一棵$n$个节点的树，进行$q$次操作：单点修改，或查询一条树链上的第$k$小值。

$n,q \le 80000,0 \le k \le n$

感谢@oy的贡献

本文部分内容转载自 OI Wiki 树状数组套主席树

概述

普通数据结构维护单一维度信息，树套树维护多维度信息。

题目链接

给定一棵$n$个节点的树，每个节点上有一个权值。对于$m$次询问，需要输出$u$到$v$的最短路径上第$k$小的点权。

$1\le n\le 100000,1 \le m\le 100000$

感谢@tth37 的贡献