关注嘉然喵，关注嘉然谢谢喵。

线段树基础

CF671E

知识点：楼房重建类线段树

我们首先考虑转化一下，这个问题就是 n 点 n-1 边，边负权点正权。先考虑原始问题，如何判断一个 [l,r] 是符合条件的？

可以写出这个区间的贡献：g_l - w_l +g_{l+1}\dots +g_r 也就是所有前缀和后缀和 \geq 0。

接着考虑加 k 的想法，我们能让一个不合法区间变成合法的，首先可以用折线图表示：

image-20220806084510299

想让前缀和 \geq 0 那么就是所有点都在 0 这条横线的上方。后缀和也就是翻转过来同样考虑。这样我们就刻画出来了两条横线，所有点都需要在两条线之间。

我们考虑贪心，扫到第一个前缀和小于 0 的位置，对其 +1，含义就是把后面所有点都抬高。但是我们不能放太前面，我们只对于某个 \leq 0 的位置前面的一个 g 进行加直到下一个位置变成 0。这样我们就能满足前缀条件。对于后缀条件，我们考虑把 g_r 的位置变成最高的位置减去它的位置，合法性就是这两部分的和 \leq k.

接下来我们就考虑从小到大扫描线，我们枚举一个 l ，然后求 r 的最大值。

  • 对于前缀来说：我们用一个 b 记录最大值，我们影响的是后缀代价，也就是 r 在这个位置及以后的 a_i 需要加上 c。后缀 b_i 的值加上 c。
  • 对于后缀来说：代价为 \max\limits_{l \leq r} (b_l) - b_r

所以我们可以上线段树！对于第一步我们直接维护，第二步我们不直接维护，设第一个的后缀代价为 a，那么就是要求

a_r +\max\limits_{l \leq r} (b_l) - b_r \leq k

里面 r 的最大值。

我们发现 a,b 是同时加的，所以我们对于上面那个式子实际上是不用管的，所以我们只需要做两个事情。

  1. 对于 b 区间加
  2. 查询 \max\limits_{r \geq l}(b_l) - premax_r \leq k 中 r 最大值

下面这个问题就是楼房重建类线段树了。

具体来说，我们考虑一个线段树，对于一个区间节点是 [l,r,t] ，其中 t 表示前缀最大值。那么我们对于上面的东西我们需要考虑快速查询 premax_r，如果 \max(t,b_l,\dots,b_{mid}) \leq k 我们就直接找一个右子树就行。

那么还有一种情况是大于，那么就不可以预处理了，但是发现左子树里这个前缀和肯定都 =t ，所以我们只要查询一个左子树的 \max，所以可以证明每种情况都只会去一个子树。整个过程是一个线段树二分的过程。

对于修改操作，我们的时间复杂度是 \mathcal O (\log^2 n) 的。

「JOISC 2019 Day3」穿越时空 Bitaro

考虑怎么用线段树来维护这个信息，我们可以把所有的开放区间全部减去 i，就直接把时间轴这一维给抹掉了。

image-20220806092342831

如果要经过边 i，我们就需要出发时间在 [l_i,r_i] 里。只考虑从左往右走，现在这个问题就是我们可以往右走往下走，让往下走的总距离和最小。

我我们注意到，在一个位置多等一会显然不如少等一会，感性理解就是现在回溯不如以后回溯。

现在就有一个 qn 的做法，我们每次贪心维护一串。维护两个函数，分别对应进入时间和出去时间以及代价，考虑几种情况。

  1. 所有区间的交非空，设交为 [l,r] ，我们就直接暴力让当前时间满足条件就行。

  2. 所有区间的交为空，发现我们出去的时候位置是基本固定的，那么我们总可以认为穿过这段区间的效果是：初始时刻 a ，到达时刻 b ，必须使用 k 次技能。

    这是因为我们可以在过区间的时候，将穿过后的一些技能平移到穿过前，这样我们的初始时刻就是相同的；同样也可以将穿过前的平移到穿过后，这样到达时刻就是相同的。

我们把第一类记为 A 点，第二类记为 B 点。B 点我们维护一个三元组 (a,b,k) 含义同上，然后我们就维护一下 A 点 B 点合并就行。

CF1693E

/shui

我们从大往小考虑，对于一个 i 考虑有多少书一次操作后变成 i，答案就是 \sum a_i。这个的意思是如果一个数 \geq i 那么一定会变成 i 的。我们前后缀考虑，如果把 j 取前缀，我们会变成 k，否则取后缀会变成 i.

segbeats

介绍

