正文 

当前位置： 首页 > 知识 > java教程

bzoj3307雨天的尾巴线段树合并

wx62f0894128448 wx62f0894128448     2022-11-30     774

关键词：


​​http://www.elijahqi.win/archives/3463​​​
Description
N个点，形成一个树状结构。有M次发放，每次选择两个点x,y
对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成
所有发放后，每个点存放最多的是哪种物品。

Input
第一行数字N，M
接下来N-1行，每行两个数字a,b,表示a与b间有一条边
再接下来M行，每行三个数字x,y,z.如题

Output
输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种，如果有
多种物品的数量一样，输出编号最小的。如果某个点没有物品
则输出0

Sample Input
20 50
8 6
10 6
18 6
20 10
7 20
2 18
19 8
1 6
14 20
16 10
13 19
3 14
17 18
11 19
4 11
15 14
5 18
9 10
12 15
11 14 87
12 1 87
14 3 84
17 2 36
6 5 93
17 6 87
10 14 93
5 16 78
6 15 93
15 5 16
11 8 50
17 19 50
5 4 87
15 20 78
1 17 50
20 13 87
7 15 22
16 11 94
19 8 87
18 3 93
13 13 87
2 1 87
2 6 22
5 20 84
10 12 93
18 12 87
16 10 93
8 17 93
14 7 36
7 4 22
5 9 87
13 10 16
20 11 50
9 16 84
10 17 16
19 6 87
12 2 36
20 9 94
9 2 84
14 1 94
5 5 94
8 17 16
12 8 36
20 17 78
12 18 50
16 8 94
2 19 36
10 18 36
14 19 50
4 12 50
Sample Output
87
36
84
22
87
87
22
50
84
87
50
36
87
93
36
94
16
87
50
50
1<=N,M<=100000
1<=a,b,x,y<=N
1<=z<=10^9

HINT

Source
直接考虑差分一下即可 即每个点储存1到这个点的所有信息 如x,y需要改那么则在x上+1 y上+1

lca-1 fa[lca]-1即可 然后最后合并的时候从底向上合并即可 这个差分可以看做 这个点到跟的路径分别被差分了一下

线段树合并一个log竟然如此慢

另外内存不太会算qwq总觉得应该是120*N

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline char gc()
    static char now[1<<16],*S,*T;
    if (T==S)T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;
    return *S++;

inline int read()
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) if (ch==-) f=-1;ch=gc();
    while(isdigit(ch)) x=x*10+ch-0,ch=gc();
    return x*f;

const int N=1e5+10;
struct node
    int y,next;
data[N<<1];
int n,h[N],dep[N],Log[N],fa[N][20],rt[N],ans[N],num,m;
inline void dfs(int x)
    for (int i=h[x];i;i=data[i].next)
        int y=data[i].y;if (y==fa[x][0]) continue;dep[y]=dep[x]+1;fa[y][0]=x;
        for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1];
        dfs(y);
    

inline int lca(int x,int y)
    if (dep[x]<dep[y]) swap(x,y);int dis=dep[x]-dep[y];
    for (int i=0;i<=Log[dis];++i) if((1<<i)&dis) x=fa[x][i];
    if (x==y) return x;
    for (int i=Log[dep[y]];~i;--i) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];

struct node1
    int left,right,id,mx;
tree[N*60];
inline void update(int x)
    int l=tree[x].left,r=tree[x].right;
    tree[x].mx=max(tree[l].mx,tree[r].mx);
    tree[x].id=tree[l].mx>=tree[r].mx?tree[l].id:tree[r].id;

inline void insert1(int &x,int l,int r,int p,int v)
    if (!x) x=++num;int mid=l+r>>1;
    if (l==r) tree[x].mx+=v;tree[x].id=l;return;
    if(p<=mid) insert1(tree[x].left,l,mid,p,v);
    else insert1(tree[x].right,mid+1,r,p,v);update(x);

inline int merge(int rt1,int rt2,int l,int r)
    if (!rt1||!rt2) return rt1+rt2;
    if(l==r) tree[rt1].mx+=tree[rt2].mx;return rt1;int mid=l+r>>1;
    tree[rt1].left=merge(tree[rt1].left,tree[rt2].left,l,mid);
    tree[rt1].right=merge(tree[rt1].right,tree[rt2].right,mid+1,r);update(rt1);return rt1;

const int nn=1e9;
inline void print(int x,int l,int r)
    int mid=l+r>>1;

    if (tree[x].left) print(tree[x].left,l,mid);
    printf("%d %d %d %d\\n",l,r,tree[x].mx,tree[x].id);
    if (tree[x].right) print(tree[x].right,mid+1,r);

inline void dfs1(int x)
    for (int i=h[x];i;i=data[i].next)
        int y=data[i].y;if (y==fa[x][0]) continue;
        dfs1(y);
        rt[x]=merge(rt[x],rt[y],1,nn);
        //printf("%d\\n",x);puts("-----");print(rt[x],1,nn);
    ans[x]=tree[rt[x]].id;

int main()
    freopen("bzoj3307.in","r",stdin);
    n=read();for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1;m=read();
    for (int i=1;i<n;++i)
        int x=read(),y=read();
        data[++num].y=y;data[num].next=h[x];h[x]=num;
        data[++num].y=x;data[num].next=h[y];h[y]=num;   
    dfs(1);num=0;
    for (int i=1;i<=m;++i)
        int x=read(),y=read(),z=read(),t=lca(x,y);
        insert1(rt[x],1,nn,z,1);insert1(rt[y],1,nn,z,1);
        insert1(rt[t],1,nn,z,-1);if (fa[t][0]) insert1(rt[fa[t][0]],1,nn,z,-1);
    dfs1(1);
    for (int i=1;i<=n;++i) printf("%d\\n",ans[i]);
    return 0;


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

题目大意：一颗树，想要在树链上添加同一物品，问最后每个点上哪个物品最多。解题思路：假如说物品数量少到可以暴力添加，且树点极少，我们怎么做。首先在一个树节点上标记出哪些物品有多少，寻找道路上的节点暴力添... 查看详情

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，最后询问每个节点中数量最多的颜色。思路：显然，我们得维护每个节点中颜色的最大值。那么我们给每个... 查看详情

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

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

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

[luogu4556]雨天的尾巴luogu发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并但是...如果你只有35分...https://www.luogu.org/discuss/show/88259#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=get 查看详情