这是一篇披着PJ组数据结构外衣的树套树教程。

大约会（尝试着）较为本质地简介一下树状数组？

cdq分治也是咕了好久了..最近总算把它学了。

cdq分治是一种离线算法，可以代替一些复杂的数据结构，降低代码难度，减小常数。废话大家都知道。

题目链接

洛谷

darkbzoj

题意简述

带通配符的单模式串、单文本串匹配。

字符串长度 $3\times10^5$。

时隔半年又来到了YALI。

题目链接

洛谷

darkbzoj

题意简述

给你两个长为 $n$ 、无重复元素的数列 $a,b$，求将 $b$ 重排后 $\left(\sum\limits_{i=1}^n[a_i>b_i]\right)-\left(\sum\limits_{i=1}^n[a_i<b_i]\right)=k$（$k$ 给定）的方案数。

$n\le2000$。

题目链接

darkbzoj

题意简述

给你一个数列，求重排后每个位置都变了的方案数。

数列长度和值域都是 $2000$。

题目链接

洛谷

darkbzoj

题意简述

给你一棵树，每个节点有 $h$ 值，一个勇士来到一个节点时如果他的战斗力大于等于 $h$ 就能占领城池并前往这个节点的父亲（除非已经到了根节点），否则阵亡；攻占一个节点后，勇士的战斗力会加/减/乘一个正整数（根据节点而定）；每个勇士有初始战斗力和想占领的第一个节点。问，每个节点各有多少个勇士阵亡，每个勇士各占领了几个节点。

题目链接

洛谷

CF problemset

CF contest

题意简述

给你一个字符串 $s$ 和 $n$ 个字符串 $x_{1..n}$，对每个 $x_i$，求有多少个 $s$ 的子串可以由 $x_i$ 旋转得到。

旋转一个字符串就是把它的一个前缀移到后面，如 abcd 可以旋转得到的字符串有 abcd，bcda，cdab，dabc。

后缀自动机是一种处理字符串问题的有力工具（废话），它的码量不比后缀数组大（实际代码难度不比后缀数组小，但也不难），处理问题时的思维难度往往比后缀数组小，复杂度更优秀。若字符集大小为 $|\Sigma|$，则：构建时间复杂度 $O(n|\Sigma|)$，转移时间复杂度 $O(1)$，空间复杂度 $O(n|\Sigma|)$ 或 构建时间复杂度 $O(n\log|\Sigma|)$，转移时间复杂度 $O(\log|\Sigma|)$，空间复杂度 $O(n)$。

题目链接

洛谷

题意简述

求 出现次数不为 $1$ 的子串的 出现次数 $\times$ 长度 的最大值。