BZOJ3307：雨天的尾巴

浅谈线段树合并：https://www.cnblogs.com/AKMer/p/10251001.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=3307

每次放物资就树上差分一下，然后用线段树维护差分值\(max\)，自底向上合并统计答案即可。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(nlogn)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e5+5;

int n,m,tot,cnt;

int f[maxn][18];

int rt[maxn],dep[maxn],ans[maxn];

int X[maxn],Y[maxn],Z[maxn],tmp[maxn];

int now[maxn],pre[maxn*2],son[maxn*2];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

namespace T {

    int tot;

    int ls[maxn*50],rs[maxn*50];

    struct tree_node {int cnt,id;}tree[maxn*50];

    tree_node calc(tree_node a,tree_node b) {

        if(a.cnt>b.cnt)return a;

        if(a.cnt<b.cnt)return b;

        if(a.id<b.id)return a;

        return b;

    }

    void update(int p) {

        tree[p]=calc(tree[ls[p]],tree[rs[p]]);

        if(!tree[p].cnt)tree[p].id=0;

    }

    void change(int &p,int l,int r,int pos,int v) {

        if(!p)p=++tot;

        if(l==r) {

            if(!tree[p].id)tree[p].id=l;

            tree[p].cnt+=v;return;

        }

        int mid=(l+r)>>1;

        if(pos<=mid)change(ls[p],l,mid,pos,v);

        else change(rs[p],mid+1,r,pos,v);

        update(p);

    }

    int merge(int a,int b) {

        if(!a||!b)return a+b;

        if(!ls[a]&&!rs[a]&&!ls[b]&&!rs[b]) {

            tree[a].cnt+=tree[b].cnt;

            return a;

        }

        ls[a]=merge(ls[a],ls[b]);

        rs[a]=merge(rs[a],rs[b]);

        update(a);return a;

    }

}

void add(int a,int b) {

    pre[++tot]=now[a];

    now[a]=tot,son[tot]=b;

}

void dfs(int fa,int u) {

    dep[u]=dep[fa]+1;

    f[u][0]=fa;

    for(int i=1;i<18;i++)

        f[u][i]=f[f[u][i-1]][i-1];

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(v!=fa)dfs(u,v);

}

void make_ans(int fa,int u) {

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(v!=fa)make_ans(u,v),rt[u]=T::merge(rt[u],rt[v]);

    if(!T::tree[rt[u]].cnt)ans[u]=0;//这里要加特判是因为有可能线段树只有一个结点并且加成了0

    else ans[u]=T::tree[rt[u]].id;

}

int lca(int a,int b) {

    if(dep[a]<dep[b])swap(a,b);

    for(int i=17;~i;i--)

        if(dep[f[a][i]]>=dep[b])

            a=f[a][i];

    if(a==b)return a;

    for(int i=17;~i;i--)

        if(f[a][i]!=f[b][i])

            a=f[a][i],b=f[b][i];

    return f[a][0];

}

int main() {

    n=read(),m=read();

    for(int i=1;i<n;i++) {

        int a=read(),b=read();

        add(a,b),add(b,a);

    }

    dfs(0,1);

    for(int i=1;i<=m;i++)

        X[i]=read(),Y[i]=read(),tmp[i]=Z[i]=read();

    sort(tmp+1,tmp+m+1);

    cnt=unique(tmp+1,tmp+m+1)-tmp-1;

    for(int i=1;i<=m;i++)

        Z[i]=lower_bound(tmp+1,tmp+cnt+1,Z[i])-tmp;

    for(int i=1;i<=m;i++) {

        int x=X[i],y=Y[i],z=Z[i];

        int fa=lca(x,y);

        T::change(rt[x],1,cnt,z,1);

        T::change(rt[y],1,cnt,z,1);

        T::change(rt[fa],1,cnt,z,-1);

        T::change(rt[f[fa][0]],1,cnt,z,-1);

    }

    make_ans(0,1);

    for(int i=1;i<=n;i++)

        printf("%d\n",tmp[ans[i]]);

    return 0;

}

巴特西

BZOJ3307：雨天的尾巴

最新文章

热门文章