对于某些对子树的统计问题,我们固然可以用DSU on Tree来解决,但是一旦带上修改,甚至是加上历史化版本的查询,我们就不得不求助于其他的算法,本篇将对线段树合并进行讲解
线段树合并一般用于对子树的统计,一般的套路就是对树的每一个节点都开上一颗动态开点线段树,然后统计子树信息时,合并所有儿子信息,统计答案,然后继续向上走;
\(code\):
void merge(int &x,int y)
{
if(!x||!y){x=x+y;return;}
sum[x]+=sum[y];
merge(ls[x],ls[y]);
merge(rs[x],rs[y]);
}
如果希望改为维护历史版本,可以这样改:
int merge(int x,int y)
{
if(!x||!y){ return x+y;return;}
int p=++tot;
ls[p]=merge(ls[x],ls[y]);
rs[p]=merge(rs[x],rs[y]);
sum[p]=sum[ls[p]]+sum[rs[p]]
return p;
}
这里是晋升者计数的\(code:\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<ctype.h>
#include<vector>
#define ll long long
using namespace std;
char buf[1<<20],*p1,*p2;
inline char gc()
{
// return getchar();
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}
template<typename T>
inline void read(T &x)
{
char tt;
bool flag=0;
while(!isdigit(tt=gc())&&tt!='-');
tt=='-'?(flag=1,x=0):(x=tt-'0');
while(isdigit(tt=gc())) x=x*10+tt-'0';
if(flag) x=-x;
}
const int maxn=1000002;
int n,tot;
int w[maxn],hashh[maxn];
int root[maxn<<2],sum[maxn<<2],ls[maxn<<2],rs[maxn<<2];
int ans[maxn];
vector<int>G[maxn];
void modify(int &p,int l,int r,int x,int d)
{
if(!p) p=++tot;
if(l==r) {sum[p]+=d;return;}
int mid=l+r>>1;
if(mid>=x) modify(ls[p],l,mid,x,d);
if(mid<x) modify(rs[p],mid+1,r,x,d);
sum[p]=sum[ls[p]]+sum[rs[p]];
}
void merge(int &x,int y)
{
if(!x||!y){x=x+y;return;}
sum[x]+=sum[y];
merge(ls[x],ls[y]);
merge(rs[x],rs[y]);
}
int query(int &p,int l,int r,int x,int y)
{
if(!p) p=++tot;
if(l>=x&&y>=r) return sum[p];
int mid=l+r>>1;
int tmp=0;
if(x<=mid) tmp+=query(ls[p],l,mid,x,y);
if(y>mid) tmp+=query(rs[p],mid+1,r,x,y);
return tmp;
}
void dfs(int x)
{
modify(root[x],1,n+1,w[x],1);
for(int i=G[x].size()-1;i>=0;i--)
{
int p=G[x][i];
dfs(p);
merge(root[x],root[p]);
}
ans[x]=query(root[x],1,n+1,w[x]+1,n+1);
}
int main()
{
read(n);
for(int i=1;i<=n;i++) read(w[i]),hashh[i]=w[i];
sort(hashh+1,hashh+1+n);
for(int i=1;i<=n;i++) w[i]=lower_bound(hashh+1,hashh+1+n,w[i])-hashh;
for(int i=2;i<=n;i++)
{
int x;
read(x);
G[x].push_back(i);
}
dfs(1);
// for(int i=1;i<=n;i++)
// printf("%d ",query(root[1],1,n,i,i));
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
简单好写,易于理解
转载于:https://www.cnblogs.com/KatouKatou/p/9859459.html
相关资源：各显卡算力对照表！
