『权值动态开点线段树』『线段树合并算法』简单理解

权值线段树与动态开点

在正常的线段树中，我们总是以下表来进行线段树的操作。而权值线段树主要用于对具体的权值进行构造线段树，用于权值计数，权值操作等问题。

由于权值太大，我们不再采用完全二叉树的编号方式，使用类似于邻接表一样的存储方式，每一个节点只存储它儿子节点的编号；且只对有用区间进行开点操作，这样复杂度也是$log$级别的。

例如，需要添加权值为为$4$的点，而总区间是$[1,10]$;我们只需要开展区间$[1,10],[1,5],[4,5],[4,4]$即可。

代码如下：

void Build(int p,int l,int r,int x,int v) { if (l == r) { t[p].ans = v; return; } int mid = l+r >> 1; if (x <= mid) { if (t[p].lc == 0) t[p].lc = getnew(); Build(t[p].lc,l,mid,x,v); } else { if (t[p].rc == 0) t[p].rc = getnew(); Build(t[p].rc,mid+1,r,x,v); } t[p].ans = t[t[p].lc].ans+t[t[p].rc].ans; return; } //单点修改位置x为v 动态开点

---

线段树合并

线段树合并所完成的操作就是：在相同区间内，对应位置相加。

我们可以使用如下方法解决：两个相同区间的节点分别为$p$和$q$，合并区间为$[l,r]$,若未建立则为0.

若$p$和$q$有其一为0，则另一者为根。若$l=r$,则累加权值，返回p。合并$p$的左孩子和$q$的左孩子，$p$的右孩子和$q$的右孩子；再讲对应位置的权值相加，返回$p$。

代码如下：

int merge(int p,int q,int l,int r) { if (p == 0) return q; if (q == 0) return p; if (l == r) { t[p].ans += t[q].ans; return p; } int mid = l+r >> 1; t[p].lc = merge(t[p].lc,t[q].lc,l,mid); t[p].rc = merge(t[p].rc,t[q].rc,mid+1,r); t[p].ans = t[t[p].lc].ans + t[t[p].rc].ans; return p; } //线段树合并

---

Question1

题目链接：[USACO17JAN]Promotion Counting晋升者计数

求每一个节点中，比根节点权值大子节点的个数。

对每一个权值进行离散化操作，空时在$n$的范围以内。首先，每一个点都是以为有且仅有节点$v_i$且权值为$1$的线段树。自底向上遍历每一个节点，当查询以$i$为根的节点时将所属的所有子节点的线段树进行合并；查询区间$[v_i+1,MAX]$的总和，则这一个数值即为所求的答案。

在这一个问题中，我们利用线段树合并解决了一类权值计数类问题，由于特殊的树形结构之间点特殊的约束关系，我们便可以联想到利用线段树合并算法来进行操作。

Ques2

题目链接：[POI2011]ROT-Tree Rotations

显然逆序对的数量和权值有关，所以这是一个权值计数类问题；由于特殊的树形结构的约束，我们通过上一题的分析能够很自然的想到是线段树合并算法。

初始化：每叶节点建立线段树，以权值为下标，以1为权值的线段树。

对于每一个非叶节点，我们考虑子树是否交换。显然当前产生的逆序分成两部分：

两个子节点本身所产生的逆序对。左孩子的右区间和*右孩子的左区间和→不交换左孩子的左区间和*右孩子的右区间和→交换

答案中选取一个最大值，再将线段树合并即可。

而这道题线段树合并的作用是：将若干个子节点的信息统计到某一个根节点上，便于答案的统计。

这道题读入很诡异呢

代码

question1

