[线段树]Codeforces1023D【Array Restoration】题解
题目概述按顺序将 $1\sim q$ 涂到长度为 $n$ 的板上（范围自定），问是否能够涂成目标状态（目标状态中有些通配符）。解题报告被翰爷秒掉了，目标状态中相邻两个相同颜色之间肯定被涂过该颜色...
[二分+后缀树+ST表+DFS序+主席树]LOJ2059(TJOI / HEOI2016)【字符串】题解
题目概述给出一个字符串 $S$ ，求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二分答案 $len$ ，然后只需要验证 $...
[DP+线段树维护矩阵转移]Codeforces573D【Bear and Cavalry】题解
题目概述给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ，有 $m$ 个询问，每次询问先交换 $P_x,P_y$ ，然后询问 $max\...
[圆方树+树链剖分+线段树]Codeforces487E【Tourists】题解
题目概述给出 $n$ 个带权点和 $m$ 条无向边的图，给出 $q$ 个操作：1.修改某个节点的点权。2.询问 $x\to y$ 路径上所有简单路径的最小点权。解题报告简单路径就是一个点不能重复...
[复杂度分析+线段树]HDU6315(2018多校练习赛第二场)【Naive Operations】题解
题目概述给出排列 $\{b_n\}$ 和刚开始都是 $0$ 的 $\{a_n\}$ ，有两种操作：1.把 $a_{[L,R]}$ 都 $+1$ 。2.询问 $\sum_{i=L}^{R}\lfl...
[线段树二分]HDU6301(2018多校第一场)【Distinct Values】题解
题目概述有一个长度为 $n$ 的序列，给出 $m$ 个限制，每个限制形如 $(l_i,r_i)$ 表示 $l_i$ 到 $r_i$ 的数互不相同，求字典序最小的满足条件的序列。解题报告把限制按照...
[DFS序换根+线段树]BZOJ5379【Tree】题解
题目概述有一棵 $n$ 个点的点权树，刚开始根是 $1$ ，现在有 $q$ 次操作：把根换成 $x$ 。把 $LCA(x,y)$ 子树中节点的权值均加上 $w$ 。询问 $x$ 子树的权值和。解...
[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解
题目概述两个数 $x,y$ 可以匹配定义为 $x+y\ge H$ 。现在给出 $\{a_n\}$ 和 $\{b_m\}$ ，问 $\{a_n\}$ 有多少个连续子序列满足：存在一种方法...
[随机+主席树二分]BZOJ5361(Lydsy1805月赛)【对称数】题解
题目概述给出一棵 $n$ 个节点的树，每个节点有权值，一条路径上的对称数定义为最小的出现次数为偶数（包括 $0$ ）的数，现在给出 $m$ 个询问 $(x,y)$ 表示询问 $(x,y)...
[线段树动态开点]BZOJ5358(Lydsy1805月赛)【口算训练】题解
题目概述给你 $\{a_n\}$ ，给出 $m$ 个询问 $l,r,d$ 表示询问 $a_l\times a_{l+1}\times\cdots\times a_r$ 是不是 $d$ 的倍数。解...
