正文 

当前位置： 首页 > 程序 > java教程

bzoj3307雨天的尾巴（可持久化线段树合并）(代码片段)

blog-dr-j blog-dr-j     2022-12-28     495

关键词：

题目大意：

一颗树，想要在树链上添加同一物品，问最后每个点上哪个物品最多。

解题思路：

假如说物品数量少到可以暴力添加，且树点极少，我们怎么做。

首先在一个树节点上标记出哪些物品有多少，寻找道路上的节点暴力添加。

而如果节点比较多，我们使用树上差分u+1，v+1,lca-1,fa[lca]-1向上求和就得到了答案

而颜色较多呢，和刚才唯一不同就在于向上求和时不要用数组，用线段树合并就好了（记录线段树区间的最大值与最大位置）

在神犇博客那里看到了废点的回收^_^

代码:

  1 #include<queue>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define lll tr[spc].ls
  6 #define rrr tr[spc].rs
  7 const int maxin=1000000000;
  8 struct pnt
  9     int fa[20];
 10     int hd;
 11     int gd;
 12     int dp;
 13     int wgt;
 14     int ans;
 15     int prp;
 16     int root;
 17 p[110000];
 18 struct ent
 19     int twd;
 20     int lst;
 21 e[220000];
 22 struct ljt
 23     int twd;
 24     int lst;
 25     int vls;
 26 el[420000];
 27 struct trnt
 28     int ls;
 29     int rs;
 30     int val;
 31     int mpl;
 32 tr[2000000],org;
 33 int bin[2000000];
 34 int top;
 35 int siz;
 36 int cnt1;
 37 int cnt2;
 38 int n,m;
 39 void adde(int f,int t)
 40 
 41     cnt1++;
 42     e[cnt1].twd=t;
 43     e[cnt1].lst=p[f].hd;
 44     p[f].hd=cnt1;
 45     return ;
 46 
 47 void addc(int pt,int c,int v)
 48 
 49     cnt2++;
 50     el[cnt2].twd=c;
 51     el[cnt2].lst=p[pt].gd;
 52     el[cnt2].vls=v;
 53     p[pt].gd=cnt2;
 54     return ;
 55 
 56 namespace Sgt
 57     void P_delete(int spc)
 58     
 59         bin[++top]=spc;
 60         tr[spc]=org;
 61         return ;
 62     
 63     void P_destory(int spc1,int spc2)
 64     
 65         P_delete(spc1);
 66         P_delete(spc2);
 67         return ;
 68     
 69     int P_new(void)
 70     
 71         if(top)
 72             return bin[top--];
 73         return ++siz;
 74     
 75     void pushup(int spc)
 76     
 77         if(tr[lll].val>=tr[rrr].val)
 78             tr[spc].val=tr[lll].val,tr[spc].mpl=tr[lll].mpl;
 79         else
 80             tr[spc].val=tr[rrr].val,tr[spc].mpl=tr[rrr].mpl;
 81         return ;
 82     
 83     int P_merge(int spc1,int spc2,int l,int r)
 84     
 85         if(!spc1||!spc2)
 86             return spc1+spc2;
 87         int spc=P_new();
 88         if(l==r)
 89         
 90             tr[spc].val=tr[spc1].val+tr[spc2].val;
 91             tr[spc].mpl=l;
 92             P_destory(spc1,spc2);
 93             return spc;
 94         
 95         int mid=(l+r)>>1;
 96         tr[spc].ls=P_merge(tr[spc1].ls,tr[spc2].ls,l,mid);
 97         tr[spc].rs=P_merge(tr[spc1].rs,tr[spc2].rs,mid+1,r);
 98         pushup(spc);
 99         P_destory(spc1,spc2);