#include <bits/stdc++.h> using namespace std; inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c<'0' || c>'9') {if (c == '-') w = -1; c = getchar();} while (c>='0' && c<='9') s = s*10+c-48,c = getchar(); return s*w; } int n, tot = 0, cnt = 0; struct node { int v,num,t; friend bool operator < (node p1,node p2) { return p1.v < p2.v; } } a[5000000]; struct Tree { int lc, rc, ans; } t[5000000]; int ans[200000]; int root[200000]; int Link[200000]; struct edge { int y,next; } e[5000000]; bool cmp(node p1, node p2) { return p1.num < p2.num; } int getnew(void) { tot ++; return tot; } void add(int x,int y) { tot ++; e[tot].y = y; e[tot].next = Link[x]; Link[x] = tot; } void Build(int p,int l,int r,int x,int v) { if (l == r) { t[p].ans = v; return; } int mid = l+r >> 1; if (x <= mid) { if (t[p].lc == 0) t[p].lc = getnew(); Build(t[p].lc,l,mid,x,v); } else { if (t[p].rc == 0) t[p].rc = getnew(); Build(t[p].rc,mid+1,r,x,v); } t[p].ans = t[t[p].lc].ans+t[t[p].rc].ans; return; } //单点修改位置x为v 动态开点 int merge(int p,int q,int l,int r) { if (p == 0) return q; if (q == 0) return p; if (l == r) { t[p].ans += t[q].ans; return p; } int mid = l+r >> 1; t[p].lc = merge(t[p].lc,t[q].lc,l,mid); t[p].rc = merge(t[p].rc,t[q].rc,mid+1,r); t[p].ans = t[t[p].lc].ans + t[t[p].rc].ans; return p; } //线段树合并 int ask(int root,int l,int r,int L,int R) { if (root == 0) return 0; if (L <= l && R >= r) return t[root].ans; int mid = l+r >> 1, ans = 0; if (L <= mid) ans += ask(t[root].lc,l,mid,L,R); if (R > mid) ans += ask(t[root].rc,mid+1,r,L,R); return ans; } //线段树 区间求和 void dfs(int x,int fa) { for (int i=Link[x];i;i=e[i].next) { int y = e[i].y; if (y == fa) continue; dfs(y,x); if (a[x].t < cnt) ans[x] += ask(root[y],1,cnt,a[x].t+1,cnt); root[x] = merge(root[x],root[y],1,cnt); } return; } int main(void) { n = read(); for (int i=1;i<=n;++i) { a[i].v = read(); a[i].num = i; } sort(a+1, a+n+1); for (int i=1;i<=n;++i) if (a[i].v ^ a[i-1].v || i == 1) a[i].t = ++cnt; else a[i].t = a[i-1].t; //离散化 for (int i=2;i<=n;++i) { int fa = read(); add(i,fa); add(fa,i); } sort(a+1, a+n+1, cmp); for (int i=1;i<=n;++i) { root[i] = getnew(); Build(root[i],1,cnt,a[i].t,1); } dfs(1,0); for (int i=1;i<=n;++i) printf("%d\n",ans[i]); return 0; }

question2

#include <bits/stdc++.h> #define int long long using namespace std; int n, tot = 0; int ans1, ans2; int ans = 0; struct node { int lc,rc,ans; } a[10000000]; void Build(int p,int l,int r,int v) { if (l == r) { a[p].ans = 1; return; } //注意逆序对此处也要赋值为1 不然无法统计答案 int mid = l+r >> 1; if (v <= mid) { a[p].lc = ++tot; Build(a[p].lc,l,mid,v); } else { a[p].rc = ++tot; Build(a[p].rc,mid+1,r,v); } a[p].ans = a[a[p].lc].ans + a[a[p].rc].ans; return; } int merge(int p,int q,int l,int r) { if (p == 0) return q; if (q == 0) return p; int mid = l+r >> 1; ans1 += a[a[p].rc].ans * a[a[q].lc].ans;//不交换子树 ans2 += a[a[p].lc].ans * a[a[q].rc].ans;//交换子树 a[p].lc = merge(a[p].lc,a[q].lc,l,mid); a[p].rc = merge(a[p].rc,a[q].rc,mid+1,r); a[p].ans = a[a[p].lc].ans + a[a[p].rc].ans; return p; } int dfs(void) { int root,x; scanf("%lld",&x); if (x != 0) root = ++tot, Build(root,1,n,x); else { int x = dfs(); int y = dfs(); root = merge(x,y,1,n); ans += min(ans1,ans2); ans1 = ans2 = 0; } return root; } signed main(void) { freopen("rot.in","r",stdin); freopen("rot.out","w",stdout); scanf("%lld",&n); dfs(); cout<<ans<<endl; return 0; }