[BZOJ3531/Luogu3313][Sdoi2014]旅行(树链剖分,线段树)

发布于 2018-02-04  73 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3531/Luogu3313][Sdoi2014]旅行(树链剖分,线段树)

Description

S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便,我们用不同的正整数代表各种宗教, S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级,旅行者们常会记下途中(包括起点和终点)留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件:
”CC x c”:城市x的居民全体改信了c教;
”CW x w”:城市x的评级调整为w;
”QS x y”:一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级总和;
”QM x y”:一位旅行者从城市x出发,到城市y,并记下了途中留宿过
的城市的评级最大值。
由于年代久远,旅行者记下的数字已经遗失了,但记录开始之前每座城市的信仰与评级,还有事件记录本身是完好的。请根据这些信息,还原旅行者记下的数字。为了方便,我们认为事件之间的间隔足够长,以致在任意一次旅行中,所有城市的评级和信仰保持不变。

Http

BZOJ
Luogu

Tag

树链剖分,线段树

解决思路

比价好想的就是树链剖分后对每一种宗教单独开一棵线段树维护,这样的话就可以直接对每一种宗教查询了。
但空间是开不下的,考虑到其实我们只要用到其中的部分空间,所以可以动态地开线段树的点,这样就可以了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100010;
const int inf=2147483647;

class SegData
{
public:
    int ls,rs;
    ll sum,mx;
};

int n,Q,nodecnt;
int Color[maxN],root[maxN],Val[maxN];
SegData S[maxN*100];
int Fa[maxN],Depth[maxN],Top[maxN],Hson[maxN],Size[maxN];
int idcnt=0,Id[maxN];
int edgecnt=-1,Head[maxN],Next[maxN*2],V[maxN*2];

void dfs1(int u,int fa);//树链剖分
void dfs2(int u,int top);
void Update(int now);
void Modify(int &now,int l,int r,int pos,int val);//线段树单点修改
ll QSum(int u,int v);//路径查询
ll QMax(int u,int v);
ll SSum(int now,int l,int r,int ql,int qr);//线段树查询
ll SMax(int now,int l,int r,int ql,int qr);

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&Q);
    for (int i=1;i<=n;i++) scanf("%d%d",&Val[i],&Color[i]);
    for (int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
        edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;V[edgecnt]=u;
    }
    Depth[1]=1;
    dfs1(1,1);
    dfs2(1,1);
    for (int i=1;i<=n;i++) Modify(root[Color[i]],1,n,Id[i],Val[i]);
    char opt[10];
    while (Q--)
    {
        scanf("%s",opt);
        if ((opt[0]=='C')&&(opt[1]=='C'))
        {
            int city,col;scanf("%d%d",&city,&col);
            Modify(root[Color[city]],1,n,Id[city],0);
            Modify(root[col],1,n,Id[city],Val[city]);
            Color[city]=col;
        }
        if ((opt[0]=='C')&&(opt[1]=='W'))
        {
            int city,val;scanf("%d%d",&city,&val);
            Val[city]=val;
            Modify(root[Color[city]],1,n,Id[city],val);
        }
        if ((opt[0]=='Q')&&(opt[1]=='S'))
        {
            int u,v;scanf("%d%d",&u,&v);
            printf("%lld\n",QSum(u,v));
        }
        if ((opt[0]=='Q')&&(opt[1]=='M'))
        {
            int u,v;scanf("%d%d",&u,&v);
            printf("%lld\n",QMax(u,v));
        }
    }
    return 0;
}

void dfs1(int u,int fa)
{
    Size[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            Fa[V[i]]=u;Depth[V[i]]=Depth[u]+1;
            dfs1(V[i],u);
            if (Size[V[i]]>Size[Hson[u]]) Hson[u]=V[i];
            Size[u]+=Size[V[i]];
        }
    return;
}

void dfs2(int u,int top)
{
    Top[u]=top;
    Id[u]=++idcnt;
    if (Hson[u]==0) return;
    dfs2(Hson[u],top);
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((V[i]!=Fa[u])&&(V[i]!=Hson[u]))
            dfs2(V[i],V[i]);
    return;
}

void Update(int now)
{
    int ls=S[now].ls,rs=S[now].rs;
    S[now].sum=S[ls].sum+S[rs].sum;
    S[now].mx=max(S[ls].mx,S[rs].mx);
    return;
}

void Modify(int &now,int l,int r,int pos,int val)
{
    if (now==0) now=++nodecnt;
    if (l==r)
    {
        S[now].sum=S[now].mx=val;
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) Modify(S[now].ls,l,mid,pos,val);
    else Modify(S[now].rs,mid+1,r,pos,val);
    Update(now);
    return;
}

ll QSum(int u,int v)
{
    ll ret=0,col=Color[v];
    while (Top[u]!=Top[v])
    {
        if (Depth[Top[u]]<Depth[Top[v]]) swap(u,v);
        ret=ret+SSum(root[col],1,n,Id[Top[u]],Id[u]);
        u=Fa[Top[u]];
    }
    if (Depth[u]>Depth[v]) swap(u,v);
    ret=ret+SSum(root[col],1,n,Id[u],Id[v]);
    return ret;
}

ll QMax(int u,int v)
{
    ll ret=0,col=Color[v];
    while (Top[u]!=Top[v])
    {
        if (Depth[Top[u]]<Depth[Top[v]]) swap(u,v);
        ret=max(ret,SMax(root[col],1,n,Id[Top[u]],Id[u]));
        u=Fa[Top[u]];
    }
    if (Depth[u]>Depth[v]) swap(u,v);
    ret=max(ret,SMax(root[col],1,n,Id[u],Id[v]));
    return ret;
}

ll SSum(int now,int l,int r,int ql,int qr)
{
    if (now==0) return 0;
    if ((l==ql)&&(r==qr)) return S[now].sum;
    int mid=(l+r)>>1;
    if (qr<=mid) return SSum(S[now].ls,l,mid,ql,qr);
    else if (ql>=mid+1) return SSum(S[now].rs,mid+1,r,ql,qr);
    else return SSum(S[now].ls,l,mid,ql,mid)+SSum(S[now].rs,mid+1,r,mid+1,qr);
}

ll SMax(int now,int l,int r,int ql,int qr)
{
    if (now==0) return 0;
    if ((l==ql)&&(r==qr)) return S[now].mx;
    int mid=(l+r)>>1;
    if (qr<=mid) return SMax(S[now].ls,l,mid,ql,qr);
    else if (ql>=mid+1) return SMax(S[now].rs,mid+1,r,ql,qr);
    else return max(SMax(S[now].ls,l,mid,ql,mid),SMax(S[now].rs,mid+1,r,mid+1,qr));
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3531/Luogu3313][Sdoi2014]旅行(树链剖分,线段树)


HNCJ OIer