0.1

诶嘿，好像鸽了太久了，博客的访问速度都明显变慢了ヽ(゜▽゜　)－C<(/;◇;)/~

1.1 线段树合并

当你有两个数组时，并且希望快速合并两个数组时，最朴实的想法莫过于：枚举、合并，吧。

for(int i=1;i<=n;++i) a[i]+=b[i];

复杂度显然是\(O(n)\)的。那么对于一个空间复杂度为\(O(n)\)的数组，时间复杂度似乎很难再低于\(O(n)\)了，那..线段树合并的复杂度是..\(O(m\log n)\)

Tips: 线段树合并时，需要佩套使用“动态开点”。

有两棵线段树\(a\)，\(b\)，合并后的树为\(c\)。对于相同位置\(id\)，如果任意一棵树不存在这个结点，那么\(c\)的对应位置就可以直接复制为另一棵树的结点；

    if(!lson[idx]||!lson[idy]) lson[idx]=(lson[idx]|lson[idy]);
    else ...;
    if(!rson[idx]||!rson[idy]) rson[idx]=(rson[idx]|rson[idy]);
    else ...;

如果两棵树共同拥有这个结点呢？那就老老实实的递归下去。

    if(!lson[idx]||!lson[idy]) ...;
    else merge(lson[idx],lson[idy],l,mid);
    if(!rson[idx]||!rson[idy]) ...;
    else merge(rson[idx],rson[idy],mid+1,r);

递归的尽头是什么？自然是当\(l=r\)时。此时，我们再赋值即可。

    if(l==r) {num[idx]+=num[idy]; return;}

完整起来就是这样的：

void merge(int idx,int idy,int l,int r){
    if(l==r) {num[idx]+=num[idy]; return;}
    int mid=(l+r)>>1;
    if(!lson[idx]||!lson[idy]) lson[idx]=(lson[idx]|lson[idy]);
    else merge(lson[idx],lson[idy],l,mid);
    if(!rson[idx]||!rson[idy]) rson[idx]=(rson[idx]|rson[idy]);
    else merge(rson[idx],rson[idy],mid+1,r);
}

1.2 线段树合并的复杂度分析

最劣情况

emm..感觉好没必要啊..有可能白忙了一大通，结果最后还是递归到了尽头。复杂度白添了一个\(O(\log n)\)

是的，在最劣情况下，复杂度的确变成了\(O(n\log n)\)。但是想想，这其实只是常数级别的劣化；如果时间不吃紧的话，这个劣化仍然是可以接受的。

最优情况

但是..具体而言，什么情况下，单次合并才会退化到\(O(\log n)\)：当两个结点都曾经被赋过值时，才会一直递归下去。所以正确的复杂度其实是：\((m \log n)\) ，\(m\)指两数组中均被赋值的个数。

那么如果\(a\)和\(b\)都是比较稀疏的数组:\(m\)是很小的，总复杂度就会变小。当两个数组几乎没有被改变过时，复杂度可以直逼常数级别！ヾ(≧▽≦*)o

平均情况

实践表明，在值域\(O(10^5)\)，插入\(O(10^5)\)时，时限\(1s\)还是不虚的。合并\(n\)个长度为\(n\)的数组时可以认为是\(O(n\log n)\)的。

2.1 [Vani有约会]雨天的尾巴

P4556 [Vani有约会]雨天的尾巴

当你自认为掌据线段树合并时，可以用这道题来检验一下。

其实说来也简单：对于每一种补给,在\(x\)和\(y\)上\(+1\)，在\(lca(x,y)\)和\(fa[lca(x,y)]\)上\(-1\)；然后用线段树合并，利用一下线段树的强大功能顺便维护一下最多补给编号即可。

注意事项：

（1） 将\(b\)合并到\(a\)后，\(a\)和\(b\)的底端结单合并起来了。因此再次更改\(a\)时，\(b\)也受到了牵连。因此记得实时更新答案

(2) 由于线段树需要动态开点，因此注意当前处理的是否被拓展过

if(!id) id++;

#include <bits/stdc++.h>
using namespace std;
#define lor(a,b,c) for(register int a=b;a<=c;++a)
#define ror(a,b,c) for(register int a=c;a>=b;--a)
#define tor(a,b) for(register int a=head[b];a;a=nxt[a])

