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$ 的数量...
标签 树状数组 下的文章
- 首页
- 树状数组
ARC068E Snuke Line
AtCoderLuogu分析先考虑对于每个 $d\in[1,m]$ 如何单独算答案。可以发现，对于 $r_i-l_i+1\geq 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$ 的前缀...
ARC101F Robots and Exits
AtCoder分析神仙题...我们先把所有只有只会从一个出口出去的机器人删掉，这些机器人不影响答案。对于剩下的机器人，记它到左边第一个出口的距离为 $a$ ，到右边第一个出口的距离为 $b$ 。那么每个机器人可以看成一个点 $(a,b)$ 。设 $x$ 为所有机器人往左移动的最远点到初始位置的距离， $y$ 为所有机器人往右移动的最远点到初始位置的距离。那么每次相当于把 $(x,y)$ 变成...
ARC101D Median of Medians
AtCoder分析令 $cnt=n(n+1)/2$ ，也就是生成的序列的项数。二分答案 $x$ 。如果最后的答案是 $x$ ，那么就有 $\frac{cnt}{2}+1$ 项的中位数不大于 $x$ 。考虑求出有多少项的中位数 $>x$ 。令 $<x$ 的数为 $-1$ ，$\geq x$ 的数为 $1$ 。那么一段区间的中位数 $>x$ 就相当于这段区间的和 $\geq 0...
CF293E Close Vertices
CodeForcesLuogu分析比较简单的点分治。可是我调了好久先考虑一个简单版的题目：Tree。那道题统计答案是用的双指针。但是这道题多了一个 $L$ 的限制，所以在双指针满足 $W$ 的限制的同时，再用一个树状数组来满足 $L$ 的限制就行了。具体实现及细节见代码。代码// ================================= // author: M_sea // ...
洛谷5302 [GXOI/GZOI2019]特技飞行
LuoguBZOJLOJ分析首先考虑怎么求出所有交点。注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ 。那么可以用 $\mathrm{set}$ 来维护 $y_{x,1}$ ，然后暴力求出所有交点。因为交点个数 $\leq 500000$ ，所以可以过。容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立...