标签 树状数组 下的文章
- 首页
- 树状数组
洛谷2414 [NOI2011]阿狸的打字机
Luogu分析做完这题感觉对 AC 自动机有了新的理解...注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀（这里建议想一想 fail 的定义），因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。然而...
ARC101F Robots and Exits
AtCoder分析神仙题...我们先把所有只有只会从一个出口出去的机器人删掉，这些机器人不影响答案。对于剩下的机器人，记它到左边第一个出口的距离为 $a$ ，到右边第一个出口的距离为 $b$ 。那么每个机器人可以看成一个点 $(a,b)$ 。设 $x$ 为所有机器人往左移动的最远点到初始位置的...
ARC101D Median of Medians
AtCoder分析令 $cnt=n(n+1)/2$ ，也就是生成的序列的项数。二分答案 $x$ 。如果最后的答案是 $x$ ，那么就有 $\frac{cnt}{2}+1$ 项的中位数不大于 $x$ 。考虑求出有多少项的中位数 $>x$ 。令 $<x$ 的数为 $-1$ ，$\geq...
CF293E Close Vertices
CodeForcesLuogu分析比较简单的点分治。可是我调了好久先考虑一个简单版的题目：Tree。那道题统计答案是用的双指针。但是这道题多了一个 $L$ 的限制，所以在双指针满足 $W$ 的限制的同时，再用一个树状数组来满足 $L$ 的限制就行了。具体实现及细节见代码。代码// ======...
洛谷5302 [GXOI/GZOI2019]特技飞行
LuoguBZOJLOJ分析首先考虑怎么求出所有交点。注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ 。那么可以用 $\mathrm{set}$ 来维护 $y_{x,1}$ ，然后暴力求出所有交点。因为交点...
洛谷3312 [SDOI2014]数表
LuoguBZOJ分析先假装没看到那个 $a$ 的限制。设 $\mathbf{f}=\sigma$，$\mathbf{g}=\mathbf{f}*\mu$ 。预处理出 $\mathbf{g}$ ，然后数论分块计算即可。然而有 $a$ 的限制，所以忽略上面的那句话。发现，只有 $\sigma(d...
洛谷3755 [CQOI2017]老C的任务
LuoguBZOJ分析发现这题和 $\mathrm{Mokia}$ 差不多，把初始值看成单点加，查询拆成四个，然后就可以 $\mathrm{CDQ}$ 分治了。不同的是要把 $y$ 坐标离散化一下。具体实现及细节见代码。分析//It is made by M_sea #include <...
洛谷4064 [JXOI2017]加法
LuoguBZOJ分析第一眼想到二分答案。 然后我就不会了首先以 $l$ 为第一关键字、$r$ 为第二关键字将所有区间排序。假设现在二分出了一个答案 $mid$ 。贪心地想，我们只会在不得不给一个区间加上 $a$ 时给它加上 $a$ 。于是从左到右扫，如果一个点没有达到 $mid$ 的话，那么...
洛谷3250 [HNOI2016]网络
LuoguBZOJ分析整体二分。对于每个询问，查询经过它的路径，然后对应地丢到左边或右边。对于每个修改，判断它的权值是否大于 $mid$ ，如果是就修改并丢到右边，否则丢到左边。可以用树状数组来维护子树权值和，每次用树上差分的方式来修改。具体实现和细节见代码。代码//It is made by...
洛谷3722 [HNOI2017]影魔
LuoguBZOJ分析对所有询问离线处理。首先用单调栈处理出每个点左右最近的比它大的数，分别记为 $L_i$ 和 $R_i$。显然 $[L_i,R_i]$ 有 $p_1$ 的贡献；左端点在 $[L_i+1,i-1]$ 之间，右端点在 $R_i$ 的区间有 $p_2$ 的贡献；左端点在 $L_i...