线段树合并的作用在于把子节点的信息直接合并在父节点身上来同时会覆盖子节点的信息来保证内存的正确性
一般作用于树上的差分操作和lca 结合起来如下
雨天的尾巴
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=100010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
int p[N][21],ans[N];
int d[N];
vector<int> g[N];
void dfs1(int u,int fa){ // 得到d 和 p数组
d[u] = d[fa] + 1;
p[u][0] = fa;
for(int i=1;i<=20;i++) p[u][i] = p[p[u][i-1]][i-1];
for(auto&v:g[u]){
if(v==fa) continue;
dfs1(v,u);
}
}
int lca(int a,int b){
if(d[a]<d[b]) swap(a,b);
while(d[a]>d[b])
a = p[a][(int)log2(d[a]-d[b])];
if(a==b) return a;
for(int j=(int)log2(d[a]);j>=0;j--)
if(p[a][j]!=p[b][j])
a=p[a][j],b=p[b][j];
return p[a][0];
}
struct code{
int l,r;
int pos;
int cnt;
}tr[81*N];
int rt[N];
int idx;
void pushup(int p){ // 哪一个救济粮最多
if(tr[tr[p].l].cnt>=tr[tr[p].r].cnt) tr[p].cnt = tr[tr[p].l].cnt,tr[p].pos = tr[tr[p].l].pos;
else tr[p].cnt = tr[tr[p].r].cnt,tr[p].pos = tr[tr[p].r].pos;
}
void change(int&p,int l,int r,int pos,int val){
if(!p) p = ++idx;
if(l==r){
tr[p].cnt += val;
tr[p].pos = l; // 他的位置就是l // 表示l这个种类的救济粮食+=val
return ;
}
int mid = l+r>>1;
if(pos<=mid) change(tr[p].l,l,mid,pos,val);
else change(tr[p].r,mid+1,r,pos,val);
pushup(p);
}
int merge(int p,int q,int l,int r){ //由于使用了差分所以说需要合并上来才是当前节点的真实情况
if(!p or !q) return p+q;
if(l==r){
tr[p].cnt += tr[q].cnt; // 表示种类 数量
tr[p].pos = l; // 表示这是数
return p;
}
int mid = l+r>>1;
tr[p].l=merge(tr[p].l,tr[q].l,l,mid);
tr[p].r=merge(tr[p].r,tr[q].r,mid+1,r);
pushup(p);
return p;
}
void dfs2(int u,int fa){
for(auto&v:g[u]){
if(v==fa) continue;
dfs2(v,u);
rt[u] = merge(rt[u],rt[v],1,N);
}
if(tr[rt[u]].cnt) ans[u] = tr[rt[u]].pos;
}
void solve(){
cin>>n>>m;
for(int i=1;i<n;i++){
int a,b; cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(1,0); // 目的是为了 可以求解lca
while(m--){
int a,b,c; cin>>a>>b>>c;
int t = lca(a,b);
change(rt[a],1,N,c,1),change(rt[b],1,N,c,1);
change(rt[t],1,N,c,-1); // 在权值线段树上加上某一段
if(p[t][0]) change(rt[p[t][0]],1,N,c,-1);
}
dfs2(1,0);
for(int i=1;i<=n;i++) cout << ans[i] << endl;
cout << endl;
return ;
}
signed main ()
{
ios// 不能有printf puts scanf
int t=1;
while(t--){
solve();
}
}
维护父节点和子节点的关系,如树上逆序对
树上逆序对
int t,n,m,idx;
struct code{
int l,r;
int cnt;
}tr[N*40];
vector<int> v;
int a[N],ans[N],root[N];
vector<int> g[N];
void pushup(int p){
tr[p].cnt = tr[tr[p].l].cnt + tr[tr[p].r].cnt;
}
void change(int& p,int l,int r,int v,int val){
if(!p) p = ++idx;
if(l==r){
tr[p].cnt += val;
return ;
}
int mid = l+r>>1;
if(v<=mid) change(tr[p].l,l,mid,v,val);
else change(tr[p].r,mid+1,r,v,val);
pushup(p);
}
int query(int& p,int l,int r,int L,int R){
if(!p) return 0;
if(L <= l and r <= R) return tr[p].cnt;
int mid = l+r>>1;
int res = 0;
if(L<=mid) res+=query(tr[p].l,l,mid,L,R);
if(R>mid) res+=query(tr[p].r,mid+1,r,L,R);
return res;
}
int merge(int p,int q,int l,int r){
if(!p or !q) return p+q;
if(l==r){
tr[p].cnt += tr[q].cnt;
return p;
}
int mid = l+r>>1;
tr[p].l=merge(tr[p].l,tr[q].l,l,mid);
tr[p].r=merge(tr[p].r,tr[q].r,mid+1,r);
pushup(p);
return p;
}
void dfs(int u,int fa){
for(auto&v:g[u]){
if(v==fa) continue;
dfs(v,u);
root[u]=merge(root[u],root[v],1,m);
}
ans[u]=query(root[u],1,m,a[u]+1,m);
change(root[u],1,m,a[u],1);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
m=v.size();
auto find = [&](int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
};
for(int i=1;i<=n;i++) a[i]=find(a[i]);
for(int i=2;i<=n;i++){
int x; cin>>x;
g[x].push_back(i);
g[i].push_back(x);
}
dfs(1,-1);
for(int i=1;i<=n;i++) cout << ans[i] << endl;
return ;
}