首页 > 其他 > 详细

[Vani有约会]雨天的尾巴

时间:2019-09-23 18:32:44      阅读:93      评论:0      收藏:0      [点我收藏+]

题意

给一颗树,每次操作将一段路径上的点的某一个属性的属性值加一,求所有操作完成后每个点属性值最大的属性

思路

树链剖分+权值线段树(\(O(nlog^2n)\))

只有一次询问,这个条件很重要

对原树剖分完之后,考虑处理每一个区间,用差分的思想,将\(l\)对应的属性值加1,\(r+1\)对应的属性值建1,最后从1到n遍历所有点即可

但是怎么叠加属性值呢?前面的操作就是单点修改,要求的是最大值,显然值域线段树

Code

//会MLE不知道为什么。。 
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,ans[N];
int seg[N],rev[N],dep[N],son[N],fa[N],size[N],top[N],hfu;
int maxpos[N<<2],maxval[N<<2];//权值线段树 
struct Node
{
    int x,y;
    Node(int xx=0,int yy=0) {x=xx;y=yy;}
};
struct Edge
{
    int next,to;
}edge[N<<1];int head[N],cnt=1;
vector<Node> modi[N];
void add_edge(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}

void dfs1(int rt)
{
    dep[rt]=dep[fa[rt]]+1;
    for(int i=head[rt];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa[rt]) continue;
        fa[v]=rt;
        dfs1(v);
        size[rt]+=size[v];
        if(size[son[rt]]<size[v]) son[rt]=v;
    }
}
void dfs2(int rt)
{
    if(son[rt])
    {
        seg[son[rt]]=++hfu;
        rev[hfu]=son[rt];
        top[son[rt]]=top[rt];
        dfs2(son[rt]);
    }
    for(int i=head[rt];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa[rt]||v==son[rt]) continue;
        seg[v]=++hfu;
        rev[hfu]=v;
        top[v]=v;
        dfs2(v);
    }
}
void modif(int x,int y,int z)
{
    modi[x].push_back(Node(z,1));
    modi[y+1].push_back(Node(z,-1));
}
void modify_edge(int x,int y,int z)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])
        {
            swap(fx,fy);
            swap(x,y);
        }
        modif(seg[fx],seg[x],z);
        x=fa[fx];fx=top[x];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modif(seg[x],seg[y],z);
}
void pushup(int rt)
{
    if(maxval[rt<<1] >= maxval[rt<<1|1]) maxpos[rt]=maxpos[rt<<1],maxval[rt]=maxval[rt<<1];
    else maxpos[rt]=maxpos[rt<<1|1],maxval[rt]=maxval[rt<<1|1];
}
void modify(int rt,int l,int r,int x,int val)
{
    if(l==x&&r==x)
    {
        maxval[rt]+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(rt<<1,l,mid,x,val);
    else modify(rt<<1|1,mid+1,r,x,val);
    pushup(rt);
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        maxval[rt]=0;
        maxpos[rt]=l;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}

int main()
{
    read(n);read(m);
    for(int i=1;i<n;++i)
    {
        int x,y;
        read(x);read(y);
        add_edge(x,y);
        add_edge(y,x);
    }
    seg[1]=rev[1]=top[1]=hfu=1;
    dfs1(1); dfs2(1);
    build(1,1,100000);
    while(m--)
    {
        int x,y,z;
        read(x);read(y);read(z);
        modify_edge(x,y,z); 
    }
    for(int i=1;i<=n;++i)
    {
        for(vector<Node>::iterator it = modi[i].begin(); it != modi[i].end(); ++it)
        {
            int loc=it->x,v=it->y;
            modify(1,1,100000,loc,v);
        }
        ans[rev[i]]=(maxval[1] ? maxpos[1] : 0);
    }
    for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

[Vani有约会]雨天的尾巴

原文:https://www.cnblogs.com/Chtholly/p/11573799.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!