[ST表]Codeforces1011F【Mars rover】题解
题目概述给出一个逻辑运算树，每个节点有一个逻辑运算或输入框（ $0$ 或 $1$ ）以及 $0/1/2$ 个儿子（根据符号定）。问每次只把所有输入框中的一个改成相反的（ $0\to 1,1\to...
[DP+线段树维护矩阵转移]Codeforces573D【Bear and Cavalry】题解
题目概述给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ，有 $m$ 个询问，每次询问先交换 $P_x,P_y$ ，然后询问 $max\...
[莫比乌斯函数+调和级数]洛谷U32290【LJJ爱数数】题解
题目概述求 ${1\over a}+{1\over b}={1\over c}(a,b,c\in N^{*},a,b,c\le n)$ 解的个数。解题报告被学弟安利了这题（学弟秒掉了来嘲讽我）。...
[圆方树+树链剖分+线段树]Codeforces487E【Tourists】题解
题目概述给出 $n$ 个带权点和 $m$ 条无向边的图，给出 $q$ 个操作：1.修改某个节点的点权。2.询问 $x\to y$ 路径上所有简单路径的最小点权。解题报告简单路径就是一个点不能重复...
[莫队]HDU6333(2018多校练习赛第四场)【Harvest of Apples】题解
题目概述求 $\sum_{i=0}^{m}{n\choose m}$ ，多组询问 $(n,m)$ 。解题报告莫队大法好，由 $n\choose m$ 可以 $O(1)$ 得到 $n\choose...
[Tarjan求割点]BZOJ2730(HNOI2012)【矿场搭建】题解
题目概述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍...
[二分+后缀树+ST表]BZOJ5405【platform】题解
题目概述给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$，问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{[L,R]})=\sum_{i=L}^{...
[单调队列+单调栈]HDU6319(2018多校练习赛第三场)【Ascending Rating】题解
题目概述给出一个长度为 $n$ 的序列，求每个长度为 $m$ 的序列中的最大值以及最大值被更新的次数。解题报告最大值单调队列，更新次数可以这么搞：先预处理 $nxt[i]$ 表示 $i$ 后面第...
[哈希]BZOJ2795(Poi2012)【A Horrible Poem】题解
题目概述给出一个长度为 $n$ 的字符串和 $q$ 个询问，每个询问形如 $(l_i,r_i)$ 表示求 $s_{[l_i,r_i]}$ 的最短循环节的长度（最短循环节表示循环若干次之后和原串相...
[复杂度分析+线段树]HDU6315(2018多校练习赛第二场)【Naive Operations】题解
题目概述给出排列 $\{b_n\}$ 和刚开始都是 $0$ 的 $\{a_n\}$ ，有两种操作：1.把 $a_{[L,R]}$ 都 $+1$ 。2.询问 $\sum_{i=L}^{R}\lfl...
