[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解
题目概述给定一个字符串 $S$ ，要求构造字符串序列 $s_1, s_2, \ldots, s_k$ ，满足任意 $s_i$ 都是 $S$ 的子串，且任意 $i \in$ $[2, n]$ ，都...
[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解
题目概述一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的点且只能取 $T$ 次。一个点不能...
[Manacher+离线+线段树]2015计蒜之道初赛第三场【商品推荐走马灯】题解
题目概述给出一个序列，一个回文区间的权值是区间权值和，问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞，然后我自带大常数TLE了……只需...
[BFS序+线段树]HDU5957【Query on a graph】题解
题目概述给一棵基环树，有两种操作：1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值和。解题报告emm……DFS序做多了都忘...
[线段树+复杂度分析]Codeforces793F【Julia the snail】题解
题目概述有 $n$ 个点和 $m$ 个传送点 $(l,r)$ 表示可以从 $l$ 传送到 $r$ ，只能往下爬或者传送。问从 $x$ 出发在不超过 $y$ 且不低于 $x$ 的前提下能够达到的最...
[单调栈+线段树]Codeforces407E【k-d-sequence】题解
题目概述有 $n$ 个数，求最长的子区间使得添加 $K$ 个数，排序之后得到一个公差为 $D$ 的等差数列。解题报告我太斯波了，式子都没仔细看就写了个二分，显然不满足单调性……一个区间 $[L,...
[线段树+复杂度分析]HDU5634【Rikka with Phi】题解
题目概述有一个序列 $\{a_n\}$ ，现在有三种操作：1.令 $i\in[L,R],a_i=\varphi(a_i)$ 。2.令 $i\in[L,R],a_i=x$ 。3.询问区间和。解题报...
[离线+霍尔定理+线段树]BZOJ2138【stone】题解
题目概述有 $n$ 堆石子，每堆 $a_i$ 个，现在要取 $m$ 次，第 $i$ 次在 $[L_i,R_i]$ 中取 $K_i$ 个（不够 $K_i$ 就取完）。问在前 $i-1$ 次取到的最...
[two-pointer+线段树]BZOJ4653(Noi2016)【区间】题解
题目概述有 $n$ 个区间，求取 $m$ 个区间使得交不为空时的最小 $max\{len\}-min\{len\}$ 。解题报告我不会做题啦……很显然区间越多交越小而且解也不会优，所以可以按照长...
[树链剖分+线段树]Codeforces1023F【Mobile Phone Network】题解
题目概述有 $n$ 个点，$K$ 条特殊边，边权待定，保证无环，还有 $m$ 条普通带权边，现在确定特殊边的边权，使得最小生成树（边权相同选特殊边）包含所有特殊边。求上述条件成立的情况下最大边权...
