[模板]线段树合并

板子就是同时在两个线段树上走，然后合并信息，一般是权值线段树

板题：

luogu_P3605

求子树内有多少比此点权值大的（类似逆序对

用线段树合并做就是每个点维护权值线段树，每dfs到一个点就dfs并合并它所有儿子的线段树，查询答案

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int maxn=100009;
int n,tot,cnt;
struct node{
    int sum,l,r;
}t[maxn*30];
int ls[maxn*30],rs[maxn*30],root[maxn];
inline void upd(int x){
    t[x].sum=t[ls[x]].sum+t[rs[x]].sum;
}
void build(int &x,int l,int r,int pos){
    x=++tot;t[x].l=l;t[x].r=r;
    if(l==r){
        t[x].sum=1;return;
    }
    if(pos<=mid)build(ls[x],l,mid,pos);
    else build(rs[x],mid+1,r,pos);
    upd(x);
}
void change(int x,int l,int r,int pos){
    if(l==r){
        t[x].sum++;return;
    }
    if(pos<=mid)change(ls[x],l,mid,pos);
    else change(rs[x],mid+1,r,pos);
    upd(x);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].l==t[x].r){
        t[x].sum+=t[y].sum;
        return x;
    }
    ls[x]=merge(ls[x],ls[y]);
    rs[x]=merge(rs[x],rs[y]);
    upd(x);
    return x;
}
int query(int x,int l,int r,int L,int R){
    if(x==0)return 0;
    if(L<=l&&r<=R)return t[x].sum;
    int ans=0;
    if(L<=mid)ans+=query(ls[x],l,mid,L,R);
    if(R>mid)ans+=query(rs[x],mid+1,r,L,R);
    return ans;
}
int a[maxn],hsh[maxn],fa[maxn];
vector<int>e[maxn];
int ans[maxn];
void dfs(int x){
    int c=e[x].size();
    for(int i=0;i<c;i++){
        dfs(e[x][i]);
        root[x]=merge(root[x],root[e[x][i]]);
    }
    ans[x]=query(root[x],1,cnt,a[x]+1,cnt);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),hsh[i]=a[i];
    for(int i=2,x;i<=n;i++)scanf("%d",&x),e[x].pb(i);
    sort(hsh+1,hsh+1+n);
    cnt=unique(hsh+1,hsh+1+n)-hsh-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(hsh+1,hsh+1+cnt,a[i])-hsh,
    build(root[i],1,cnt,a[i]);
    dfs(1);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}

CF600E

一棵树有n个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号的和

同上题

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int maxn=100009;
int n,tot;
struct node{
    int mx;ll id;
}t[maxn*30];
int ls[maxn*30],rs[maxn*30];
inline void upd(int x){
    if(t[ls[x]].mx>t[rs[x]].mx)t[x].mx=t[ls[x]].mx,t[x].id=t[ls[x]].id;
    else if(t[ls[x]].mx<t[rs[x]].mx)t[x].mx=t[rs[x]].mx,t[x].id=t[rs[x]].id;
    else t[x].mx=t[ls[x]].mx,t[x].id=t[ls[x]].id+t[rs[x]].id;
}
void build(int &x,int l,int r,int pos){
    x=++tot;
    if(l==r){
        t[x].id=l;
        t[x].mx++;
        return;
    }
    if(pos<=mid)build(ls[x],l,mid,pos);
    else build(rs[x],mid+1,r,pos);
    upd(x);
}
void change(int x,int l,int r,int pos){
    if(l==r){
        t[x].mx++;
        return;
    }
    if(pos<=mid)change(ls[x],l,mid,pos);
    else change(rs[x],mid+1,r,pos);
    upd(x);
}
int merge(int x,int y,int l,int r){
    if(!x||!y)return x+y;
    if(l==r){
        t[x].mx+=t[y].mx;
        return x;
    }
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    upd(x);
    return x;
}
int root[maxn];
ll ans[maxn];
struct nod{
    int v,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add(int u,int v){
    e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void dfs(int x,int fa){
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].v==fa)continue;
        dfs(e[i].v,x);
        root[x]=merge(root[x],root[e[i].v],1,n);
    }
    ans[x]=t[root[x]].id;
}
int c[maxn];
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]),build(root[i],1,n,c[i]);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);add(u,v);add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
}