旅行(树链剖分+动态开点线段树)

佚名 6年前 (2018-09-25) 算法 1615人围观抢沙发百度已收录

旅行

https://www.luogu.org/problemnew/show/P3313

题目描述

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

为了方便，我们用不同的正整数代表各种宗教， 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依次表示城市数和事件数。

接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。接下来N-1行每行两个整数x，y表示一条双向道路。

接下来Q行，每行一个操作，格式如上所述。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

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

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

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

思路

对于每个信仰都要开一个线段树，但如果是用常规的方法写线段树会MLE，所以需要用动态开点的方法来写线段树

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<string>
  6 #include<cmath>
  7 #include<queue>
  8 #include<vector>
  9 #include<set>
 10 #define maxn 100005
 11 using namespace std;
 12 struct sair{
 13     int w,c;
 14 }city[maxn];
 15 struct Tree{
 16     int l,r,sum,Max;
 17 }tree[maxn*40];
 18 int root[maxn];
 19 vector<int>ve[maxn];
 20 int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn];
 21 int cnt,n;
 22 
 23 void pushup(int rt){
 24     tree[rt].sum=tree[tree[rt].l].sum+tree[tree[rt].r].sum;
 25     tree[rt].Max=max(tree[tree[rt].l].Max,tree[tree[rt].r].Max);
 26 }
 27 
 28 void add(int cur,int l,int r,int p,int v){
 29     if(l==r){
 30         tree[cur].sum=v;
 31         tree[cur].Max=v;
 32         return;
 33     }
 34     int mid=(l+r)/2;
 35     if(p<=mid){
 36         if(!tree[cur].l){
 37             tree[cur].l=++cnt;
 38         }
 39         add(tree[cur].l,l,mid,p,v);
 40     }
 41     else{
 42         if(!tree[cur].r){
 43             tree[cur].r=++cnt;
 44         }
 45         add(tree[cur].r,mid+1,r,p,v);
 46     }
 47     pushup(cur);
 48 }
 49 
 50 int querysum(int L,int R,int cur,int l,int r){
 51     if(!cur) return 0;
 52     if(L<=l&&R>=r){
 53         return tree[cur].sum;
 54     }
 55     int mid=(l+r)/2;
 56     int ans=0;
 57     if(L<=mid) ans+=querysum(L,R,tree[cur].l,l,mid);
 58     if(R>mid) ans+=querysum(L,R,tree[cur].r,mid+1,r);
 59     return ans;
 60 }
 61 
 62 int querymax(int L,int R,int cur,int l,int r){
 63     if(!cur) return 0;
 64     if(L<=l&&R>=r){
 65         return tree[cur].Max;
 66     }
 67     int mid=(l+r)/2;
 68     int ans=0;
 69     if(L<=mid) ans=max(ans,querymax(L,R,tree[cur].l,l,mid));
 70     if(R>mid) ans=max(ans,querymax(L,R,tree[cur].r,mid+1,r));
 71     return ans;
 72 }
 73 
 74 void dfs1(int now,int f,int deep){
 75     dep[now]=deep;
 76     siz[now]=1;
 77     fa[now]=f;
 78     int maxson=-1;
 79     for(int i=0;i<ve[now].size();i++){
 80         if(ve[now][i]==f) continue;
 81         dfs1(ve[now][i],now,deep+1);
 82         siz[now]+=siz[ve[now][i]];
 83         if(siz[ve[now][i]]>maxson){
 84             maxson=siz[ve[now][i]];
 85             son[now]=ve[now][i];
 86         }
 87     }
 88 }
 89 
 90 void dfs2(int now,int topp){
 91     id[now]=++cnt;
 92     top[now]=topp;
 93     if(!son[now]) return;
 94     dfs2(son[now],topp);
 95     for(int i=0;i<ve[now].size();i++){
 96         if(ve[now][i]==son[now]||ve[now][i]==fa[now]) continue;
 97         dfs2(ve[now][i],ve[now][i]);
 98     }
 99 }
100 
101 int sumRange(int x,int y,int type){
102     int ans=0;
103     while(top[x]!=top[y]){
104         if(dep[top[x]]<dep[top[y]]) swap(x,y);
105         ans+=querysum(id[top[x]],id[x],type,1,n);
106         x=fa[top[x]];
107     }
108     if(dep[x]>dep[y]) swap(x,y);
109     ans+=querysum(id[x],id[y],type,1,n);
110     return ans;
111 }
112 
113 int maxRange(int x,int y,int type){
114     int ans=0;
115     while(top[x]!=top[y]){
116         if(dep[top[x]]<dep[top[y]]) swap(x,y);
117         ans=max(ans,querymax(id[top[x]],id[x],type,1,n));
118         x=fa[top[x]];
119     }
120     if(dep[x]>dep[y]) swap(x,y);
121     ans=max(ans,querymax(id[x],id[y],type,1,n));
122     return ans;
123 }
124 
125 int main(){
126 
127     int q;
128     scanf("%d %d",&n,&q);
129     for(int i=1;i<=n;i++){
130         scanf("%d %d",&city[i].w,&city[i].c);
131     }
132     int x,y;
133     for(int i=1;i<n;i++){
134         scanf("%d %d",&x,&y);
135         ve[x].push_back(y);
136         ve[y].push_back(x);
137     }
138     cnt=0;
139     dfs1(1,0,1);
140     dfs2(1,1);
141     cnt=0;
142     for(int i=1;i<=n;i++){
143         if(!root[city[i].c]){
144             root[city[i].c]=++cnt;
145         }
146         add(root[city[i].c],1,n,id[i],city[i].w);
147     }
148     char pos[5];
149     for(int i=1;i<=q;i++){
150         scanf("%s %d %d",pos,&x,&y);
151         if(pos[1]=='S'){
152             printf("%d\n",sumRange(x,y,root[city[x].c]));
153         }
154         else if(pos[1]=='C'){
155             add(root[city[x].c],1,n,id[x],0);
156             city[x].c=y;
157             if(!root[city[x].c]){
158                 root[city[x].c]=++cnt;
159             }
160             add(root[city[x].c],1,n,id[x],city[x].w);
161         }
162         else if(pos[1]=='W'){
163             city[x].w=y;
164             if(!root[city[x].c]){
165                 root[city[x].c]=++cnt;
166             }
167             add(root[city[x].c],1,n,id[x],city[x].w);
168         }
169         else if(pos[1]=='M'){
170             printf("%d\n",maxRange(x,y,root[city[x].c]));
171         }
172     }
173 }