【bzoj3531】[Sdoi2014]旅行

2015.04.14 18:53 Tue | 3次阅读 | 旧日oi | 固定链接 | 源码

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,并记下了途中留宿过
的城市的评级最大值。
由于年代久远,旅行者记下的数字已经遗失了,但记录开始之前每座城市的信仰与评级,还有事件记录本身是完好的。请根据这些信息,还原旅行者记下的数字。    为了方便,我们认为事件之间的间隔足够长,以致在任意一次旅行中,所有城市的评级和信仰保持不变。

Input

    输入的第一行包含整数N,Q依次表示城市数和事件数。
接下来N行,第i+l行两个整数Wi,Ci依次表示记录开始之前,城市i的
评级和信仰。
接下来N-1行每行两个整数x,y表示一条双向道路。
接下来Q行,每行一个操作,格式如上所述。

Output

    对每个QS和QM事件,输出一行,表示旅行者记下的数字。

Sample Input

5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4

Sample Output

8
9
11
3

HINT

N,Q < =10^5    , C < =10^5
数据保证对所有QS和QM事件,起点和终点城市的信仰相同;在任意时
刻,城市的评级总是不大于10^4的正整数,且宗教值不大于C。

题解

比较裸的树链剖分,因为宗教只有10^5种,所以给每种建立个动态开点的线段树就行了,内存很良心……线段树的写法和我平时的不太一样,还有点不习惯,但是也不影响什么了……当初觉得好神的线段树跟现在学的东西相比好像弱了不少……突然想起一句歌词:
经过老伯的家
篮框变得好高
爬过的那棵树
又何时变得渺小
过去的成绩现在觉得不值一提,过去无法达到的地方现在仍无法企及……
我这是怎么了…………………………
差点忘了贴代码就发出去了……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,q,cnt;
int c[maxn],v[maxn];
int root[maxn],siz[maxn],fa[maxn],son[maxn],top[maxn],rank[maxn],dep[maxn];
struct edge{
    int to;
    int next;
}e[maxn<<1];
int h[maxn],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
void dfs1(int u,int f,int d)
{
    siz[u]=1;fa[u]=f;son[u]=-1;dep[u]=d;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f)
    {
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;rank[u]=++cnt;
    if(son[u]!=-1) dfs2(son[u],tp);
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=fa[u]&&v!=son[u]) dfs2(v,v);
}
struct segment_tree{
    int root[maxn*10],l[maxn*200],r[maxn*200],mx[maxn*200],sum[maxn*200],tot;
    #define ls l[x]
    #define rs r[x]
    void pushup(int x)
    {
        sum[x]=sum[ls]+sum[rs];
        mx[x]=max(mx[ls],mx[rs]);
    }
    void update(int &x,int pos,int v,int L,int R)
    {
        if(!x) x=++tot;
        if(L==R) 
        {
            sum[x]=mx[x]=v;
            return;
        }
        int mid=(L+R)>>1;
        if(pos<=mid) update(ls,pos,v,L,mid);
        else update(rs,pos,v,mid+1,R);
        pushup(x);
    }
    int query(int x,int st,int ed,int L,int R,int kind)
    {
        if(!x)return 0;
        if(st<=L&&ed>=R) return kind?mx[x]:sum[x];
        int mid=(L+R)>>1;
        int ret=0;
        if(st<=mid)  ret=query(ls,st,ed,L,mid,kind);
        if(ed>mid) 
        {
            if(kind) ret=max(ret,query(rs,st,ed,mid+1,R,kind));
            else ret+=query(rs,st,ed,mid+1,R,kind);
        }
        return ret;
    }
    int get_ans(int rt,int x,int y,int kind)
    {
        int ret=0;
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            if(kind) ret=max(ret,query(rt,rank[top[x]],rank[x],1,n,1));
            else ret+=query(rt,rank[top[x]],rank[x],1,n,0);
            x=fa[top[x]];
        }
        if(dep[x]<dep[y]) swap(x,y);
        if(kind) ret=max(ret,query(rt,rank[y],rank[x],1,n,1));
        else ret+=query(rt,rank[y],rank[x],1,n,0);
        return ret;
    }
}st;
int main()
{
    n=read();q=read();
    for(int i=1;i<=n;i++) v[i]=read(),c[i]=read();
    for(int u,t,i=1;i<n;i++)
    {
        u=read();t=read();
        ae(u,t);ae(t,u);
    }
    dfs1(1,0,0);
    dfs2(1,1);
    for(int i=1;i<=n;i++) 
    st.update(st.root[c[i]],rank[i],v[i],1,n);
    char s[10];
    for(int x,y,i=1;i<=q;i++)
    {
        scanf("%s",s);x=read();y=read();
        if(s[0]=='C')
        {
            if(s[1]=='C') 
            {
                st.update(st.root[c[x]],rank[x],0,1,n);
                st.update(st.root[c[x]=y],rank[x],v[x],1,n);
            }
            else st.update(st.root[c[x]],rank[x],v[x]=y,1,n);
        }
        else
        {
            if(s[1]=='S') printf("%d\n",st.get_ans(st.root[c[x]],x,y,0));
            else printf("%d\n",st.get_ans(st.root[c[x]],x,y,1));
        }
    }
    return 0;
}```