100         return spc;
101     
102     void Update(int l,int r,int &spc,int pos,int v)
103     
104         if(!spc)
105             spc=P_new();
106         if(l==r)
107         
108             tr[spc].val+=v;
109             tr[spc].mpl=(tr[spc].val)?l:0;
110             return ;
111         
112         int mid=(l+r)>>1;
113         if(pos<=mid)
114             Update(l,mid,tr[spc].ls,pos,v);
115         else
116             Update(mid+1,r,tr[spc].rs,pos,v);
117         pushup(spc);
118         if(!tr[spc].val)
119             tr[spc].mpl=0;
120         return ;
121     
122 
123 void Basic_dfs(int x,int f)
124 
125     p[x].dp=p[f].dp+1;
126     p[x].fa[0]=f;
127     for(int i=1;i<=19;i++)
128         p[x].fa[i]=p[p[x].fa[i-1]].fa[i-1];
129     p[x].wgt=1;
130     for(int i=p[x].hd;i;i=e[i].lst)
131     
132         int to=e[i].twd;
133         if(to==f)
134             continue;
135         Basic_dfs(to,x);
136         p[x].wgt+=p[to].wgt;
137     
138     return ;
139 
140 void Ans_dfs(int x,int f)
141 
142     for(int i=p[x].hd;i;i=e[i].lst)
143     
144         int to=e[i].twd;
145         if(to==f)
146             continue;
147         Ans_dfs(to,x);
148     
149     for(int i=p[x].gd;i;i=el[i].lst)
150     
151         int clr=el[i].twd;
152         Sgt::Update(1,maxin,p[x].root,clr,el[i].vls);
153     
154     p[x].ans=tr[p[x].root].mpl;
155     p[f].root=Sgt::P_merge(p[f].root,p[x].root,1,maxin);
156 
157 int Lca(int x,int y) 
158 
159     if(p[x].dp<p[y].dp)
160         std::swap(x,y);
161     for(int i=19;i>=0;i--)
162         if(p[p[x].fa[i]].dp>=p[y].dp)
163             x=p[x].fa[i];
164     if(x==y)
165         return x;
166     for(int i=19;i>=0;i--)
167         if(p[x].fa[i]!=p[y].fa[i])
168             x=p[x].fa[i],y=p[y].fa[i];
169     return p[x].fa[0];
170 
171 int main()
172 
173     scanf("%d%d",&n,&m);
174     for(int i=1;i<n;i++)
175     
176         int a,b;
177         scanf("%d%d",&a,&b);
178         adde(a,b);
179         adde(b,a);
180     
181     Basic_dfs(1,1);
182     for(int i=1;i<=m;i++)
183     
184         int x,y,z;
185         scanf("%d%d%d",&x,&y,&z);
186         addc(x,z,1);
187         addc(y,z,1);
188         int lca=Lca(x,y);
189         addc(lca,z,-1);
190         if(lca!=1)
191             addc(p[lca].fa[0],z,-1);
192     
193     Ans_dfs(1,1);
194     for(int i=1;i<=n;i++)
195         printf("%d
",p[i].ans);
196     return 0;
197

 

bzoj3307雨天的尾巴

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3307【题解】这什么垃圾题啊卡空间卡时间卡栈然后我会了一种新姿势：人工栈（好像也不难啊喂）我们发现对于每种物品，只需要在u这地方的权值线段树上+1，v的权值线段树上+1，LC... 查看详情

bzoj3307雨天的尾巴

题目链接：传送门题目大意：中文题，略题目思路：网上有题解说是合并线段树的，但是太难蒟蒻不会，只能用树剖求解　　　　　如果不是树而是一维数组我们会怎么解？   　　　　　当然是利用前缀和思想标记（... 查看详情

bzoj-3307:雨天的尾巴

咱可以差分一下，把$u-v$这条路径上的$z$都加$1$变成$u$和$v$的$z$加$1$，$lca$和$fa_{lca}$的$z$减$1$。用线段树实现最大值的查询，最后$dfs$自底向上一路合并并查询即可。先开始线段树数组开小了，$RE$了一次。1#include<cassert>2#inclu... 查看详情

bzoj3307:雨天的尾巴(代码片段)

传送门树上差分+线段树合并+离散化对于修改的路径，树上差分就好了代码：#include<cstdio>#include<iostream>#include<cstring>#include<tr1/unordered_map>#include<algorithm>usingnamespacestd;voidread(int&x) 查看详情

bzoj3307:雨天的尾巴

3307:雨天的尾巴TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 479  Solved: 214[Submit][Status][Discuss]DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的 查看详情

[bzoj3307]雨天的尾巴

3307:雨天的尾巴TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 709  Solved: 296[Submit][Status][Discuss]DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的 查看详情

bzoj3307雨天的尾巴

3307:雨天的尾巴TimeLimit: 10Sec  MemoryLimit: 128MBDescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。... 查看详情

[bzoj3307]雨天的尾巴(代码片段)

DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，M接下来N-1行，每行两个数字a,b,表示a与b... 查看详情

p4556[vani有约会]雨天的尾巴（线段树合并）(代码片段)

传送门一道线段树合并首先不难看出树上差分我们把每一次修改拆成四个，在(u,v)分别放上一个，在(lca)和(fa[lca])各减去一个，那么只要统计一下子树里的总数即可然而问题就在于怎么统计。直接暴力肯定是要咕咕的，那么线段... 查看详情

luogu4556雨天的尾巴树上差分线段树合并(代码片段)

传送门 一个套路题……树上差分+线段树合并即可注意一个细节：$pushup$的时候如果最大值为$0$一定要把最大值对应的答案也设为$0$，否则会$WA$第二个点另外如果这道题空限变小了请不要交这份代码，因为这份代码没有卡空... 查看详情

luogu4556雨天的尾巴(线段树合并+差分)(代码片段)

题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮... 查看详情

[vani有约会]雨天的尾巴(代码片段)

我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。结果原题范围k<=100000……果断线段树合并。普及线段树合并：比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右... 查看详情

线段树合并(代码片段)

3307:雨天的尾巴模板题。简单题调不过最好的方法是重构代码或者放一天然后重构代码。1//Achen2#include<algorithm>3#include<iostream>4#include<cstring>5#include<cstdlib>6#include<vector>7#include<cstdio>8#inc 查看详情

权值线段树-动态开点-合并（p4556[vani有约会]雨天的尾巴(代码片段)

题意：https://www.luogu.com.cn/problem/P4556树链加数，问你每个节点最多的是哪个数。思路：树链加数很容易想到差分。从下往上用权值线段树合并即可，直接用pushup把答案存在树根即可，不用每次查询最多的数1structEDGE23intto,next;4edge[N... 查看详情

p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)

传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情

p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)

传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情

[bzoj3551]peaks半可持久化并查集可持久化线段树合并

实现1#include<cstdio>2#include<cstring>3#include<cstdlib>4#include<cctype>5#include<algorithm>6#include<map>7usingnamespacestd;8#defineF(i,a,b)for(registerinti=(a);i& 查看详情

p4556[vani有约会]雨天的尾巴(线段树合并+树上差分)(代码片段)

传送门题意：给一颗树，n个节点，m次操作。每次操作使u到v的路径上每个节点中颜色z的数量加1，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情