CF547E Mike and Friends
CodeforcesLuogu分析考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。代码// =================================== // au...
标签 树状数组 下的文章
- 首页
- 树状数组
洛谷6089 [JSOI2015]非诚勿扰
Luogu分析先考虑怎么求 $s$ 个候选人中选中了第 $x$ 个的概率。考虑本题怎么做。可以发现要求的是一个类似于逆序对的东西，因此直接树状数组即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =====================...
BZOJ5036 [Jsoi2014]回文串
BZOJ分析首先在每两个字符中插入 texttt{#}，然后跑 Manacher。记 Manacher 求出的数组为 $f$。考虑每个询问。我们首先扩展到插入 texttt{#} 后的串，即令 $l\leftarrow 2\times l-1$，$r\leftarrow 2\times r+1$。设新串中的答案为 $ans'$，则原答案为 $\frac{ans'-(r-l+2)}{2}$，意...
BZOJ5173 [Jsoi2014]矩形并
BZOJ分析考虑对于每个矩形，求出其它矩形与它的交的面积之和。我们把其它矩形都加上 $1$，然后统计该矩形内的和即可。进一步可以得到这样一个做法：首先把所有矩形都加上 $1$，然后对于每个矩形统计它内部的和，减去它的面积即为所求。最后加起来除以 $n(n-1)$ 即为答案。那么问题就在于怎么支持矩形加、矩形求和了。有一个在线的做法是二维树状数组，但空间无法承受。因此可以考虑离线，用扫描线替代...
CF749E Inversions After Shuffle
CodeforcesLuogu分析考虑一个点对 $(i,j)\;(i<j)$ 的贡献。分两种情况考虑：$i,j$ 都在连续段内、$i,j$ 不都在连续段内。先考虑第一种情况。显然连续段的左端点 $\in[1,i]$，右端点 $\in[j,n]$，于是随机出的连续段包含 $i,j$ 的概率为那么对于每个 $i$，我们只要知道满足 $j>i,a_j<a_i$ 的 $j$ 的数量...
ARC068C Snuke Line
AtCoderLuogu分析考虑某种商品 $i$。如果 $r_i-l_i+1\geq d$，那么这种商品一定能够被买到。如果 $r_i-l_i+1<d$，那么这种商品只会被买到一次。将所有商品按 $r_i-l_i+1$ 从小到大排序，从小到大枚举 $d$，对于所有 $r_i-l_i+1<d$ 的商品都将 $[l_i,r_i]$ 加上 $1$，然后枚举 $d$ 的倍数统计即可得到第...
CF1234E Special Permutations
CodeforcesLuogu分析首先把 $pos(p_k(n),x)$ 写成一个比较好看的形式考虑 $x_i$ 和 $x_{i+1}$ 这两个数对所有 $f(p_k(n))$ 值的贡献。根据初中数学套路，我们需要分类讨论：若 $x_i=x_{i+1}$，此时贡献全部为 $0$。若 $x_i\neq x_{i+1}$，我们令 $a=\min\left\{x_i,x_{i+1}\right\}...
洛谷3460 [POI2007]TET-Tetris Attack
Luogu分析设第 $i$ 个数的两个出现位置为 $a_i,b_i$。可以发现，若 $(a_i,b_i)$ 中有 $x$ 个数还没有消去，那么要把 $i$ 消去的代价为 $x$。于是我们可以从前往后扫，如果当前的数是第一次出现就在这个位置 $+1$，否则将答案加上 $(a_i,b_i)$ 的区间和并把 $a_i-1$ 。用树状数组维护这个过程即可。输出方案在扫的过程中顺便搞一下就好了。代码/...
BZOJ4548 小奇的糖果
BZOJ分析只考虑选的点都在线段下方的情况，在线段上方的情况可以通过将纵坐标取反一样的做。首先考虑线段的纵坐标无限大的情况，显然线段的左右边界会卡在相邻的两个颜色相同的点之间。那么只需要将所有点按横坐标排序，维护一下上一个某种颜色的点，再用树状数组维护区间内点的个数即可。现在把线段向下移动，假设现在纵坐标刚好比某个点 $u$ 的纵坐标小 $1$，此时线段左右边界会卡在上一个和 $u$ 颜色相...
洛谷2414 [NOI2011]阿狸的打字机
Luogu分析做完这题感觉对 AC 自动机有了新的理解...注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀（这里建议想一想 fail 的定义），因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。然而现在要找的是子串而不是后缀。注意到所有前缀的所有后缀包含了所有子串，于是我们只需要把 $Y$ 的前缀...