洛谷5070 [Ynoi2015]即便看不到未来
Luogu 分析 把询问离线，从左往右加入每个数并维护以这个数为右端点时每个左端点的答案。 假设当前加入了 $x$，那么它显然不会更新 $a_x$ 上一次出现位置之前的左端点的答案（因为这些区间排序去重后根本没有变化），而且只会和 $[x-11,x+11]$ 的数产生贡献（因为只需要统计 $\leq 10$ 的长度）。而插入 $x$ 后极长值域连续段可能会有以下变化 从 $[a,x-1]$...
标签 树状数组 下的文章
- 首页
- 树状数组
洛谷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
Codeforces Luogu 分析 考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。 将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。 代码 // =================================== /...
CF749E Inversions After Shuffle
Codeforces Luogu 分析 考虑一个点对 $(i,j)\;(i<j)$ 的贡献。 分两种情况考虑：$i,j$ 都在连续段内、$i,j$ 不都在连续段内。 先考虑第一种情况。显然连续段的左端点 $\in[1,i]$，右端点 $\in[j,n]$，于是随机出的连续段包含 $i,j$ 的概率为 那么对于每个 $i$，我们只要知道满足 $j>i,a_j<a_i$ 的...
洛谷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)$ 变成 $(x...
洛谷5302 [GXOI/GZOI2019]特技飞行
Luogu LOJ 分析 首先考虑怎么求出所有交点。 注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ 。 那么可以用 set 来维护 $y_{x,1}$ ，然后暴力求出所有交点。 因为交点个数 $\leq 500000$ ，所以可以过。 容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立的。 先考虑怎...