线段树、树状数组、倍增、分治（朴素分治 / CDQ / 整体二分）、平衡树、字典树、笛卡尔树
多乎哉？不多也。
题目来源：
- llsw’s pdf
- 洛谷文章广场题解区搜索对应算法
- 自己以前的一些零散题解
找了一些有数据结构方面思维难点的题，实现难度通常不会很大，也有少许粑粑夹杂其中
# 是缺题解，* 是缺代码
线段树
维护特殊信息
金鱼草（区间覆盖信息）
http://222.180.160.110:61235/contest/6051/problem/4
给定 \(n\) 个区间 \([l,r]\)，给出 \(q\) 个询问，每次询问 \([L,R]\) 是否能被表示为若干 \([l,r]\) 的并集。注意不能覆盖到 \([L,R]\) 之外的点。
\(n,q\le 5\times 10^5,|V|\le 10^9\)。
- 题目所求等价于 check 满足 \(l\ge L\land r\le R\) 的所有区间是否能够覆盖 \([L,R]\)
- 这个很简单，需要区间修改的做法就不提了。可以想一下有没有只需要单点修改的做法
发现权值线段树可以维护「一段连续左端点对应区间的并」是否是连续的：
维护位于区间内的左端点最后一个覆盖到的点 \(rv\)（可以在区间外；发现从区间左端点到 \(rv\) 会被连续覆盖），区间内最后一个没有被覆盖到的点 \(p\)，和表示区间是否能被完整覆盖的标记 \(flag\)。pushup 是容易的。容易发现如果我们在树上询问 \([L,R]\) 中所有左端点的 \(flag\)，无法保证参与覆盖的 \(r\le R\)。故离线下来扫描线即可。
实际上由于未知原因跑得很可能不如区间修改的方法快 TAT
#include <bits/stdc++.h>
const int maxn = 5e5 + 5;
struct _ {
bool flag;
int l, r, rv, p;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].rv = std::max(t[lt].rv, t[rt].rv);
if (!t[lt].flag) {
t[p].flag = 0;
if (!t[rt].flag && t[lt].rv < t[rt].p)
t[p].p = t[rt].p;
else
t[p].p = t[lt].p;
}
else if (!t[rt].flag && t[lt].rv < t[rt].p)
t[p].flag = 0, t[p].p = t[rt].p;
else
t[p].flag = 1, t[p].p = 0;
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = t[p].p = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void add(int p, int x, int v) {
if(t[p].l == t[p].r) {
t[p].flag = 1, t[p].p = 0;
t[p].rv = std::max(t[p].rv, v);
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
add(lt, x, v);
else
add(rt, x, v);
pushup(p);
return;
}
_ ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p];
int mid = (t[p].l + t[p].r) >> 1;
if (r <= mid)
return ask(lt, l, r);
if (l > mid)
return ask(rt, l, r);
auto ls(ask(lt, l, r)), rs(ask(rt, l, r));
if (!ls.flag) {
if (!rs.flag && ls.rv < rs.p)
ls.p = rs.p;
}
else if (!rs.flag && ls.rv < rs.p)
ls.flag = 0, ls.p = rs.p;
ls.rv = std::max(ls.rv, rs.rv);
return ls;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("snapdragon.in", "r", stdin);
std::freopen("snapdragon.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m, q;
std::cin >> m >> n >> q;
bld(1, 1, m);
std::vector<std::vector<int> > t(m + 1);
for (int i = 1, l, r; i <= n; ++i) {
std::cin >> l >> r;
t[r].push_back(l);
}
std::vector<int> res(q + 1);
std::vector<std::vector<std::pair<int, int> > > tq(m + 1);
for (int i = 1, l, r; i <= q; ++i) {
std::cin >> l >> r;
tq[r].emplace_back(l, i);
}
for (int i = 1; i <= m; ++i) {
for (auto l : t[i])
add(1, l, i);
for (auto [l, id] : tq[i])
res[id] = ask(1, l, i).flag;
}
for (int i = 1; i <= q; ++i)
std::cout << (res[i] ? "YES" : "NO") << '\n';
return 0;
}# 题日 Zapatak（哈希）
https://www.luogu.com.cn/problem/P11262
简单数据结构（带一点递推性质）
https://pjudge.ac/problem/21636
给定初始为空的多重集 \(p\), \(q\)，这两个多重集中的元素都有 \(a,b\) 两种属性。需要需要维护 \(p\) 和 \(q\) 的加点和删点操作，询问 \(\forall \,i\in p,j\in q\)，\(\max(i_x + j_x, i_y + j_y)\) 的最小值。
\(m\le 10^6,V\le 10^9\)。
- 考虑对不等式恒等变形，转化为偏序问题。若 \(a_{i,0}+b_{j,0}\ge a_{i,1}+b_{j,1}\)，则 \(a_{i,0}-a_{i,1}\ge b_{j,1}-b_{j,0}\)。
把 \(a\) 按照 \(a_{i,0}-a_{i,1}\) 排序、把 \(b\) 按照 \(b_{j,1}-b_{j,0}\) 排序。
要求某个时刻的答案，需要对于每一个 \(i\) 找到最小的 \(b_{j,0}\)，使得 \(b_{j,1}-b_{j,0}\) 在 \([-\infty, a_{i,0}-a_{i,1}]\) 中，同时找到最小的 \(b_{j,1}\)，使得 \(b_{j,1}-b_{j,0}\) 在 \([a_{i, 0}-a_{i,1},+\infty]\) 中。
这个带有一点递推的性质，在线段树 pushup 的时候，用左边的 \(b_{j,0}\) 结合右边的答案得到父亲的答案。
听说我之前赛时切了这题？怎么没印象。llsw 讲题的时候说要离线，但是没想到离线做法 orz
#include <bits/stdc++.h>
const int inf = 2e9 + 1;
struct _ { long long aa, ab, ba, bb, u; int l, r, id; };
std::vector<_> t(1);
std::vector<std::multiset<long long> > aa(1), ab(1), ba(1), bb(1);
int tot, cnt;
#define lt t[p].l
#define rt t[p].r
void pushup(int p) {
t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
if (lt) {
t[p].u = t[lt].u;
t[p].aa = t[lt].aa, t[p].ab = t[lt].ab, t[p].ba = t[lt].ba, t[p].bb = t[lt].bb;
}
if (rt) {
t[p].u = std::min(t[p].u, t[rt].u);
t[p].aa = std::min(t[p].aa, t[rt].aa);
t[p].ab = std::min(t[p].ab, t[rt].ab);
t[p].ba = std::min(t[p].ba, t[rt].ba);
t[p].bb = std::min(t[p].bb, t[rt].bb);
}
if (lt && rt)
t[p].u = std::min({ t[p].u, t[lt].ba + t[rt].aa, t[lt].ab + t[rt].bb });
return;
}
int adda(int p, long long l, long long r, int x, int a, int b) {
if (!p)
p = ++tot, t.emplace_back(), t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
if (l == r) {
if (!t[p].id)
t[p].id = ++cnt, aa.emplace_back(), ab.emplace_back(), ba.emplace_back(), bb.emplace_back();
int id = t[p].id;
aa[id].insert(a), ab[id].insert(b);
t[p].aa = *aa[id].begin(), t[p].ab = *ab[id].begin();
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return p;
}
long long mid = (l + r) >> 1;
if (x <= mid) {
auto s(adda(lt, l, mid, x, a, b));
lt = s;
}
else {
auto s(adda(rt, mid + 1, r, x, a, b));
rt = s;
}
pushup(p);
return p;
}
int addb(int p, long long l, long long r, int x, int a, int b) {
if (!p)
p = ++tot, t.emplace_back(), t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
if (l == r) {
if (!t[p].id)
t[p].id = ++cnt, aa.emplace_back(), ab.emplace_back(), ba.emplace_back(), bb.emplace_back();
int id = t[p].id;
ba[id].insert(a), bb[id].insert(b);
t[p].ba = *ba[id].begin(), t[p].bb = *bb[id].begin();
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return p;
}
long long mid = (l + r) >> 1;
if (x <= mid) {
auto s(addb(lt, l, mid, x, a, b));
lt = s;
}
else {
auto s(addb(rt, mid + 1, r, x, a, b));
rt = s;
}
pushup(p);
return p;
}
void dela(int p, long long l, long long r, int x, int a, int b) {
if (l == r) {
int id = t[p].id;
aa[id].erase(aa[id].find(a)), ab[id].erase(ab[id].find(b));
t[p].aa = (aa[id].empty() ? inf : *aa[id].begin());
t[p].ab = (ab[id].empty() ? inf : *ab[id].begin());
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return;
}
long long mid = (l + r) >> 1;
if (x <= mid)
dela(lt, l, mid, x, a, b);
else
dela(rt, mid + 1, r, x, a, b);
pushup(p);
return;
}
void delb(int p, long long l, long long r, int x, int a, int b) {
if (l == r) {
int id = t[p].id;
ba[id].erase(ba[id].find(a)), bb[id].erase(bb[id].find(b));
t[p].ba = (ba[id].empty() ? inf : *ba[id].begin());
t[p].bb = (bb[id].empty() ? inf : *bb[id].begin());
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return;
}
long long mid = (l + r) >> 1;
if (x <= mid)
delb(lt, l, mid, x, a, b);
else
delb(rt, mid + 1, r, x, a, b);
pushup(p);
return;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("set.in", "r", stdin);
std::freopen("set.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int q, rt = 0;
std::cin >> q;
for (int i = 1; i <= q; ++i) {
int op, d, a, b;
std::cin >> op >> d >> a >> b;
if (op == 0 && d == 0)
dela(rt, -inf, inf, a - b, a, b);
else if (op == 0)
delb(rt, -inf, inf, b - a, a, b);
else if (d == 0)
rt = adda(rt, -inf, inf, a - b, a, b);
else
rt = addb(rt, -inf, inf, b - a, a, b);
std::cout << (t[1].u == inf ? -1 : t[1].u) << '\n';
}
return 0;
}# 命运（利用线段树的分治结构递推）
https://www.luogu.com.cn/problem/P6773
* 对数据结构的爱（维护函数）
https://www.luogu.com.cn/problem/P5609
给定长度为 \(n\) 的数组 \(a\) 和模数 \(p\)（\(a_i\) 初始可能比 \(p\) 大很多，还有可能为负），给定 \(m\) 次询问，每次问区间 \([l,r]\)，进行这样的操作：
初始 \(sum=0\)，从 \(l\) 到 \(r\)，依次令 \(sum\gets sum+a_i\)，当且仅当 \(sum\ge p\) 时令 \(sum\gets sum-p\)（注意这不是取模，减完之后还是可能 \(\ge p\)）。
问最终 \(sum\) 的值。\(n\le 10^6,m\le 2\times 10^5\)。
考虑线段树维护函数。定义 \(f(x)\) 表示区间上想要减去 \(x\) 次 \(p\) 需要的最小初始值（这样才能让定义域和区间长有关），查询时直接二分即可；考虑初始化时如何合并。
首先思考较为暴力的做法，对于左侧点 \(a\) 和右侧点 \(b\)，若 \(f(a+1)-1+s_l-a\cdot p\ge f(b)\)，也即可以减去 \(a+b\) 次，就可以用 \(\max(f(a),f(b)-s_l+a\cdot p)\) 来更新 \(f(a+b)\)。
发现 \((a,b)\) 的贡献一定小于 \((a+1,b-1)\) 的贡献；具体地，发现 \(f(x+1)-f(x)\ge p\) 后就很显然了。采用双指针，优先移动 \(b\)，就能把最短区间扫一遍。
关于线段树维护函数
维护一个函数，形如 \(f_{[l,r]}(x)\) 表示在 \([l,r]\) 区间上，\(x\) 的一个映射
如果相邻区间的函数可以用某种方式合并，就可以用线段树来维护
把树建在值域上，就可以在节点内把这段区间每个点对应的函数值存下来。一般来说是静态的，因为这是一个类前缀和的形式，没办法修改
每个点的点值数组会在当前层被扫一遍，上一层被扫一遍，如果合并能够做到线性，总复杂度就是单 \(\log\) 的。
实际情形下函数本身可能很隐秘、很抽象，怎么优化到线性合并也不太好想
* COmPoUNdS（模意义下问题）
https://www.luogu.com.cn/problem/P12389
给定常数模数，维护模意义下的区间加、区间哈希。\(n\le 10^6\)。
线段树哈希是可以维护区间加的，但是没办法维护区间取模
类似 ABC419E 里面用到的，模意义下序列全等可以转化成差分全等，区间修改就可以简化成单点修改了
额外判一下开头的元素（维护原数组或者是差分数组之和）是否相等就可以了
* 改进代码（模意义下问题）
https://www.luogu.com.cn/problem/P4635
给定序列 \(a_{1\sim n}\) 和常数 \(p\)，维护:
- 修改：模 \(p\) 意义下区间加；
- 询问：区间中 \(\sum\limits_{i=l}^{r-1}[a_i>a_{i+1}]\)。
\(n\le 10^5,p\le 10^6\)。
询问也和模意义差分有关系，假如 \(s\) 为当前差分数组前缀和模 \(p\) 的值（也就是原数），发现前一个数 \(>\) 后一个数当且仅当 \(s\) 加爆了。维护原数组用来确定 \(s\) 的初值。再维护区间内差分数组之和（不取模），在这个和里有多少个 \(p\) 就会爆多少次。
黑白树（很新的东西）
http://222.180.160.110:61235/problem/46907
以楼房重建为代表的 \(\log^2\) 一类前缀信息维护
特点：pushup 时需要先获得一边的信息，在另一边进行线段树上二分，单次操作是 \(O(\log^2)\) 的
本质是一类具有单调性的前 / 后缀信息，区间对全局的贡献和区间外的信息有关，故不能直接维护对全局的贡献，只能维护区间内的答案。但由于两个子区间答案可以合并出大区间答案（通过线段树上二分得到需要的信息），所以只需要逐层向上合并就可以得到全局答案
一个名字是『线段树维护前缀信息』，感觉不很精确。log 方线段树又是什么鬼名字？更多还是叫的楼房重建线段树吧
楼房重建
https://www.luogu.com.cn/problem/P4198
给定 \(a_{1\sim n}\)，维护 \(q\) 次操作：
- 单点修改；
- 查询 \(\dfrac{a_i}i\) 的前缀最大值序列长度。
\(n,q\le 10^5\)。
Fractures 说当年（初一）是他力荐 gm 给我们拉这个题的。dashena！
- 线段树维护单调栈，或者说前缀最值，维护方式过于经典，使得『楼房重建』成为该 trick 称呼之一
考虑 pushup。保留左边整段区间，对于左区间序列末的元素
反证法易得 \(x\) 一定在右区间答案序列内：若 \(x\) 不在答案序列内，则右区间内存在一个 \(>x\) 且位于 \(x\) 之前的元素，那么 \(x\) 就不是第一个l.rv，我们在右区间内找到第一个大于之的元素 \(x\)，从它开始的序列就是答案。> l.rv的元素，矛盾。故在右区间中二分能够接上去的区间长度，加起来即可。
题目只要求总区间答案，故不需要查询。动态开点可能需要小心处理一下。
#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
struct {
int l, r, u;
double lv, rv, mv;
} t[maxn << 2];
int tot;
#define lt t[p].l
#define rt t[p].r
int askt(int p, int l, int r, double v) {
if (l == r)
return t[p].u;
int mid = (l + r) >> 1;
if (lt && t[p].mv > v)
return t[p].u - t[lt].u + askt(lt, l, mid, v);
return askt(rt, mid + 1, r, v);
}
void pushup(int p, int l, int r) {
t[p].mv = t[lt].rv;
if (lt && rt) {
t[p].lv = t[lt].lv;
t[p].rv = std::max(t[lt].rv, t[rt].rv);
if (t[lt].rv < t[rt].lv)
t[p].u = t[lt].u + t[rt].u;
else if (t[lt].rv >= t[rt].rv)
t[p].u = t[lt].u;
else {
int mid = (l + r) >> 1;
t[p].u = t[lt].u + askt(rt, mid + 1, r, t[lt].rv);
}
}
else {
t[p].u = t[lt + rt].u;
t[p].lv = t[lt + rt].lv, t[p].rv = t[lt + rt].rv;
}
return;
}
void upd(int &p, int l, int r, int x, double v) {
if (!p)
p = ++tot;
if (l == r) {
t[p].lv = t[p].rv = v, t[p].u = 1;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
upd(lt, l, mid, x, v);
else
upd(rt, mid + 1, r, x, v);
pushup(p, l, r);
return;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("P4198_2.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m, rt = 0;
std::cin >> n >> m;
std::vector<double> a(n + 1);
for (int x; m--; ) {
double y;
std::cin >> x >> y;
a[x] = y / x;
upd(rt, 1, n, x, y / x);
std::cout << t[1].u << '\n';
}
return 0;
}二叉搜索树
https://pjudge.ac/problem/21889
给定一个大小为 \(n\) 的树，树上每个元素是一个 BST，你需要维护 \(q\) 次操作：
- 对于树上的一条路径 \((u,v)\)，在经过的所有节点上的 BST 插入 \(x\)，保证任意时刻 BST 中无相同值
- 在点 \(u\) 查找 \(x\)，如果 \(x\) 存在则返回其到 BST 根的元素和，否则返回查找时最远走到的那个点，到 BST 根的元素和。
\(n,q\le 2\times 10^5\)。
- 考虑链上问题。差分，把更新 \([l, r]\) 看作在差分数组 \(l\) 处插入，在 \(r+1\) 处删除，离线下来再从左到右扫一遍操作就能更新。
- 考虑查询。\(i\) 树上存在过的所有元素是已知的，考虑如何基于此获取 \(i\) 树上 \(t_0\) 时刻，\(x\) 的所有祖先。
对于比 \(x\) 大的元素，考虑祖先 \(p_a\) 和非祖先 \(p\) 的区别：
根据 BST 的性质易得，对于最低的右侧祖先 \({p_a}_0\)，其是 \(\ge x\) 的最小的元素（加入时刻 \(t_a<t_0\)）；
同理可以找到 \({p_a}_0\) 右侧最低的祖先（其左侧的祖先显然也在 \(x\) 左侧），该祖先满足 \(t<t_a\)。从左右两边分别得到 \(x\) 的所有祖先。容易证明该过程对于不在树上的 \(x\) 也是正确的。- 具体地，需要能够求出 \(\ge x\) 的元素中，以 \(t_0\) 为起点的前缀最小值序列的区间和。线段树维护单调栈容易解决不带 \(t_0\) 限制的答案；再次利用性质就能满足限制。
对于树的情况，把差分放到树上，线段树合并即可。
#include <bits/stdc++.h>
const int lim = 2e5;
const int maxn = 2e7 + 5;
const int inf = 0x3f3f3f3f;
struct {
int l, r, rv;
long long u;
} t[maxn];
std::vector<int> tr;
#define lt t[p].l
#define rt t[p].r
int newnode(void) {
static int tot = 0;
if (tr.empty())
return ++tot;
auto p(tr.back());
t[p].l = t[p].r = 0;
tr.pop_back();
return p;
}
long long askv(int p, int l, int r, int v) {
if (l == r)
return t[p].rv < v ? t[p].u : 0;
int mid = (l + r) >> 1;
if (v > t[lt].rv)
return t[p].u - t[lt].u + askv(lt, l, mid, v);
return askv(rt, mid + 1, r, v);
}
void pushup(int p, int l, int r) {
t[p].rv = std::min(t[lt].rv, t[rt].rv);
int mid = (l + r) >> 1;
t[p].u = t[lt].u + askv(rt, mid + 1, r, t[lt].rv);
return;
}
void upd(int &p, int l, int r, int x, int v, int u) {
if (!p)
p = newnode();
if (l == r) {
t[p].rv = v, t[p].u = u;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
upd(lt, l, mid, x, v, u);
else
upd(rt, mid + 1, r, x, v, u);
pushup(p, l, r);
return;
}
void merge(int &p, int q, int l, int r) {
if (!p || !q) {
p += q;
return;
}
if (l == r) {
t[p].rv = std::min(t[p].rv, t[q].rv);
t[p].u = std::max(t[p].u, t[q].u);
return;
}
int mid = (l + r) >> 1;
merge(t[p].l, t[q].l, l, mid), merge(t[p].r, t[q].r, mid + 1, r);
pushup(p, l, r), tr.push_back(q);
return;
}
int qv = inf;
long long ask(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
auto s(askv(p, l, r, qv));
qv = std::min(qv, t[p].rv);
return s;
}
int mid = (l + r) >> 1;
long long res = 0ll;
if (ql <= mid)
res = ask(lt, l, mid, ql, qr);
if (qr > mid)
res += ask(rt, mid + 1, r, ql, qr);
return res;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("ex_problem4.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> top(n + 1), fa(n + 1), siz(n + 1), son(n + 1), dep(n + 1);
std::function<void(int, int)> DFS = [&](int x, int faa) {
siz[x] = 1;
for (auto i : g[x])
if (i != faa) {
fa[i] = x, dep[i] = dep[x] + 1;
DFS(i, x), siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
};
DFS(1, -1);
DFS = [&](int x, int topp) {
top[x] = topp;
if (son[x])
DFS(son[x], topp);
for (auto i : g[x])
if (i != fa[x] && i != son[x])
DFS(i, i);
return;
};
DFS(1, 1);
auto getLCA = [&](int x, int y) {
for (; top[x] != top[y]; x = fa[top[x]])
if (dep[top[y]] > dep[top[x]])
std::swap(x, y);
return (dep[x] < dep[y] ? x : y);
};
std::vector<std::vector<int> > d(n + 1);
std::vector<std::vector<std::pair<int, int> > > u(n + 1);
std::vector<std::vector<std::tuple<int, int, int> > > q(n + 1);
int cnt = 0;
for (int i = 1; i <= m; ++i) {
int op;
std::cin >> op;
if (op == 0) {
int x, v;
std::cin >> x >> v;
q[x].emplace_back(++cnt, i, v);
} else {
int x, y, v;
std::cin >> x >> y >> v;
int faa = getLCA(x, y);
u[x].emplace_back(i, v), u[y].emplace_back(i, v);
if (fa[faa])
d[fa[faa]].emplace_back(v);
}
}
std::vector<long long> res(cnt + 1);
std::vector<std::vector<int> > rt(2, std::vector<int> (n + 1));
t[0].rv = inf;
DFS = [&](int x, int fa) {
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
merge(rt[0][x], rt[0][i], 1, lim);
merge(rt[1][x], rt[1][i], 1, lim);
}
for (auto [t, v] : u[x]) {
upd(rt[0][x], 1, lim, v, t, v);
upd(rt[1][x], 1, lim, lim - v + 1, t, v);
}
for (auto v : d[x]) {
upd(rt[0][x], 1, lim, v, inf, 0);
upd(rt[1][x], 1, lim, lim - v + 1, inf, 0);
}
for (auto [id, t, v] : q[x]) {
qv = t, res[id] = ask(rt[0][x], 1, lim, v, lim);
qv = t, res[id] += ask(rt[1][x], 1, lim, lim - v + 1, lim);
qv = t, res[id] -= ask(rt[0][x], 1, lim, v, v);
}
};
DFS(1, -1);
for (int i = 1; i <= cnt; ++i)
std::cout << res[i] << '\n';
return 0;
}Nastya and CBS
https://www.luogu.com.cn/problem/CF1340F
给定长度为 \(n\) 的括号序列，由 \(k\) 种括号对（\(-i,i\) 表示第 \(i\) 种左、右括号）组成，你需要维护单点修改元素、区间查询是否为合法括号序列。
\(1\le k\le n\le 10^5,q\le 10^5\)。
- 考虑不带修且允许 \(O(n)\) 询问的情景，经典题，扫一遍，用栈维护即可；
\(k=1\) 时是线段树经典题，可以类比这个经典题，从刻画合法的条件入手。
如果存在相邻且可以匹配的可以直接消掉，一直重复这样的操作，此时要么包含不能匹配的子串，如{[)}，要么是)]} ({[{{的形式。- 考虑怎么 pushup，发现中间生成的一段
([()])必须完全匹配，消掉它们之后，大区间又变成)]} ({[{{的形式。 - 每次 pushup 要合并的区间很长，考虑怎么快速地做『消除相邻匹配括号』这一步。容易想到记录一段括号（例：
([{）及其对应反括号（例：}])）的哈希值，check 是否相等，然后就可以不管它们了，并不是真的要删去。 线段树不能维护每个前后缀的哈希值，但需要的只是在删除连续匹配括号后长度为 \(len\) 的哈希值，可以线段树上二分。
这个过程有点困难，需要在询问的同时匹配、消除；但发现所谓消除就是对位相减，注意一下什么时候移位，还是好写的。询问看似不太可做，因为中途的答案不是线段树的节点；如果把询问看成一次修改，就可以用类似可持久化的方式实现。
由于并不是真的要可持久化，询问新建的点可以重复利用。如果不重复利用，每次询问最多新建 \(O(\log n)\) 个点，空间复杂度 \(O(q\log n)\)，在 CF 上有点卡，也是能过的。
Hint：有卡 998244353 的 Hack，故可以用 1e9 + 7 当模数；WA on 7 是正确性有巨大问题，WA on 8 可能是 long long 没开完 / 数组开小了 / 哈希方向有问题 / 线段树上二分写挂了（通常是消括号消错了）。前人踩坑后人嘲笑。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
const int base = 1e5 + 3;
const int maxn = 7e5 + 5;
struct Node {
bool flag;
long long hr0, hl1;
int l, r, lc, rc, ll, rl;
Node& operator= (const Node &q) {
flag = q.flag, hr0 = q.hr0, hl1 = q.hl1;
l = q.l, r = q.r, ll = q.ll, rl = q.rl;
return *this;
}
Node operator+ (const Node &q) const;
} t[maxn << 2];
int tot;
int a[maxn];
long long bpow[maxn], inv[maxn];
long long askhl1(const Node &p, int k) {
if (k == 0)
return 0ll;
if (k > p.ll)
return -1ll;
if (p.ll == k)
return p.hl1;
int ll = t[p.lc].ll, rl = t[p.lc].rl;
if (ll >= k)
return askhl1(t[p.lc], k);
k -= ll, k += rl;
auto hl1 = askhl1(t[p.rc], k);
hl1 = ((hl1 + mod - t[p.lc].hr0) * inv[rl] % mod * bpow[ll] % mod + t[p.lc].hl1) % mod;
return hl1;
}
long long askhr0(const Node &p, int k) {
if (k == 0)
return 0ll;
if (k > p.rl)
return -1ll;
if (p.rl == k)
return p.hr0;
int rl = t[p.rc].rl, ll = t[p.rc].ll;
if (rl >= k)
return askhr0(t[p.rc], k);
k -= rl, k += ll;
auto hr0 = askhr0(t[p.lc], k);
hr0 = ((hr0 + mod - t[p.rc].hl1) * inv[ll] % mod * bpow[rl] % mod + t[p.rc].hr0) % mod;
return hr0;
}
Node Node::operator+ (const Node &q) const {
Node res;
res.l = l, res.r = q.r;
if (flag || q.flag)
res.flag = 1;
else {
if (rl == q.ll) {
if (hr0 == q.hl1) {
res.flag = 0;
res.ll = ll, res.rl = q.rl;
res.hl1 = hl1, res.hr0 = q.hr0;
}
else
res.flag = 1;
}
else if (rl < q.ll) {
auto qhl1 = askhl1(q, rl);
if (hr0 == qhl1) {
res.flag = 0;
res.ll = ll + q.ll - rl, res.rl = q.rl;
res.hl1 = ((q.hl1 + mod - qhl1) % mod * inv[rl] % mod * bpow[ll] % mod + hl1) % mod;
res.hr0 = q.hr0;
}
else
res.flag = 1;
}
else {
auto phr0 = askhr0(*this, q.ll);
if (phr0 == q.hl1) {
res.flag = 0;
res.ll = ll, res.rl = rl - q.ll + q.rl;
res.hl1 = hl1;
res.hr0 = ((hr0 + mod - phr0) % mod * inv[q.ll] % mod * bpow[q.rl] % mod + q.hr0) % mod;
}
else
res.flag = 1;
}
}
return res;
}
void bld(int &p, int l, int r) {
p = ++tot;
if (l == r) {
t[p].l = t[p].r = l;
if (a[l] < 0)
t[p].ll = 1, t[p].hl1 = -a[l];
else
t[p].rl = 1, t[p].hr0 = a[l];
return;
}
int mid = (l + r) >> 1;
bld(t[p].lc, l, mid), bld(t[p].rc, mid + 1, r);
t[p] = t[t[p].lc] + t[t[p].rc];
return;
}
void add(int p, int x, int v) {
if (t[p].l == t[p].r) {
if (v < 0) {
t[p].rl = 0, t[p].hr0 = 0ll;
t[p].ll = 1, t[p].hl1 = -v;
}
else {
t[p].ll = 0, t[p].hl1 = 0ll;
t[p].rl = 1, t[p].hr0 = v;
}
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
add(t[p].lc, x, v);
else
add(t[p].rc, x, v);
t[p] = t[t[p].lc] + t[t[p].rc];
return;
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return p;
int mid = (t[p].l + t[p].r) >> 1;
if (r <= mid)
return ask(t[p].lc, l, r);
if (l > mid)
return ask(t[p].rc, l, r);
int q = ++tot;
t[q].lc = ask(t[p].lc, l, r);
t[q].rc = ask(t[p].rc, l, r);
t[q] = t[t[q].lc] + t[t[q].rc];
return q;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k, rt = 0;
std::cin >> n >> k;
bpow[0] = inv[0] = 1ll;
auto qkp = [&](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[1] = qkp(base, mod - 2);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
bpow[i] = bpow[i - 1] * base % mod;
if (i >= 2)
inv[i] = inv[i - 1] * inv[1] % mod;
}
bld(rt, 1, n);
int q;
std::cin >> q;
for (int op; q--; ) {
std::cin >> op;
if (op == 1) {
int x, v;
std::cin >> x >> v;
add(1, x, v);
}
else {
int l, r;
std::cin >> l >> r;
if ((r - l + 1) & 1)
std::cout << "No" << '\n';
else {
auto s(ask(1, l, r));
std::cout << ((!t[s].flag && !t[s].ll && !t[s].rl) ? "Yes" : "No") << '\n';
}
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}# Hungry Cow P
https://www.luogu.com.cn/problem/P9130
# 牛半仙的妹子序列
http://222.180.160.110:61235/problem/29550
# Organizing a Race
https://www.luogu.com.cn/problem/CF671E
这个题不太应该放在这里的，因为存在只用一只 log 的纯线段树上二分做法，用楼房重建显得有点唐了
# 转盘
https://www.luogu.com.cn/problem/P4425
# 前进四（楼房重建 ver）
可持久化线段树
# Card Game
历史信息
# 比赛
https://www.luogu.com.cn/problem/P8868
# V
# Cartesian Tree
https://www.luogu.com.cn/problem/CF1290E
# rprmq1
https://www.luogu.com.cn/problem/P6109
# rpfrdtzls
https://www.luogu.com.cn/problem/P9057
# TEST_90
https://www.luogu.com.cn/problem/P9990
线段树合并
树上的线段树合并都很熟悉了，利用了线段树合并是线性的，以及 dsu on tree
不如说绝大多数线段树合并都有树上背景，因为自带合并顺序和复杂度保证
Tip：树上合并的背景下，线段树合并的表现会比主席树优秀很多，因为前者跑不满
不在树上的问题，题目可能会通过各种方式保证复杂度，比如保证每个点只会被合并一次之类
# 迁移计划 / Migration Plan
https://www.luogu.com.cn/problem/P11993
# 永无乡
https://www.luogu.com.cn/problem/P3224
# 语言
https://www.luogu.com.cn/problem/P5327
# 梦幻布丁
https://www.luogu.com.cn/problem/P3201
还有两个比较屎的 P7563 和 P7963
扫描线
离线，按照下标排序，扫一遍处理询问，就可以利用『所有更靠前的下标都以被计算过』来处理问题
不只局限于区间询问，单点的可能反而更难一点，需要发现和下标大小有关的性质
等差子序列
https://www.luogu.com.cn/problem/P2757
给定一个 \(n\) 的排列，问是否能找到 \(len\ge 3\) 的子序列，使得其是等差的。
\(n\le 5\times 10^5\)。
根据单调性，可以简化为 \(len=3\) 时的答案
也就是对于中项 \(j\)，能不能找到 \(i<j<k\)，使得 \(a_j-a_i=a_k-a_j\)。从下标出发，差值是不好维护的；注意到是排列，可以从值出发，转化成是否存在一个 \(d\)，使得 \(a_j-d\) 在之前出现，\(a_j+d\) 在之后出现。
利用下标『之前』和『之后』的限制，做扫描线，查看是否存在 \(d\) 使 \(a_j-d\) 出现过但是 \(a_j+d\) 没有出现过；还是因为是排列，数量只会为 \(0\) 或 \(1\)，如果非法说明 \(a_j-d\) 和 \(a_j+d\) 都是 \(0\) 或者都是 \(1\)，发现是关于 \(a_j\) 的回文，故权值线段树维护哈希，如果 \(a_j\) 两侧全部回文，说明 \(j\) 不是合法中项。
#include <bits/stdc++.h>
namespace fastIO {
const int LEN = (1 << 20);
#ifdef ONLINE_JUDGE
inline int nec(void) {
static char buf[LEN], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, LEN, stdin);
if (e == buf)
return EOF;
p = buf;
}
return *p++;
}
#else
#define nec getchar
#endif
inline bool read(int &x) {
x = 0;
bool f = 0;
char ch = nec();
while (ch < '0' || ch > '9') {
if (ch == EOF)
return 0;
if (ch == '-')
f = 1;
ch = nec();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = nec();
}
if (f)
x = -x;
return 1;
}
void print(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x >= 10)
print(x / 10);
putchar(x % 10 + '0');
return;
}
void print(int x, char ch) {
print(x);
putchar(ch);
return;
}
} // namespace fastIO
namespace XSC062 {
using namespace fastIO;
#define lt (p << 1)
#define rt (lt | 1)
using sc = unsigned long long;
const int p = 13331; // 0103 ¿É°®µÎÄó
const int lim = 5e5;
const int maxn = 5e5 + 5;
struct _ {
int l, r;
sc lh, rh;
};
int T, n;
int a[maxn];
sc base[maxn];
_ t[maxn << 2];
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
void pushup(int p) {
int ll = t[lt].r - t[lt].l + 1;
int rl = t[rt].r - t[rt].l + 1;
t[p].lh = t[lt].lh * base[rl] + t[rt].lh;
t[p].rh = t[rt].rh * base[ll] + t[lt].rh;
return;
}
void bld(int p, int l, int r) {
t[p].lh = t[p].rh = 0;
t[p].l = l, t[p].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid);
bld(rt, mid + 1, r);
return;
}
void upd(int p, int x, int v) {
if (t[p].l == t[p].r) {
t[p].lh = t[p].rh = v;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
upd(lt, x, v);
else upd(rt, x, v);
pushup(p);
return;
}
sc qryl(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].lh;
sc ans = 0;
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
ans = qryl(lt, l, r);
if (r > mid) {
ans *= base[min(r, t[p].r) - mid];
ans += qryl(rt, l, r);
}
return ans;
}
sc qryr(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].rh;
sc ans = 0;
int mid = (t[p].l + t[p].r) >> 1;
if (r > mid)
ans = qryr(rt, l, r);
if (l <= mid) {
ans *= base[mid - max(l, t[p].l) + 1];
ans += qryr(lt, l, r);
}
return ans;
}
int main() {
read(T);
base[0] = 1;
for (int i = 1; i <= lim; ++i)
base[i] = base[i - 1] * p;
while (T--) {
read(n);
bld(1, 1, n);
for (int i = 1; i <= n; ++i)
read(a[i]);
for (int i = 1; i <= n; ++i) {
int len = min(n - a[i], a[i] - 1);
if (i > 1) {
upd(1, a[i - 1], 1);
}
if (len == 0)
continue;
int l = a[i] - len;
int r = a[i] + len;
if (qryl(1, l, a[i] - 1) !=
qryr(1, a[i] + 1, r)) {
puts("Y");
goto isSol;
}
}
puts("N");
isSol: ;
}
return 0;
}
} // namespace XSC062
int main() {
XSC062::main();
return 0;
}小奇的糖果
有 \(N\) 个有颜色（\(M\) 种）的点在平面上，在平面上取一条水平的线段，可以选择线段上方的所有点，也可以选择下方的所有点。找出一条线段和选取的方向，使得在选取的点不包含所有颜色的前提下，最大化选到点的数量。
\(N,M\le 10^6,|x|,|y|\le 10^9\)。
先离散化 + 按 \(y\) 排序降一维，贪心地枚举某种颜色 \(c\) 不选。考虑线段在平面最底部时的答案，取出所有颜色为 \(c\) 的点的 \(x\) 坐标，只能选择相邻的 \(x\) 之间的所有点。枚举每一对相邻的点计算答案。把线段上移，如果碰到了一个颜色为 \(c\) 的点，就说明这个点不再参与限制，删去即可，该点原前驱和后继围出来的区间就能够更新答案。用链表 / 单调栈就能很快地维护。
先枚举颜色再跑扫描线是 \(O(n^2\log n)\) 的，考虑优化。注意到数据结构里存在当前颜色没有影响，因为一定不在询问区间内。整体做扫描线，复杂度 \(O(n\log n)\)。
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e5 + 5;
struct _ {
int x, y, c;
bool operator< (const _ &q) const {
return y < q.y;
}
};
_ a[maxn];
int s[maxn], t[maxn];
int ls[maxn], rs[maxn];
int cp[maxn], cn[maxn];
int pre[maxn], nex[maxn];
std::vector<int> g[maxn];
int div[maxn], Bit[maxn];
int T, n, k, tot, cnt, now, res;
int max(int x, int y) { return x > y ? x : y; }
int lowbit(int x) { return x & -x; }
void add(int x, int v) {
for (; x <= n; x += lowbit(x)) Bit[x] += v;
return;
}
int ask(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += Bit[x];
return res;
}
int ask(int l, int r) {
if (l > r) return 0;
return ask(r) - ask(l - 1);
}
int main() {
// freopen("1.in", "r", stdin);
read(T);
while (T--) {
read(n), read(k), now = res = 0;
for (int i = 1; i <= k; ++i) {
s[i] = ++now, t[i] = ++now;
div[s[i]] = 0, div[t[i]] = n + 1;
nex[s[i]] = t[i], pre[t[i]] = s[i];
pre[s[i]] = nex[t[i]] = 0;
}
for (int i = 1; i <= n; ++i) {
read(a[i].x), read(a[i].y), read(a[i].c);
ls[i] = a[i].x, rs[i] = a[i].y;
}
std::sort(a + 1, a + n + 1, [&](_ x, _ y) { return x.x < y.x; });
std::sort(ls + 1, ls + n + 1);
std::sort(rs + 1, rs + n + 1);
tot = std::unique(ls + 1, ls + n + 1) - ls - 1;
cnt = std::unique(rs + 1, rs + n + 1) - rs - 1;
for (int i = 1; i <= n; ++i) {
a[i].x = std::lower_bound(ls + 1, ls + tot + 1, a[i].x) - ls;
a[i].y = std::lower_bound(rs + 1, rs + cnt + 1, a[i].y) - rs;
}
for (int i = 1; i <= n; ++i) {
div[++now] = a[i].x;
add(a[i].x, 1), g[a[i].y].push_back(now);
pre[now] = pre[t[a[i].c]], nex[pre[t[a[i].c]]] = now;
pre[t[a[i].c]] = now, nex[now] = t[a[i].c];
}
memcpy(cp, pre, sizeof (cp));
memcpy(cn, nex, sizeof (cn));
for (int i = 1; i <= k; ++i) {
for (int j = s[i]; j != t[i]; j = nex[j])
res = max(res, ask(div[j] + 1, div[nex[j]] - 1));
}
for (int i = 1; i <= n; ++i) {
for (auto j : g[i]) add(div[j], -1);
for (auto j : g[i]) {
res = max(res, ask(div[pre[j]] + 1, div[nex[j]] - 1));
nex[pre[j]] = nex[j], pre[nex[j]] = pre[j];
}
}
for (int i = 1; i <= n; ++i) add(a[i].x, 1);
for (int i = n; i; --i) {
for (auto j : g[i]) add(div[j], -1);
for (auto j : g[i]) {
res = max(res, ask(div[cp[j]] + 1, div[cn[j]] - 1));
cn[cp[j]] = cn[j], cp[cn[j]] = cp[j];
}
}
print(res, '\n');
for (int i = 1; i <= n; ++i)
g[i].clear(), g[i].shrink_to_fit();
}
return 0;
}
} // namespace XSC062rmscne
https://www.luogu.com.cn/problem/P7907
给定长为 \(n\) 的序列，\(q\) 次询问 \([l,r]\) 中的最短子区间 \([l',r']\)，使得其包含 \([l,r]\) 中出现的全部值。输出长度即可。
\(n,q,V\le 2\times 10^6\)。
区间里面找子区间也是扫描线经典问题。
区间种类数会有几种思路：集合哈希、前驱后继、莫队之类。PS：这个题用 ODT 可以拿到最优解
对于 \(i=1\sim n\)，依次考虑 \(i\) 作为右端点的情况。线段树维护每个 \(j\) 作为左端点时的 \(i-r_j\)，其中 \([j, r_j]\) 是与 \([j,i]\) 种类相同的最小区间。
询问的时候，只需要找到最大的 \(j'\)，满足 \([j, r]\) 与 \([l, r]\) 种类相同，求 \([l, j']\) 的区间和即可。找 \(j'\) 可以记录前驱后继，初始每个 \(l\) 对应的 \(j'\) 就是自己。若加入了一个与 \(l\) 相同的新元素，那么 \(l\) 就不再有贡献，此时 \(l\) 的 \(j'\) 就会继承 \(l+1\) 的 \(j'\)，这个过程用并查集即可简单维护。
#include <bits/stdc++.h>
const int lim = 2e6;
const int maxn = 2e6 + 5;
const int maxm = 5e7 + 5;
const int inf = 0x3f3f3f3f;
struct { int l, r, u, d; } t[maxn << 2];
int tot;
#define lt (p << 1)
#define rt (lt | 1)
void pushdown(int p) {
if (~t[p].d) {
t[lt].d = t[rt].d = t[p].d;
t[lt].u = t[p].d - t[lt].r + 1;
t[rt].u = t[p].d - t[rt].r + 1;
t[p].d = -1;
}
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].d = -1;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void upd(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d = v, t[p].u = v - t[p].r + 1;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
upd(lt, l, r, v);
if (r > mid)
upd(rt, l, r, v);
t[p].u = std::min(t[lt].u, t[rt].u);
return;
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].u;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1, res = inf;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res = std::min(res, ask(rt, l, r));
return res;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, q;
std::cin >> n;
std::vector<int> a(n + 1), la(lim + 1), pre(n + 1), f(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
pre[i] = la[a[i]], la[a[i]] = i, f[i] = i;
}
std::cin >> q;
std::vector<int> res(q + 1);
std::vector<std::vector<std::pair<int, int> > > t(n + 1);
for (int i = 1, l, r; i <= q; ++i) {
std::cin >> l >> r;
t[r].emplace_back(l, i);
}
bld(1, 1, n);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
auto merge = [&](int x, int y) {
x = find(x), y = find(y);
f[std::min(x, y)] = std::max(x, y);
return;
};
for (int r = 1; r <= n; ++r) {
if (pre[r])
merge(pre[r], pre[r] + 1);
upd(1, pre[r] + 1, r, r);
for (auto [l, i] : t[r])
res[i] = ask(1, l, find(l));
}
for (int i = 1; i <= q; ++i)
std::cout << res[i] << '\n';
return 0;
}# 颜色
https://www.luogu.com.cn/problem/P4065
给定 \(n\) 个元素，每个元素有一个颜色。选择若干颜色（不能全选或全不选），问有多少种选取方案使得拥有这些颜色的点是一段连续的区间。
\(n\le 3\times 10^5\)。
势能线段树
# 市场
# Segment Tree Beats!
维护区间取 min，区间求和。
pdf P57
# Segment Tree Beats! Plus
维护区间加，区间取 min，区间求和。
pdf P60
# 最假女选手
# Mzl loves segment tree
http://222.180.160.110:61235/problem/10203
pdf P66
# CTSN loves segment tree
https://www.luogu.com.cn/problem/U180387
# 前进四（segment tree beats ver）
另见 楼房重建 ver
# 基础数据结构练习题
# 线段树 3
https://www.luogu.com.cn/problem/P6242
# 赛格蒙特彼茨
pdf P70
# 堕天作战 TEST_98
https://www.luogu.com.cn/problem/P9069
线段树分治
# 八纵八横
https://www.luogu.com.cn/problem/P3733
笛卡尔树
一些思考方式和 trick 吧
* 由乃救爷爷
https://www.luogu.com.cn/problem/P3793
尽可能快地维护随机序列区间最值。
随机序列笛卡尔树期望深度是 \(\log\)。就可以做了。
来自 UnyieldingTrilobite 的文章：同样可以用悬线！悬线 + 分块 就可以做了。
* 情景剧（最值的性质，维护方式的取舍）
http://222.180.160.110:61235/contest/4273/problem/1
给定长度为 \(n\) 的序列 \(a_{1\sim n}\)，找到一个区间，使得 区间长度 \(\times\) 区间最大值 \(\times\) 区间最小值 最大。输出最大值。
\(n\le 10^6,V\le 10^9\)。
- 容易想到建笛卡尔树。这里的 最大值 和 最小值 地位相等吗？为什么？
- 如果我们是钦定最大值，再去最大化『最小值 \(\times\) 区间长』，好像没办法做，因为这个最大贡献没什么性质
但如果钦定最小值，能取到的最长区间就是在小根笛卡尔树上的管辖区间，显然区间越长取到的最大值也越大，直接取这里的最大值即可
所以最大值和最小值地位不等是因为，区间长和最大值大小是正相关的，所以只需要最大化区间长，最大值也就最大化了所以在小根笛卡尔树上维护区间最大值即可
# 小蓝的好友
https://www.luogu.com.cn/problem/P2611
星白 by TTpandaS（笛卡尔树 + dsu on tree）
http://222.180.160.110:61235/contest/6517/problem/3
给定 \(n\) 的排列 \(a_{1\sim n}\)，回答 \(q\) 个询问：
给定 \([l,r]\)，是否存在 \(l\le x<y\le r\)，使得：
- \(a_x<a_y\)，且 \(a_x\) 不为 \([x,y]\) 中最小值；
- 令 \(a_i\) 为 \([x, y]\) 中最小值，则 \(a_i\mid (a_x\cdot a_y)\)。
\(n\le 3\times 10^5,q\le10^6\)。
- 容易想到对于 \(i\) 反过来找 \([x,y]\)。如果建立小根笛卡尔树，在 \(i\) 的左边找 \(x\)、右边找 \(y\)。
一个自然的想法是对于左侧的每个 \(x\)，维护最近的合法 \(y\)；或是对于右侧的每个 \(y\)，维护最近的合法 \(x\)。
做一个 DSU on Tree，哪边区间短就维护哪边，是单 \(\log\) 的。需要解决点内预处理，以 \(x\) 为例，对于每个 \(x\) 和当前点 \((p,l,r)\)，需要查询 \((p, r]\) 中最小的 \(y\)，使得 \(a_y\) 是 \(\dfrac {a_p}{\gcd(a_x,a_p)}\) 的倍数。离线下来扫描线，
不是很理解为什么题目要再加一个偏序限制，除了增加代码量和用时外似乎并没有什么作用？开 \(n\) 棵线段树，跑 \(n\) 次树状数组，用 \(y\) 更新所有 \(a_y\) 因数在 \(a_y\) 处的 min / max，可以在两个 log 内获得支配对类似物。查询时直接 rmq（这里唐了写了 st 表，实际上只需要前后缀）即可。整体复杂度 \(O(n\log^2 n)\)。
#include <bits/stdc++.h>
const int LEN = (1 << 20);
#ifdef ONLINE_JUDGE
int nec(void) {
static char buf[LEN], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, LEN, stdin);
if (e == buf) return EOF;
p = buf;
}
return *p++;
}
#else
#define nec getchar
#endif
bool read(int &x) {
x = 0;
bool f = 0;
char ch = nec();
while (ch < '0' || ch > '9') {
if (ch == EOF) return 0;
if (ch == '-') f = 1;
ch = nec();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = nec();
}
if (f) x = -x;
return 1;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
read(n);
std::vector<std::vector<int> > mul(n + 1);
std::vector<int> a(n + 1), l(n + 1), r(n + 1), pos(n + 1);
for (int i = 1; i <= n; ++i) {
read(a[i]), pos[a[i]] = i;
for (l[i] = i; l[i] != 1 && a[i] < a[l[i] - 1]; l[i] = l[l[i] - 1]);
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += i)
mul[i].push_back(pos[j]);
std::sort(mul[i].begin(), mul[i].end());
}
for (int i = n; i; --i)
for (r[i] = i; r[i] != n && a[i] < a[r[i] + 1]; r[i] = r[r[i] + 1]);
struct query { int id, l, r; };
std::vector<std::vector<query> > ql(n + 1), qr(n + 1);
for (int i = 1; i <= n; ++i)
if (i - l[i] < r[i] - i)
for (int j = l[i]; j < i; ++j)
qr[a[i] / std::__gcd(a[i], a[j])].push_back({ j, i + 1, r[i] });
else
for (int j = i + 1; j <= r[i]; ++j)
ql[a[i] / std::__gcd(a[i], a[j])].push_back({ j, l[i], i - 1 });
std::vector<int> u(n + 1), rt(n + 1), bit(n + 1);
auto lowbit = [](int x) {
return x & -x;
};
auto add = [&](int x, int v) {
for (; x <= n; x += lowbit(x))
bit[x] = v;
return;
};
std::function<int(int)> ask = [&](int x) {
int res = 0;
for (; x; x -= lowbit(x))
res = std::max(res, bit[x]);
return res;
};
for (int fac = 1; fac <= n; ++fac) {
std::sort(ql[fac].begin(), ql[fac].end(), [&](query x, query y) { return x.r < y.r; });
auto i = mul[fac].begin();
for (auto [id, l, r] : ql[fac]) {
for (; i != mul[fac].end() && *i <= r; ++i)
add(a[*i], *i);
auto mx(ask(a[id]));
if (mx >= l)
u[id] = std::max(u[id], mx);
}
for (auto i : mul[fac])
add(a[i], 0);
}
bit.assign(n + 1, 0x3f3f3f3f);
ask = [&](int x) {
int res = 0x3f3f3f3f;
for (; x; x -= lowbit(x))
res = std::min(res, bit[x]);
return res;
};
for (int fac = 1; fac <= n; ++fac) {
std::sort(qr[fac].begin(), qr[fac].end(), [&](query x, query y) { return x.l > y.l; });
std::reverse(mul[fac].begin(), mul[fac].end());
auto i = mul[fac].begin();
for (auto [id, l, r] : qr[fac]) {
for (; i != mul[fac].end() && *i >= l; ++i)
add(n - a[*i] + 1, *i);
auto mn(ask(n - a[id] + 1));
if (mn <= r)
u[mn] = std::max(u[mn], id);
}
for (auto i : mul[fac])
add(n - a[i] + 1, 0x3f3f3f3f);
}
std::vector<std::vector<int> > st(20, std::vector<int> (n + 1));
for (int i = 1; i <= n; ++i) {
// if (u[i] != 0)
// printf("%d %d\n", u[i], i);
st[0][i] = u[i];
}
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[j][i] = std::max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
auto askmx = [&](int l, int r) {
int k = std::__lg(r - l + 1);
return std::max(st[k][l], st[k][r - (1 << k) + 1]);
};
int q;
read(q);
for (int l, r; q--; ) {
read(l), read(r);
std::cout << (askmx(l, r) >= l ? "Yes" : "No") << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}# PERIODNI
https://www.luogu.com.cn/problem/P6453
CDQ 分治
# Coloring Nodes（偏序很隐秘）
https://www.luogu.com.cn/problem/P12423
字典树
字典树作为 log 数据结构的时候，等价权值线段树，而且支持合并、分裂（权值线段树 also OK，强调一下而已）
有些情景 Trie 写起来会比权值线段树舒服一些，比如值域操作、二进制操作之类
# 异或粽子
https://www.luogu.com.cn/problem/P5283