洛谷5070 [Ynoi2015]即便看不到未来
Luogu分析把询问离线，从左往右加入每个数并维护以这个数为右端点时每个左端点的答案。假设当前加入了 $x$，那么它显然不会更新 $a_x$ 上一次出现位置之前的左端点的答案（因为这些区间排序去重后根本没有变化），而且只会和 $[x-11,x+11]$ 的数产生贡献（因为只需要统计 $\leq 10$ 的长度）。而插入 $x$ 后极长值域连续段可能会有以下变化从 $[a,x-1]$ 变成了 ...
标签 树状数组 下的文章
- 首页
- 树状数组
洛谷6619 [省选联考 2020 A/B 卷] 冰火战士
LuoguLOJ分析看完题后可以发现几个结论：冰人能选的是一段前缀，火人能选的是一段后缀。总能量为能选的冰人的能量和和能选的火人的能量和中较小的那个的两倍。总能量是关于温度的单峰函数。答案一定是某个战士的温度。因为答案一定是某个战士的温度，所以先把所有温度离散化（下文的温度也指离散化后的温度）。看到这个单峰可以想到三分温度，但是由于有很多地方的值是相同的所以不太好三分；但是注意到冰人的能量和...
洛谷3934 [Ynoi2016]炸脖龙I
Luogu分析这种题显然要用扩展欧拉定理先考虑没有修改的情况，我们只需要像其它扩展欧拉定理题一样递归下去即可。显然只会递归 $\mathcal{O}(\log p)$ 层，所以复杂度是对的。现在考虑这个修改。我们实际上只需要知道每个位置的值，因此用树状数组实现区间修改、单点查询即可。$\varphi(p)$ 的值显然不能在递归时 $\mathcal{O}(\sqrt{p})$ 求，但是 $p...
洛谷3760 [TJOI2017]异或和
Luogu分析容易想到拆位。则我们需要计算有多少对 $(i,j)$ 满足 $s_j-s_{i-1}$ 的第 $k$ 位是 $1$。那么有两种情况：如果 $s_j$ 的 $0\sim k-1$ 位小于等于 $s_{i-1}$ 的 $0\sim k-1$ 位，则 $s_j$ 和 $s_{i-1}$ 的第 $k$ 位不同时满足条件。否则，$s_j$ 和 $s_{i-1}$ 的第 $k$ 位相同时满...
LOJ2729 「JOISC 2016 Day 1」俄罗斯套娃
LOJ分析我们把每个套娃看做一个点 $(R_i,H_i)$，把套在一起的若干个套娃看做一条链，把每条链 $H$ 最大的那个套娃称作这条链的头。这样子问题就变为，每个点可以向右上方某一个点连边，求最小链数。先考虑只有一组询问的情况。我们把所有物品按 $H$ 从小到大排序，然后依次加入。对于每个物品，显然选择能选择的最右的链头连上最优。于是我们只需要找到左边第一个链头即可。考虑处理询问。可以将链...
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$ 的数量...