前言
算法竞赛题目考察的是选手对于数据结构的选取与算法的巧妙结合，而数据结构中线段树扮演一个至关重要的角色，而近期（CSP 结束）在 hfu 的安排下我们需要自己弄一周的 ds，所以就有了这篇奇妙的博客。
线段树基础知识
在我看来，线段树其实就是在数组的基础上添加了一些额外的点，这些点用于维护原数组的信息，在此基础上又添加一些点维护之前添加的点的信息，就这么一层一层往上直到最后只有一个点，而这个点也就管理了这整个数组。而这些点之间的管理关系也就形成了一棵树，故为线段树。
然后考虑添加的这些点，如果这些点很随意，最劣情况可能会被卡成一些神秘的东西，于是我们就让第一层维护两个点，第二层维护四个点，这样我们只会建出 \(\log\) 层，并且增加的节点数是 \(O(n)\) 的。这样线段树就有了很优美的性质，也称得上真正的线段树了。
对于用线段树维护信息，我们不必在每次修改操作将相关的节点全部修改，但是我们需要知道我们应该去修改哪些地方。比如我在树上走，走到了一个区间 \([l,r]\)，如果这个区间被修改的区间包含，这就意味着我需要将这整个区间修改，可是直接修改是 \(O(len)\) 的，这时我们就可以先将这个地方的修改记下来，等到我查询这个区间的时候在处理它。这样在线段树上找出的区间是 \(O(\log)\) 的，所以正常的修改就是找区间加上 \(O(1)\) 打标记。
而查询和修改同理，都是在树上走每次碰到一个区间能够被全部算进贡献就直接加入贡献，否则就继续往下走，但是在修改和查询时都需要注意下放之前的标记，也就是我下一次走到有标记的节点时我会对其进行一些操作，这时原来的标记与现在的操作的两个区间大概率是不同的，所以在操作前我们需要下放之前的标记。
然后放两道板子。
我们可以将线段树给建出，过程就是一个遍历树的过程，只是到树叶（也就是原数组）时需要保存信息再一层一层传回去。修改与查询在此不再赘述。
void upd(int x){
s[x] = s[ls] + s[rs];
}
void bld(int x, int l, int r){
if(l == r)return (void)(s[x] = a[l]);
int mid = l + r >> 1;
bld(ls, l, mid), bld(rs, mid + 1, r);
upd(x);
}
void pd(int x, int l, int r){
if(! tg[x])return; int mid = l + r >> 1;
tg[ls] += tg[x], tg[rs] += tg[x];
s[ls] += tg[x] * (mid - l + 1);
s[rs] += tg[x] * (r - mid);
return (void)(tg[x] = 0);
}
void mdf(int x, int l, int r, int ql, int qr, ll y){
if(ql <= l and r <= qr)return (void)(s[x] += y * (r - l + 1), tg[x] += y);
int mid = l + r >> 1; pd(x, l, r);
if(ql <= mid)mdf(ls, l, mid, ql, qr, y);
if(mid < qr)mdf(rs, mid + 1, r, ql, qr, y);
upd(x);
}
ll qry(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return s[x];
int mid = l + r >> 1; ll res = 0; pd(x, l, r);
if(ql <= mid)res = qry(ls, l, mid, ql, qr);
if(mid < qr)res += qry(rs, mid + 1, r, ql, qr);
return res;
}
这时有了乘法操作修改与下放似乎变得复杂，这时我们需要先分析不同操作的优先级。
首先我们肯定对于乘法与加法分别打标记，然后对于一个加法标记，它的意义是让区间加上一个数，如果直接加那么乘法标记就会受影响。将乘法标记增加一定是错的，所以我们应该将它下放。注意到乘法的优先级是高于加法，所以在下放时要让乘法标记先下放。
如果是有一个乘法标记，这时之前区间内的加法标记也应该乘上它，因为乘法分配律。所以乘法就直接全改了就行。
void upd(int x){
s[x] = (s[ls] + s[rs]) % p;
}
void bld(int x, int l, int r){
tg2[x] = 1;
if(l == r)return (void)(s[x] = a[l]);
int mid = l + r >> 1;
bld(ls, l, mid), bld(rs, mid + 1, r);
upd(x);
}
void pd(int x, int l, int r){
int mid = l + r >> 1;
tg1[ls] = (tg1[ls] * tg2[x] + tg1[x]) % p, tg1[rs] = (tg1[rs] * tg2[x] + tg1[x]) % p;
s[ls] = (s[ls] * tg2[x] + tg1[x] * (mid - l + 1)) % p;
s[rs] = (s[rs] * tg2[x] + tg1[x] * (r - mid)) % p;
tg2[ls] = tg2[ls] * tg2[x] % p;
tg2[rs] = tg2[rs] * tg2[x] % p;
return (void)(tg1[x] = 0, tg2[x] = 1);
}
void mdf1(int x, int l, int r, int ql, int qr, ll y){
if(ql <= l and r <= qr)return (void)(s[x] = y * s[x] % p, tg2[x] = tg2[x] * y % p, tg1[x] = tg1[x] * y % p);
int mid = l + r >> 1; pd(x, l, r);
if(ql <= mid)mdf1(ls, l, mid, ql, qr, y);
if(mid < qr)mdf1(rs, mid + 1, r, ql, qr, y);
upd(x);
}
void mdf2(int x, int l, int r, int ql, int qr, ll y){
if(ql <= l and r <= qr)return (void)(s[x] = (s[x] + y * (r - l + 1)) % p, tg1[x] = (tg1[x] + y) % p);
int mid = l + r >> 1; pd(x, l, r);
if(ql <= mid)mdf2(ls, l, mid, ql, qr, y);
if(mid < qr)mdf2(rs, mid + 1, r, ql, qr, y);
upd(x);
}
ll qry(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return s[x];
int mid = l + r >> 1; ll res = 0; pd(x, l, r);
if(ql <= mid)res = qry(ls, l, mid, ql, qr);
if(mid < qr)res += qry(rs, mid + 1, r, ql, qr);
return res % p;
}
这个题注意修改操作优先级大于加法操作，每次修改操作时需要清空标记。然后就是不要在叶子节点\(\text {pushdown}\)！
void upd(int x){
c[x] = max(c[ls], c[rs]);
}
void build(int x, int l, int r){
tg1[x] = max0810;
if(l == r)return(void)(c[x] = a[l]);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pdtg1(int x){
if(tg1[x] == max0810)return;
tg2[ls] = tg2[rs] = 0;
c[ls] = c[rs] = tg1[ls] = tg1[rs] = tg1[x];
tg1[x] = max0810;
}
void pd(int x){
pdtg1(x);
if(! tg2[x])return;
c[ls] += tg2[x]; c[rs] += tg2[x];
tg2[ls] += tg2[x]; tg2[rs] += tg2[x];
tg2[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int op, ll y){
if(L <= l and r <= R){
if(op ^ 1){
c[x] += y; tg2[x] += y;
}
else{
c[x] = tg1[x] = y;
tg2[x] = 0;
}
return;
}
int mid = l + r >> 1; pd(x);
if(L <= mid)mdfy(ls, l, mid, L, R, op, y);
if(R > mid)mdfy(rs, mid + 1, r, L, R, op, y);
upd(x);
}
ll qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return c[x];
int mid = l + r >> 1; ll res = max0810; pd(x);
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid) res = max(res, qry(rs, mid + 1, r, L, R));
return res;
}
线段树的拓展1（可持久化）
可持久化其实就是加了一个可以访问历史版本的功能，就比如我询问之前某次修改后的答案你可以和普通线段树复杂度一样 \(O(\log n)\) 回答。
考虑具体如何实现。其实每次修改操作，我们只会修改 \(O(\log n)\) 个点，于是我们就可以把这些点组成的链扯出来，对于每次操作重新“开”一颗线段树，就像下面这样。
我们把每次操作看成一个树根，往下修改时就在原来的树上走，如果一个点不修改，就直接继承到现在的树上，否则就新开一个节点。然后其他东西就该咋弄咋弄，正常往这上面套各种线段树应该都行。
然后我们就不得不说一个非常重要的东西了。
可持久化权值线段树（主席树）
是的，我们如果让权值线段树可持久化，它就成了众所周知的主席树。这个东西能够查询静态区间第 \(k\) 小。至于动态区间第 \(k\) 小嘛，在外面再套一个树状数组不就行了？
先说静态的。我们把输入每一个数看成一次操作，而每次操作就是在值域中修改一个点。然后询问的时候就可以看成前缀和。在树上走的时候，对于寻找当前区间 \([l,r]\) 中值域里的第 \(k\) 大，我就正常线段树二分，但是同时二分两棵线段树，对于一个 \(mid\)，前一半的值域在 \([l,r]\) 中数的个数等价于 \([1,r]\) 中数的个数减去 \([1,l-1]\) 中数的个数。然后就可以直接做了。
代码如下：
int n, m, a[N], b[N], tt;
int rt[N << 5], c[N << 5], nd, ls[N << 5], rs[N << 5];
void upd(int &x, int y, int l, int r, int p){
x = ++nd; c[x] = c[y] + 1;
if(l == r)return; int mid = l + r >> 1;
if(p <= mid)rs[x] = rs[y], upd(ls[x], ls[y], l, mid, p);
else ls[x] = ls[y], upd(rs[x], rs[y], mid + 1, r, p);
}
int qry(int x, int y, int l, int r, int k){
if(l == r)return l; int mid = l + r >> 1, res = c[ls[x]] - c[ls[y]];
if(res >= k)return qry(ls[x], ls[y], l, mid, k);
return qry(rs[x], rs[y], mid + 1, r, k - res);
}
signed main(){
n = rd(), m = rd();
for(int i = 1; i <= n; ++i)a[i] = b[i] = rd();
sort(b + 1, b + 1 + n);
tt = unique(b + 1, b + 1 + n) - b - 1;
for(int i = 1; i <= n; ++i)a[i] = lower_bound(b + 1, b + 1 + tt, a[i]) - b, upd(rt[i], rt[i - 1], 1, tt, a[i]);
for(int i = 1; i <= m; ++i){
int l = rd(), r = rd(), k = rd();
printf("%d\n", b[qry(rt[r], rt[l - 1], 1, tt, k)]);
}
return 0;
}
然后考虑动态区间怎么做。
我们可以给主席树套一棵树状数组，每次暴力修改完在树状数组上维护，注意树状数组记录的其实只是每一棵主席树的树根，所以跑树状数组每一个点时要在对应的主席树上进行修改。查询可类比上文，上文中我们记录了两个树根，现在我们可以把树状数组上的一些相关的树根开两个数组记一下，每次二分就把所有树的答案累加起来，其他部分与上面类似不再赘述。
代码如下：
namespace SGT{
int nd, rt[N << 9], ls[N << 9], rs[N << 9], c[N << 9];
void gotols(){
for(int i = 1; i <= c1; ++i)q1[i] = ls[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = ls[q2[i]];
}
void gotors(){
for(int i = 1; i <= c1; ++i)q1[i] = rs[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = rs[q2[i]];
}
void upd(int &x, int l, int r, int p, int y){
if(! x)x = ++nd; c[x] += y;
if(l == r)return; int mid = l + r >> 1;
if(p <= mid)upd(ls[x], l, mid, p, y);
else upd(rs[x], mid + 1, r, p, y);
}
int qryk(int l, int r, int k){
if(l == r)return l; int mid = l + r >> 1, res = 0;
for(int i = 1; i <= c1; ++i)res -= c[ls[q1[i]]];
for(int i = 1; i <= c2; ++i)res += c[ls[q2[i]]];
if(res >= k)return gotols(), qryk(l, mid, k);
return gotors(), qryk(mid + 1, r, k - res);
}
int qryrk(int l, int r, int k){
if(l == r)return 0; int mid = l + r >> 1, res = 0;
if(k <= mid)return gotols(), qryrk(l, mid, k);
for(int i = 1; i <= c1; ++i)res -= c[ls[q1[i]]];
for(int i = 1; i <= c2; ++i)res += c[ls[q2[i]]];
return gotors(), res + qryrk(mid + 1, r, k);
}
}
using namespace SGT;
namespace BIT{
int lb(int x){return x & - x;}
void get(int l, int r){
c1 = c2 = 0;
for(int i = l - 1; i; i -= lb(i))q1[++c1] = rt[i];
for(int i = r; i; i -= lb(i))q2[++c2] = rt[i];
}
void mdf(int p, int y){
int x = lower_bound(b + 1, b + 1 + tt, a[p]) - b;
for(; p <= n; p += lb(p))upd(rt[p], 1, tt, x, y);
}
int kth(int l, int r, int k){get(l, r); return qryk(1, tt, k);}
int rk(int l, int r, int k){int kk = lower_bound(b + 1, b + 1 + tt, k) - b; get(l, r); return qryrk(1, tt, kk) + 1;}
}
首先分析题目性质，想想我们的答案有什么特点。因为是找最大中位数，是不是应该可以二分啊。假设当前二分一个 \(mid\)，有一个套路就是把大于等于它的赋值成一，否则为零，然后看求子段和是否大于等于零即可判断。对于这道题，就是中间确定部分的可以用值域线段树维护，左右两边再分别开一个线段树维护前后缀最大子段和就行。
然后关于代码，就是放的我的远古时期写的我自己都看的难受神秘代码。
#include<bits/stdc++.h>
#define s(x) tr[x].sum
#define ls(x) tr[x].lson
#define rs(x) tr[x].rson
#define lm(x) tr[x].lmx
#define rm(x) tr[x].rmx
#define lc(x) tr[x].ncl
#define rc(x) tr[x].ncr
using namespace std;
const int N = 2e4 + 10;
int n, m, a[N], num[N], cnt, rt[N], idq, x1, x2, x3, x4;
int L(int x){return lower_bound(num + 1, num + cnt + 1, x) - num;}
struct tree
{
int sum, lmx, rmx;
int lson, rson;
bool ncl, ncr;
}tr[N * 40];
vector < int > c[N];
void upd(int x)
{
s(x) = s(ls(x)) + s(rs(x));
lm(x) = max(lm(ls(x)), s(ls(x)) + lm(rs(x)));
rm(x) = max(rm(rs(x)), s(rs(x)) + rm(ls(x)));
}
int build(int l, int r)
{
int x = ++idq;
if(l == r)
{
if(L(a[l]) < 2)s(x) = lm(x) = rm(x) = - 1;
else s(x) = lm(x) = rm(x) = 1;
return x;
}
int mid = l + r >> 1; lc(x) = rc(x) = 1;
ls(x) = build(l, mid); rs(x) = build(mid + 1, r);
upd(x); return x;
}
int modify(int x, int y, int l, int r, int to, int val, bool cc)
{
if(!cc)x = ++idq;
if(l == r)
{
s(x) = lm(x) = rm(x) = val;
return x;
}
int mid = l + r >> 1;
if(to <= mid)
{
if(!rc(x)) rs(x) = rs(y);
if(!lc(x))lc(x) = 1, ls(x) = modify(x, ls(y), l, mid, to, val, 0);
else ls(x) = modify(ls(x), ls(y), l, mid, to, val, 1);
}
else
{
if(!lc(x)) ls(x) = ls(y);
if(!rc(x))rc(x) = 1, rs(x) = modify(x, rs(y), mid + 1, r, to, val, 0);
else rs(x) = modify(rs(x), rs(y), mid + 1, r, to, val, 1);
}
upd(x); return x;
}
int query(int x, int l, int r, int L, int R)
{
if(L <= l and r <= R)return s(x);
int mid = l + r >> 1; int ret = 0;
if(L <= mid)ret += query(ls(x), l, mid, L, R);
if(mid < R)ret += query(rs(x), mid + 1, r, L, R);
return ret;
}
tree query1(int x, int l, int r, int L, int R)
{
if(L <= l and r <= R)return tr[x];
int mid = l + r >> 1;
if(L <= mid and mid < R)
{
tree ret;
tree le = query1(ls(x), l, mid, L, R);
tree ri = query1(rs(x), mid + 1, r, L, R);
ret.sum = le.sum + ri.sum;
ret.lmx = max(le.lmx, le.sum + ri.lmx);
return ret;
}
else if(L <= mid)return query1(ls(x), l, mid, L, R);
else return query1(rs(x), mid + 1, r, L, R);
}
tree query2(int x, int l, int r, int L, int R)
{
if(L <= l and r <= R)return tr[x];
int mid = l + r >> 1;
if(L <= mid and mid < R)
{
tree ret;
tree le = query2(ls(x), l, mid, L, R);
tree ri = query2(rs(x), mid + 1, r, L, R);
ret.sum = le.sum + ri.sum;
ret.rmx = max(ri.rmx, ri.sum + le.rmx);
return ret;
}
else if(L <= mid)return query2(ls(x), l, mid, L, R);
else return query2(rs(x), mid + 1, r, L, R);
}
bool check(int val)
{
int sz = 0;
if(x2 + 2 <= x3) sz = query(rt[val], 1, n, x2 + 1, x3 - 1);
int sr = query1(rt[val], 1, n, x3, x4).lmx;
int sl = query2(rt[val], 1, n, x1, x2).rmx;
return (sl + sz + sr) >= 0;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)scanf("%d", &a[i]), num[++cnt] = a[i];
sort(num + 1, num + cnt + 1);
cnt = unique(num + 1, num + cnt + 1) - num - 1;
for(int i = 1; i <= n; i++)c[L(a[i])].push_back(i);
rt[1] = build(1,n);
for(int i = 2; i <= cnt; i++)for(int j = 0; j < c[i - 1].size(); j++)
{
int go = c[i - 1][j];
rt[i] = modify(rt[i], rt[i - 1], 1, n, go, - 1, rt[i] > 0);
}
scanf("%d", &m);
int las = 0;
int d[6];
while(m--)
{
scanf("%d %d %d %d", &x1, &x2, &x3, &x4);
d[1] = (x1 + las) % n;
d[2] = (x2 + las) % n;
d[3] = (x3 + las) % n;
d[4] = (x4 + las) % n;
sort(d + 1, d + 5);
x1 = d[1] + 1, x2 = d[2] + 1, x3 = d[3] + 1, x4 = d[4] + 1;
int l = 1, r = cnt;
int ans = 0;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid))ans = mid, l = mid + 1;
else r = mid - 1;
}
las = num[ans];
printf("%d\n", las);
}
return 0;
}
线段树的拓展2（线段树合并）
注意合并要用动态开点线段树，不然复杂度会变成 \(O(n\log^2n)\) 的，因为线段树有 \(O(n\log n)\) 个节点，合并又是 \(O(\log n)\) 的。
怎么合并呢？我们还是在树上走，如果走到一点地方时存在节点（可能是一个或两个）为空，就可以直接返回另一个节点，否则就往下递归，到叶子时合并回来即可。但是乍一看这不是爆炸了吗？所以接下来我们需要口胡细致分析一下复杂度。
容易发现：在合并两棵树的过程中走到有空节点的时候就返回了，相当于走一个点就会删掉一些点，所以总复杂度不会超过总点数也就是 \(O(n\log n)\)。
讲题前先谈谈我对于线段树合并的理解。首先为什么需要合并线段树，就是因为对于一些问题我们需要合并的信息是 \(O(n)\) 级别的，对于这类式子我们肯定需要一种 \(O(\log)\) 的方式去优化。然后就是如何去理解合并的过程，因为如果真的每一个点都开一个线段树那肯定爆炸没得说。其实我们是把每个点对应在一段区间上，或是下标或是值域，然后对于每一个点的线段树动态开点，最后是合并过程中并不是单纯的加加减减，而是要根据你的式子去还原整个过程，或许你现在还不太懂，但等你看了后面某道题后你便会恍然大悟。
然后看一道板子。
P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
观察到是在树上修改，于是可以联想到某个经典套路，将树上路径转化成差分。具体的，对于一条路径 \((u,v)\)，设 \(t=lca(u,v)\)，则我可以把对于 \((u,v)\) 的操作看成对于 \((root,u)\) 和 \((root,v)\) 的操作还有 \((root,t)\) 和 \((root,fa_t)\) 的逆操作。然后考虑对每个点开线段树。本题可以用颜色做线段树下标，然后就似乎是单点修改（直接线段树二分）加上线段树合并。
然后稍微注意一下树上合并时需要跑一遍 dfs 序，然后递归返回时合并。
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1, sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
int lca(int u, int v){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
u = fa[tp[u]];
}
return dep[u] < dep[v] ? u : v;
}
void upd(int x){
if(s[ls[x]] > s[rs[x]] or (s[ls[x]] == s[rs[x]] and col[ls[x]] < col[rs[x]]))return(void)(s[x] = s[ls[x]], col[x] = col[ls[x]]);
s[x] = s[rs[x]], col[x] = col[rs[x]];
}
void md(int &p, int l, int r, int c, int y){
if(! p)p = ++tot;
if(l == r)return(void)(s[p] += y, col[p] = c);
int mid = l + r >> 1;
if(c <= mid)md(ls[p], l, mid, c, y);
else md(rs[p], mid + 1, r, c, y);
upd(p);
}
int merge(int a, int b, int l, int r){
if(! a or ! b)return a | b;
if(l == r)return s[a] += s[b], a;
int mid = l + r >> 1;
ls[a] = merge(ls[a], ls[b], l, mid);
rs[a] = merge(rs[a], rs[b], mid + 1, r);
upd(a); return a;
}
void dfs(int u){
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u])continue;
dfs(v); rt[u] = merge(rt[u], rt[v], 1, 100000);
}
if(s[rt[u]])ans[u] = col[rt[u]];
}
signed main(){
n = rd(), q = rd();
for(int i = 1; i < n; ++i){
int u = rd(), v = rd();
add(u, v); add(v, u);
}
dfs1(1, 0); dfs2(1, 1);
for(int i = 1; i <= q; ++i){
int u = rd(), v = rd(), w = rd();
md(rt[u], 1, 100000, w, 1); md(rt[v], 1, 100000, w, 1);
int f = lca(u, v);
md(rt[f], 1, 100000, w, - 1); md(rt[fa[f]], 1, 100000, w, - 1);
}
dfs(1);
for(int i = 1; i <= n; ++i)printf("%d\n", ans[i]);
return 0;
}
怎么感觉有点过于板子了？
对于求第 \(k\) 大的问题我们用值域线段树，然后考虑怎么解决连通性？然后你会发现直接并查集维护，然后并查集就是菊花图，对每朵花的花心开一棵线段树，然后正常合并即可。
int fd(int x){
return x == f[x] ? x : f[x] = fd(f[x]);
}
void upd(int x){
s[x] = s[ls[x]] + s[rs[x]];
}
void md(int &p, int l, int r, int y){
if(! p)p = ++cnt;
if(l == r)return(void)(++s[p]);
int mid = l + r >> 1;
if(y <= mid)md(ls[p], l, mid, y);
else md(rs[p], mid + 1, r, y);
upd(p);
}
int merge(int a, int b, int l, int r){
if(! a or ! b)return a | b;
if(l == r)return s[a] += s[b], a;
int mid = l + r >> 1;
ls[a] = merge(ls[a], ls[b], l, mid);
rs[a] = merge(rs[a], rs[b], mid + 1, r);
upd(a); return a;
}
int qry(int p, int l, int r, int y){
if(l == r)return l;
int mid = l + r >> 1, ans;
if(s[ls[p]] >= y)ans = qry(ls[p], l, mid, y);
else ans = qry(rs[p], mid + 1, r, y - s[ls[p]]);
return ans;
}
void sol1(){
int x = rd(), y = rd();
x = fd(x), y = fd(y);
if(x == y)return;
f[y] = x; rt[x] = merge(rt[x], rt[y], 1, 100000);
}
signed main(){
n = rd(), m = rd();
for(int i = 1, x; i <= n; ++i)md(rt[i], 1, 100000, x = rd()), f[i] = i, pos[x] = i;
for(int i = 1; i <= m; ++i)sol1();
q = rd();
for(int i = 1; i <= q; ++i){
char c; cin >> c;
if(c == 'B')sol1();
else{
int x = rd(), y = rd(); x = fd(x);
if(s[rt[x]] < y){puts("-1"); continue;}
printf("%d\n", pos[qry(rt[x], 1, 100000, y)]);
}
}
return 0;
}
是不是觉得太简单了？那么来一点有难度的。
对于这道题我们可以很容易想到一个暴力 dp，设 \(f_{u,i}\) 表示 \(u\) 节点为第 \(i\) 大的数的概率。然后答案就是：
\[\sum_{i=1}^mi\times V_i\times f_{1,i}^2 \]然后开始转移，我们令当前点 \(u\) 的左儿子叫 \(l\)，右儿子叫 \(r\)，转移式子也就呼之欲出：
\[f_{u,i}=f_{l,i}\times p_u\times\sum_{j<i}f_{r,j}+ f_{r,i}\times p_u\times\sum_{j<i}f_{l,j}+ f_{l,i}\times (1-p_u)\times\sum_{j>i}f_{r,j}+ f_{r,i}\times (1-p_u)\times\sum_{j>i}f_{l,j} \]希望没有笔误
然后你就发现每次你都需要拿一段前缀出来转移，能不能优化一下啊？然而确实可以。考虑线段树维护，下标就是排名（dp 的第二维）。现在你就把每个 \(f_i\) 都看成二叉树上的点权，然后就可以合并了但是，
考虑这道题的合并并不是单纯的加减，我们上面推出的转移式中 \(f_i\) 是带了系数的，所以在合并时我们还需要记一下系数，那么系数又怎么求呢？
考虑把上面的式子拆完，就是对于线段树上一个点 \(i\)，它的系数就是：
\[\sum_{k,j<i}p_k\times f_j+\sum_{k',j'>i}(1-p_{k'})\times f_{j'} \]说人话就是左边（下标）比它小的点乘上对应节点的概率 \(p\) 加上右边的。所以按照上面的实现就好了。
此题小结
其实线段树合并的本质就是优化状态转移。对于合并的顺序需要注意与线段树配套用的工具具体选择，然后对于合并的式子其实就是转移式子的复现，具体一点也就是拆分再乘法分配律合并同类项。
代码
const db eps = 1e-8;
const ll inf = 1e18;
const int N = 3e5 + 5, p = 998244353;
ll qmi(ll x, ll y){
ll res = 1ll;
for(; y; y >>= 1, x = x * x % p)if(y & 1)res = res * x % p;
return res;
}
const ll ii = qmi(10000, p - 2);
int n, b[N], nd, m;
int rt[N << 5], ls[N << 5], rs[N << 5];
ll s[N << 5], tg[N << 5], f[N], a[N];
int fa[N], c[N], ch[N][2];
inline int jia(int x, int y){return x - p + y >= 0 ? x - p + y : x + y;}
void upd(int x){
s[x] = jia(s[ls[x]], s[rs[x]]);
}
void updd(int x, ll y){
if(! x)return;
s[x] = s[x] * y % p;
tg[x] = tg[x] * y % p;
}
void pd(int x){
if(tg[x] == 1)return;
updd(ls[x], tg[x]), updd(rs[x], tg[x]);
return (void)(tg[x] = 1);
}
void addin(int &x, int l, int r, int pos){
if(! x)tg[x = ++nd] = 1;
if(l == r)return(void)(s[x] = 1);
int mid = l + r >> 1; pd(x);
if(pos <= mid)addin(ls[x], l, mid, pos);
else addin(rs[x], mid + 1, r, pos);
upd(x);
}
int merge(int x, int y, int l, int r, ll sx, ll sy, ll pp){
if(! x or ! y)return updd(x | y, (x ? sx : sy)), x | y;
int mid = l + r >> 1; pd(x), pd(y);
ll lsl = s[ls[x]], rsl = s[rs[x]], lsr = s[ls[y]], rsr = s[rs[y]];
ls[x] = merge(ls[x], ls[y], l, mid, jia(sx, rsr * (p + 1 - pp) % p), jia(sy, rsl * (p + 1 - pp) % p), pp);
rs[x] = merge(rs[x], rs[y], mid + 1, r, jia(sx, lsr * pp % p), jia(sy, lsl * pp % p), pp);
return upd(x), x;
}
void dfs(int u){
if(! c[u])addin(rt[u], 1, m, a[u]);
if(c[u] == 1)dfs(ch[u][0]), rt[u] = rt[ch[u][0]];
if(c[u] == 2)dfs(ch[u][0]), dfs(ch[u][1]), rt[u] = merge(rt[ch[u][0]], rt[ch[u][1]], 1, m, 0, 0, a[u]);
}
void getans(int x, int l, int r){
if(! x)return;
if(l == r)return(void)(f[l] = s[x]);
int mid = l + r >> 1; pd(x);
getans(ls[x], l, mid); getans(rs[x], mid + 1, r);
}
int main(){
rd(n);
for(int i = 1; i <= n; ++i)rd(fa[i]), fa[i] ? ch[fa[i]][c[fa[i]]++] = i : 0;
for(int i = 1; i <= n; ++i){
rd(a[i]);
if(c[i])a[i] = a[i] * ii % p;
else b[++m] = a[i];
}
sort(b + 1, b + 1 + m);
for(int i = 1; i <= n; ++i)if(! c[i])a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b;
dfs(1); getans(rt[1], 1, m); ll ans = 0;
for(int i = 1; i <= m; ++i)ans = jia(ans, 1ll * i * b[i] % p * f[i] % p * f[i] % p);
wt(ans);
return 0;
}
线段树的一些高级玩法
这一部分主要是一些其他的算法、思想与线段树的运用，其实最主要的思想还是寻找题目性质，然后线段树优化维护信息的过程。
那就先来看一些线段树与树剖的东西。
树剖+线段树
做过序列上给一些颜色求颜色段数量的题吧？如果我把它扔到树上会怎么样呢？
结果是根本不会怎么样。直接树剖把树变成链做，套上线段树就完了。
void add(int u, int v){
e[++cnt] = {hd[u], v}; hd[u] = cnt;
}
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1; sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top; dfn[u] = ++tim, rk[tim] = u;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
struct node{
int len, l, r;
};
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
lc[x] = lc[ls], rc[x] = rc[rs];
s[x] = s[ls] + s[rs] - (rc[ls] == lc[rs]);
}
void build(int x, int l, int r){
if(l == r)return(void)(lc[x] = rc[x] = a[rk[l]], s[x] = 1);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pd(int x){
if(! lz[x])return;
lc[ls] = rc[ls] = lz[x];
lc[rs] = rc[rs] = lz[x];
s[ls] = s[rs] = 1;
lz[ls] = lz[rs] = lz[x]; lz[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int c){
if(L <= l and r <= R)return(void)(lc[x] = rc[x] = lz[x] = c, s[x] = 1);
int mid = l + r >> 1; pd(x);
if(L <= mid)mdfy(ls, l, mid, L, R, c);
if(R > mid)mdfy(rs, mid + 1, r, L, R, c);
upd(x);
}
node qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return {s[x], lc[x], rc[x]};
int mid = l + r >> 1; node res, t; pd(x);
res = {0, 0, 0};
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid){
t = qry(rs, mid + 1, r, L, R);
if(! res.len)return t;
res.len += t.len - (rc[ls] == lc[rs]);
res.r = t.r;
}
return res;
}
void mpath(int u, int v, int c){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
mdfy(1, 1, n, dfn[tp[u]], dfn[u], c);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
mdfy(1, 1, n, dfn[u], dfn[v], c);
}
int qpath(int u, int v){
int pr1 = 0, pr2 = 0, ans = 0;
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v), swap(pr1, pr2);
node res = qry(1, 1, n, dfn[tp[u]], dfn[u]);
ans += res.len - (pr1 == res.r);
pr1 = res.l; u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v), swap(pr1, pr2);
node res = qry(1, 1, n, dfn[u], dfn[v]);
ans += res.len - (pr1 == res.l) - (pr2 == res.r);
return ans;
}
这道是不是太简单了一点？那就加强一下！
这下看懂了！
其实颜色段的处理不成问题，我们需要思考的是树根的变化应该如何高效处理。
这个时候我们就可以分类讨论一下树根的位置了。如果树根就是询问点那直接输出全局的答案；如果树根不在当前询问点 \(u\) 的子树内，是不是对 \(u\) 根本没有影响啊！最后就剩一种——在 \(u\) 的某棵子树内，这时候我们肯定要先找到是哪一棵子树，然后用全局减去这棵子树就行。
那么如何快速找子树呢？我们可以类比树剖求 LCA 的过程，然后就做完了。找子树和其他操作都是 \(O(n\log n)\) 的。
void add(int u, int v){
e[++cnt] = {hd[u], v}; hd[u] = cnt;
}
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1; sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top; dfn[u] = ++tim, rk[tim] = u;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
mi[x] = min(mi[ls], mi[rs]);
}
void build(int x, int l, int r){
if(l == r)return(void)(mi[x] = a[rk[l]]);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pd(int x){
if(! lz[x])return;
mi[ls] = mi[rs] = lz[x];
lz[ls] = lz[rs] = lz[x]; lz[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int c){
if(L <= l and r <= R)return(void)(mi[x] = lz[x] = c);
int mid = l + r >> 1; pd(x);
if(L <= mid)mdfy(ls, l, mid, L, R, c);
if(R > mid)mdfy(rs, mid + 1, r, L, R, c);
upd(x);
}
ll qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return mi[x];
int mid = l + r >> 1; ll res = INF; pd(x);
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid)res = min(res, qry(rs, mid + 1, r, L, R));
return res;
}
void mpath(int u, int v, int c){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
mdfy(1, 1, n, dfn[tp[u]], dfn[u], c);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
mdfy(1, 1, n, dfn[u], dfn[v], c);
}
ll qtree(int u){
if(u == root)return mi[1];
if(dfn[root] < dfn[u] or dfn[root] >= dfn[u] + sz[u])return qry(1, 1, n, dfn[u], dfn[u] + sz[u] - 1);
int v = root;
while(tp[u] != tp[v]){
v = tp[v];
if(fa[v] == u)break;
v = fa[v];
}
if(tp[u] == tp[v])v = rk[dfn[u] + 1];
return min(qry(1, 1, n, 1, dfn[v] - 1), qry(1, 1, n, dfn[v] + sz[v], n));
}
好了也该来一道那啥一点的题了（
如果你会 LCT 而且代码能力强的话建议直接无脑做就完了。
考虑不会 LCT 的人会怎么做。如果用数据结构啥的维护删边可能不太现实，所以考虑倒着做就把删边变成了加边。然后就是如何维护两点之间桥的数量。我可以先把初始的桥给处理出来，跑一下 tarjan 然后图就成了一棵树，然后考虑加边操作意味着什么。如果现在需要将 \((u,v)\) 加入图中，那么树上 \(u,v\) 之间的路径上的桥就都没了，因为构成环。所以每次加边操作都可以看成区间赋值，然后树剖套一个果的线段树就做完了。
void addx(int u, int v){
ex[++cntx] = {hdx[u], v}; hdx[u] = cntx;
}
void tarjan(int u, int fa){
id[u] = low[u] = ++seq;
st.push(u);
for(int i = hdx[u]; i; i = ex[i].nxt){
int v = ex[i].to;
if(v == fa)continue;
if(! id[v])tarjan(v, u);
low[u] = min(low[u], low[v]);
}
if(low[u] == id[u]){
++ct;
while(st.top() ^ u){
col[st.top()] = ct;
st.pop();
}
col[u] = ct; st.pop();
}
}
void add(int u, int v){
e[++cnt] = {hd[u], v}; hd[u] = cnt;
}
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1; sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top; dfn[u] = ++tim, rk[tim] = u;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
s[x] = s[ls] + s[rs];
}
void build(int x, int l, int r){
if(l == r)return(void)(s[x] = 1);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pd(int x, int l, int r){
if(! lz[x])return;
int mid = l + r >> 1;
s[ls] = s[rs] = 0;
lz[ls] = lz[rs] = lz[x]; lz[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int c){
if(L <= l and r <= R)return(void)(s[x] = c, lz[x] = 1);
int mid = l + r >> 1; pd(x, l, r);
if(L <= mid)mdfy(ls, l, mid, L, R, c);
if(R > mid)mdfy(rs, mid + 1, r, L, R, c);
upd(x);
}
ll qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return s[x];
int mid = l + r >> 1, res = 0; pd(x, l, r);
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid)res += qry(rs, mid + 1, r, L, R);
return res;
}
void mpath(int u, int v, int c){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
mdfy(1, 1, n, dfn[tp[u]], dfn[u], c);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
mdfy(1, 1, n, dfn[u] + 1, dfn[v], c);
}
int qpath(int u, int v){
int res = 0;
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
res += qry(1, 1, n, dfn[tp[u]], dfn[u]);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
return res + qry(1, 1, n, dfn[u] + 1, dfn[v]);
}
signed main(){
n = rd(), m = rd();
for(int i = 1; i <= m; ++i){
E[i].u = rd(), E[i].v = rd();
if(E[i].u > E[i].v)swap(E[i].u, E[i].v);
++mp[mkp(E[i].u, E[i].v)];
}
while(1){
q[++tot][0] = rd();
if(q[tot][0] == - 1)break;
q[tot][1] = rd(), q[tot][2] = rd();
if(q[tot][1] > q[tot][2])swap(q[tot][1], q[tot][2]);
if(! q[tot][0])--mp[mkp(q[tot][1], q[tot][2])];
}
--tot;
for(int i = 1; i <= m; ++i){
int u = E[i].u, v = E[i].v;
if(mp[mkp(u, v)])addx(u, v), addx(v, u);
}
tarjan(1, 0);
for(int i = 1; i <= m; ++i){
int u = E[i].u, v = E[i].v;
if(mp[mkp(u, v)] and col[u] ^ col[v])add(col[u], col[v]), add(col[v], col[u]);
}
for(int i = 1; i <= tot; ++i)q[i][1] = col[q[i][1]], q[i][2] = col[q[i][2]];
dfs1(1, 0); dfs2(1, 1); build(1, 1, n);
for(int i = tot; i; --i){
if(q[i][0])ans[++tt] = q[i][1] == q[i][2] ? 0 : qpath(q[i][1], q[i][2]);
else mpath(q[i][1], q[i][2], 0);
}
for(int i = tt; i; --i)printf("%d\n", ans[i]);
return 0;
}