const int MAXN=1e5+5,MAXM=1e5+5,TOP=1e5,MAXD=8e6+5;

int n,m;
int ecnt,head[MAXN],edge[MAXN<<1],nxt[MAXN<<1];
int fa[MAXN][17],dep[MAXN];
int x[MAXM],y[MAXM],z[MAXM],lca[MAXM];
int tot,root[MAXN],lson[MAXD],rson[MAXD],num[MAXD],max_num[MAXD],max_id[MAXD];
int ans[MAXN];

inline void insert(int,int,int);
void dfs_init(int,int);
inline int get_lca(int a,int b);
inline void updata(int);
int query_num(int,int,int,int);
void modify(int&,int,int,int,int);
void merge(int,int,int,int);
void dfs(int,int);

int main(){
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);

    lor(i,1,n-1){
        int a,b; scanf("%d%d",&a,&b);
        insert(a,b,++ecnt); insert(b,a,++ecnt);
    }
    dfs_init(1,1);
    lor(i,1,m){
        scanf("%d%d%d",&x[i],&y[i],&z[i]); lca[i]=get_lca(x[i],y[i]);
        modify(root[x[i]],1,TOP,z[i],1); modify(root[y[i]],1,TOP,z[i],1);
        modify(root[lca[i]],1,TOP,z[i],-1);
        if(fa[lca[i]][0]!=lca[i]) modify(root[fa[lca[i]][0]],1,TOP,z[i],-1);
    }

    dfs(1,1);
    lor(i,1,n) printf("%d\n",ans[i]);

    return 0;
}

inline void insert(int from,int to,int id){
    nxt[id]=head[from]; head[from]=id; edge[id]=to;
}

void dfs_init(int u,int f){
    fa[u][0]=f; dep[u]=dep[f]+1;
    lor(i,1,15) fa[u][i]=fa[fa[u][i-1]][i-1];
    tor(i,u){
        int v=edge[i]; if(v==f) continue;
        dfs_init(v,u);
    }
}

inline int get_lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    ror(i,0,15) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i]; if(a==b) return a;
    ror(i,0,15) if(fa[a][i]!=fa[b][i]) {a=fa[a][i]; b=fa[b][i];} return fa[a][0];
}

inline void updata(int id){
    if(!lson[id]||!rson[id])
        {max_num[id]=max_num[lson[id]|rson[id]]; max_id[id]=max_id[lson[id]|rson[id]];
    }
    if(max_num[lson[id]]>=max_num[rson[id]]){
        max_num[id]=max_num[lson[id]]; max_id[id]=max_id[lson[id]];
    }
    else{
        max_num[id]=max_num[rson[id]]; max_id[id]=max_id[rson[id]];
    }
}

int query_num(int id,int l,int r,int p){
    if(!id) return 0;
    if(l==r) return num[id];
    int mid=(l+r)>>1;
    if(p<=mid) return query_num(lson[id],l,mid,p);
    else return query_num(rson[id],mid+1,r,p);
}

void modify(int &id,int l,int r,int p,int k){
    if(!id) id=++tot;
    if(l==r) {num[id]+=k; max_num[id]=num[id]; max_id[id]=num[id]>0?l:0; return;}
    int mid=(l+r)>>1;
    if(p<=mid) modify(lson[id],l,mid,p,k);
    else modify(rson[id],mid+1,r,p,k);
    updata(id);
}


void merge(int idx,int idy,int l,int r){
    if(l==r) {num[idx]+=num[idy]; max_num[idx]=num[idx]; max_id[idx]=num[idx]>0?l:0; return;}
    int mid=(l+r)>>1;
    if(!lson[idx]||!lson[idy]) lson[idx]=(lson[idx]|lson[idy]);
    else merge(lson[idx],lson[idy],l,mid);
    if(!rson[idx]||!rson[idy]) rson[idx]=(rson[idx]|rson[idy]);
    else merge(rson[idx],rson[idy],mid+1,r);
    updata(idx);
}

void dfs(int u,int f){
    tor(i,u){
        int v=edge[i]; if(v==f) continue;
        dfs(v,u);
        if(!root[u]) root[u]=++tot;
        merge(root[u],root[v],1,TOP);
    }
    ans[u]=max_id[root[u]];
}

2.2 天天爱跑步

P1600 天天爱跑步

据说用线段树合并可以得到\(80pts\)，但并没有写过