Segment Tree Beats 学习笔记 - Neal_lee - 博客园 (cnblogs.com)

支持两种操作：

  1. 区间 check min
  2. 区间加

我们考虑记录区间中最大值，严格次大值，最大值个数，和。

考虑check min的 c：

  1. c \geq max 无事发生。
  2. secmax\leq c \leq max 所有 max 变成 c，sum += (c - mx) * num
  3. c \leq secmax 递归两子树，pushup

考虑对复杂度进行势能分析！带区间修改是 log^2 ，不带是 \log 的

void update(int x, int l, int r, int L, int R, int val){
    if(t[x].mx <= val) return;
    if(l >= L && r <= R && t[x].smx < val){ addtag(x, val); return; }
    int mid = (l+r)>>1;
    pushdown(x);
    if(mid >= L) update(x*2, l, mid, L, R, val);
    if(mid < R) update(x*2+1, mid+1, r, L, R, val);
    pushup(x);
}

例题 CF1290E

对于每个子树的大小，我们考虑为 i 左侧第一个大于 ai 的位置 - i 左侧第一个大于 ai 的位置 - 1

那么分开来算，我们以第一个为例，第二个是对称的。

从 1-i 来算

线段树分裂

支持三种操作：

  1. 区间正序排列
  2. 区间倒序排列
  3. 区间和

用 treap 维护所有连续段，再用权值线段树维护所有连续段的值

我们每次做区间修改的时候，每次用线段树分裂把当前块分成小块，对于大部块merge。

莫队

“大家都会！”

扫描线

B 维正交范围

在一个 B 维直角坐标系下，第 i 维坐标在一个整数范围 [l_i,r_i] 范围内。

A-side

理解为前缀。

一维扫描线

用扫描线扫一维，用 DS 维护另一维。

扫过去的过程中会 DS 维护的那一维上产生一些修改和查询。

查询信息可以差分就直接差分（二维数点），否则就需要分治了。

另一个角度就是序列角度，一维扫过去枚举右端点，DS 维护的是左端点答案。个人比较喜欢下面这种表达。

一般来说，能差分的题就尽量差分，问题第一维实际上是降低了自由度，让问题简单了很多!典型的差分方法：

  • [l,r] 差分为 [1,r] - [1,l-1]，两个前缀和
  • 树上差分
  • 二维前缀和差分

BZOJ3489

image-20220807084535101

这个是一类问题的反演，反演的问题类型：

  1. 平面上 n 个点，m 次询问矩形内有多少点。
  2. 平面上 n 个矩形，m 次询问每个点上有多少矩形。

对于这个题就是考虑每个点对哪些区间有贡献，那么就是算每个值对每个区间的贡献。我们称本题询问的这种值称为色数。

我们要维护的实际上是一个 4-side 的矩形。

TEST_73

image-20220807085549763

考虑点连通块就是 点 - 边 的个数。我们考虑边数，边数需要满足三个条件：两个端点，边的编号都在 [l,r] 之间。

我们反演一下问题，计算每条边对答案的贡献，得到一个三维问题。发现我们只需要 \min\{a,b,c\},\max\{a,b,c\} 这样就只需要做二维数点了！

这题启发是要好好研究问题，否则会造成问题的升维。

BZOJ4212

image-20220807090057889

考虑建 trie，前缀就是 trie 上对应的子树，后缀就是反着建同理。

这个同时的约束，我们把问题拓展到二维，实际上就是查询有多少 x 满足在第一个子树里，又在第二个子树里。

子树问题我们可以直接上 DFS 序，就变成一个二维数点了。

UOJ637

这类关于颜色数的问题，我们都考虑利用不同值对答案贡献独立的性质。

对每个元素，我们计算一下它对哪些询问有贡献，然后用DS维护。

我们考虑这个询问被哪些元素不包含。

CometOJ contest14D

image-20220807101418558

还是构造二维平面，一维是操作位置，一维是原来序列的位置。

假设区间对 [l,r] 进行染色，那么贡献是 3-side 的。

image-20220807102536520

区间子区间问题

待补

CF526F

转化后题意：给排列，求有多少区间满足 \max\limits_{l\leq i\leq r}{a_i} - \min\limits_{l\leq i\leq r}{a_i} = r - l

还是想能不能转化成矩形，

掉线了，学弟说可以析合树！

CF997E

我们把 l,r 分别当成 x,y 轴，那么子区间就是转换为查询一个矩形内有多少点满足某条件，是一个三角部分。

可以看作是一个2-side矩形。

文章目录