[扫描线+线段树]LOJ6276【果树】题解
题目概述一棵 $n$ 个节点的树，每个节点有颜色，求路径上没有相同颜色的路径个数，每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑，模拟考的时候我疯狂想容斥，我都想到用正解做链了却没想到...
[线段树+复杂度分析]LOJ6507(雅礼集训 2018 Day7)【A】题解
题目概述区间与，区间或，区间最小值。解题报告完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度，如果 $[L,R]$ 与(或)上 $x$ ，那么 $x$ 为 $0(1)$ 的...
[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解
题目概述有一个串，现在要找出这个串的一个子串使得这个子串在原串出现了至少 $2$ 次，接着对这个子串继续操作直到无法操作为止。求最多操作多少次。解题报告Div.1好难啊……因为要求最大值，所以贪...
[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$ 次取到的最...