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

概述

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

题目链接

给定一个$2*n$的矩阵，从中选出若干数，且任意两个数不上下或左右相邻，求这些数的最大总和

$1\le n \le 100000,1 \le h_{i,j}\le 1000000000$

咕咕咕~

题目链接

将$n$个$1$和$m$个$0$组成字符串，使得在任意的前$k$个字符中，$1$的个数不能少于$0$的个数。求满足条件的字符串共有多少个。

$1\le m \le n \le 1000000$

概述

乘法逆元定义：如果一个线性同余方程$ax\equiv 1 \mod b$，则$x$成为$a \mod b$的逆元，记作$a^{-1}$。

乘法逆元一般用于求$a/b\mod p$的值（$p$通常为质数），是解决模意义下分数数值的必要手段。

对于$a/b\mod p$，我们可以求出$b$在$\mod p$下的逆元，然后乘上$a$再$\mod p$，就是这个分数的值了。

题目链接

给定一个有$n$个节点的树，在其中选出$m$条没有公共边的路径，并使得$m$条路径中最短路径的长度尽可能大。输出这个最短路径的长度。

$2\le n \le 50000,1\le m\le n-1 $