洛谷 P3313 [SDOI2014]旅行

我寻思着这东西哪里用了主席树了

KONO题面哒！

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，并记下了途中留宿过的城市的评级最大值。

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

数据范围

N，Q < =10^5 ， C < =10^5

数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时

刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

题意简述：一棵树上每个节点有两个权值w,c。每次有四种操作：1.更改某节点c值；2.更改某节点w值；3.求两节点路径中权值c与起始点c值相同的点的w值和；4.与上操作类似，求路径上最大值

单点修改，树上路径查值，一看就想到了倍增LCA暴力统计

（逃

首先发现需要求树上路径的数据并有修改操作，树剖会是一个很好的选择。(打一遍，调一年，爆零不花一分钱)

看到在查找区间和/最大值时会有一个\(C\)来限定我们的查找范围，我们想到可以暴力一点，开\(C\)棵线段树来记录每个区间中的数据。但是开成满树的话内存肯定升天，所以动态开点就好了。

对于1号操作，我们选择直接把第\(C\)颗树中的当前权值抹去，然后在更换后的线段树中加一个进去。

2号操作很水。

3，4号操作已包含在树剖中。

然后就做完了。

(我又把\(==\)写成\(=\)了,丢人)

KONO代码哒！

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct edge{
    int to,next;
}g[maxn*2];
int head[maxn],cnt;
void add(int from,int to)
{
    g[++cnt].next=head[from];
    g[cnt].to=to;
    head[from]=cnt;
}
int n,m;
int w[maxn],c[maxn];
int f[maxn];
int Dfn,dfn[maxn],dep[maxn];
int Top[maxn];
int root[maxn];
int id[maxn];
int zson[maxn];
int val[maxn];
struct node{
    int ls,rs;
    int sum,_max;
    int tag;
};
struct tree{
    node sum[maxn<<6];
    int tot;
    void pushup(int p)
    {
        sum[p].sum=sum[sum[p].ls].sum+sum[sum[p].rs].sum;
        sum[p]._max=max(sum[sum[p].ls]._max,sum[sum[p].rs]._max);
    }
    void era(int p)
    {
        sum[p].sum=sum[p]._max=0;
        sum[p].tag=1;
    }
    void pushdown(int p,int l,int r)
    {
        if(!sum[p].tag)return;
        if(sum[p].rs)era(sum[p].rs);
        if(sum[p].ls)era(sum[p].ls);
        return;
    }
    void ins(int x,int &p,int l,int r,int k)
    {
        if(!p)p=++tot;
        if(l==r){
            sum[p].sum=k;
            sum[p]._max=k;
            sum[p].tag=0;
            return;
        }
        pushdown(p,l,r);
        int mid=((l+r)>>1);
        if(mid>=x)ins(x,sum[p].ls,l,mid,k);
        else ins(x,sum[p].rs,mid+1,r,k);
        pushup(p);
        return;
    }
    void del(int x,int p,int l,int r)
    {
        if(l==r){
            era(p);
            return;
        }
        int mid=((l+r)>>1);
        pushdown(p,l,r);
        if(mid>=x){if(sum[p].ls)del(x,sum[p].ls,l,mid);}
        else if(sum[p].rs)del(x,sum[p].rs,mid+1,r);
        pushup(p);
    }
    int get_max(int x,int y,int p,int l,int r)
    {
        if(x<=l&&y>=r){
            return sum[p]._max;
        }
        int res=0;
        int mid=((l+r)>>1);
        pushdown(p,l,r);
        if(sum[p].ls)if(mid>=x)res=max(res,get_max(x,y,sum[p].ls,l,mid));
        if(sum[p].rs)if(mid<y)res=max(res,get_max(x,y,sum[p].rs,mid+1,r));
        return res;
    }
    int get_sum(int x,int y,int p,int l,int r)
    {
        if(x<=l&&y>=r){
            return sum[p].sum;
        }
        int res=0;
        int mid=((l+r)>>1);
        pushdown(p,l,r);
        if(sum[p].ls)if(mid>=x)res+=get_sum(x,y,sum[p].ls,l,mid);
        if(sum[p].rs)if(mid<y)res+=get_sum(x,y,sum[p].rs,mid+1,r);
        return res;
    }
    int q_max(int x,int y,int c)
    {
        int res=0;
        while(Top[x]!=Top[y]){
            if(dep[Top[x]]<dep[Top[y]])swap(x,y);
            res=max(res,get_max(id[Top[x]],id[x],root[c],1,n));
            x=f[Top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        res=max(res,get_max(id[x],id[y],root[c],1,n));
        return res;
    }
    int q_sum(int x,int y,int c)
    {
        int res=0;
        while(Top[x]!=Top[y]){
            if(dep[Top[x]]<dep[Top[y]])swap(x,y);
            res+=get_sum(id[Top[x]],id[x],root[c],1,n);
            x=f[Top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        res+=get_sum(id[x],id[y],root[c],1,n);
        return res;
    }
    
}tr;
int Size[maxn];
void dfs1(int x,int fr)
{
    dep[x]=dep[fr]+1;
    f[x]=fr;
    Size[x]=1;
    int _max=-1;
    for(int i=head[x];i;i=g[i].next)
    {
        int v=g[i].to;
        if(v==fr)continue;
        dfs1(v,x);
        Size[x]+=Size[v];
        if(Size[v]>_max){
            _max=Size[v];
            zson[x]=v;
        }
    }
}
int num;
void dfs2(int x,int fr,int top)
{
    id[x]=++num;
    val[id[x]]=w[x];
    Top[x]=top;
    if(!zson[x])return;
    dfs2(zson[x],x,top);
    for(int i=head[x];i;i=g[i].next)
    {
        int v=g[i].to;
        if((v==fr)||(v==zson[x]))continue;
        dfs2(v,x,v);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
    for(i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    for(i=1;i<=n;i++)
    {
        tr.ins(id[i],root[c[i]],1,n,w[i]);
    }
    for(i=1;i<=m;i++)
    {
        char ch[2];
        int a,b;
        cin>>ch>>a>>b;
        switch(ch[1]){
            case 'C':{
                tr.del(id[a],root[c[a]],1,n);
                c[a]=b;
                tr.ins(id[a],root[b],1,n,w[a]);
                break;
            }
            case 'W':{
                tr.ins(id[a],root[c[a]],1,n,b);
                w[a]=b;
                break;
            }
            case 'S':{
                int tmp=tr.q_sum(a,b,c[a]);
                printf("%d\n",tmp);
                break;
            }
            case 'M':{
                int tmp=tr.q_max(a,b,c[a]);
                printf("%d\n",tmp);
                break;
            }
        }
    }
}

今天看少前冬活剧情，不管是格里芬、铁血、还是军方那边都差点猛男落泪……

全程脑补UNICORN，内味儿甚浓……

看到那些为了自己理想牺牲的军人，我也不知道自己该不该说叶戈尔必死了……

什么？秃子洞有叶戈尔座驾？炮狙队满上！

什么？要机枪？告辞.jpg

洛谷 P3313 [SDOI2014]旅行

原文：https://www.cnblogs.com/cooper233/p/12215850.html