标签 树状数组 下的文章
- 首页
- 树状数组
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分析感谢 $\mathrm{\color{black}{y}\color{red}{ch}}$ 的讲解qwq首先考虑怎么求出所有交点。注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ ...
洛谷3312 [SDOI2014]数表
LuoguBZOJ分析以下内容中默认 $n<m$ 。我们先假装没看到那个 $a$ 的限制。那么就是要求 $\large\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma\big(\gcd(i,j)\big)$ 。枚举 $\gcd$ ：$\large\...
洛谷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...
BZOJ4361 isn
BZOJ分析考虑一个长度为$i$的非子序列对答案的贡献是什么。可以发现是$i\times (n-i)!$。但是这样子会有一些非法情况：在删掉一个数之前序列已经是非降的了。设$g[i]$表示长度为$i$的非降子序列的个数。考虑长度为$i$的不下降子序列对答案的贡献。显然，如果先构成了一个长度为$...
洛谷4303 [AHOI2006]基因匹配
LuoguBZOJ分析有点神仙qwq注意到“每个数正好出现5次”，这说明每个数的转移点不超过5个。把转移点搞出来，每个数对应的转移点按倒序重排，就变成了一个长度为$25n$的序列。然后求这个序列的最长上升子序列就行了，可以使用树状数组来优化。代码//It is made by M_sea #i...