正文 

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

gdoi2014模拟雨天的尾巴(代码片段)

无尽的蓝黄 无尽的蓝黄     2022-11-12     778

关键词：

题目

深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连
根拔起，以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。
首先村落里的一共有n 座房屋，并形成一个树状结构。然后救济粮分m 次发放，每次选择
两个房屋(x,y)，然后对于x 到y 的路径上（含x 和y) 每座房子里发放一袋z 类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

分析

相信大多数人都跟我一样，看到这道题，果断认为是树链剖分。
其实不然（我1.5h把熟练剖分打出来，以为能过50%。结果打错了，20%。然后。。。打暴力的人都是50%，#%……&*）。
我们注意到z<=10^9，那么的数据范围。
但是m<=100000，所以就先做个离散化。
。。。
接着用到个很神奇的东西，叫线段树合并。
对于树上的每一个节点开一棵线段树，记录该节点的每个z的数量以及某一段z的最大值。注意要动态开节点，否则会爆空间。
发现，如果要修改从x到y的路径，其实就是将x的z值加一，y的z值加一，lca(x,y)的z值减一以及fa[lca(x,y)]的z值减一（why？因为当线段树合并后从x到lca(x,y)的路径上和从y到lca(x,y)的路径上的每个节点的z值都加一，但lca(x,y)这个节点重复加了，那么就减掉。不过剩余的z值还会继续上传，所以在fa[lca(x,y)]**就把上传的z值减去）
合并操作

int mesh(int x,int y,int l,int r)

    if(l==r)
    
        tree[x].v+=tree[y].v;
        return 0;                                                    
    
    int mid=(l+r)/2;
    if(tree[y].l)
    
        if(!tree[x].l)
            tree[x].l=tree[y].l;
            else
        mesh(tree[x].l,tree[y].l,l,mid);
    
    if(tree[y].r)
    
        if(!tree[x].r)
            tree[x].r=tree[y].r;
            else
        mesh(tree[x].r,tree[y].r,mid+1,r);
    
    tree[x].v=max(tree[tree[x].l].v,tree[tree[x].r].v);

当然，当所有的修改操作做完后才线段树合并，否则会超时。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
using namespace std;
struct trees

    int l,r,v;
tree[8000000];
struct read

    int x,y,z;
re[110000];
int next[201000],last[201000],to[201000],po,tot,n,m,g[200000][20],t[200000],deep[200000],f[200000],sum,ans[2000000];
bool cmp(read x,read y)

    return x.z<y.z;

int bj(int x,int y)

    next[++tot]=last[x];
    last[x]=tot;
    to[tot]=y;

int dg(int x)

    for(int i=last[x];i;i=next[i])
    
        int j=to[i];
        if(j!=g[x][0])
        
            deep[j]=deep[x]+1;
            g[j][0]=x;
            dg(j);
        
    

int prelca()

    for(int j=1;j<=log2(n);j++)
    
        for(int i=1;i<=n;i++)
        
            g[i][j]=g[g[i][j-1]][j-1];
        
    

int lca(int x,int y)

    if(deep[x]>deep[y])
    
        x=x^y;
        y=x^y;
        x=x^y;
    
    for(int i=log2(n);i>=0;i--)
    
        if(deep[g[y][i]]>deep[x])
            y=g[y][i];
    
    if(deep[y]!=deep[x]) y=g[y][0];
    for(int i=log2(n);i>=0;i--)
    
        if(g[y][i]!=g[x][i])
        
            y=g[y][i];
            x=g[x][i];
        
    
    if(x!=y) y=g[y][0];
    return y;

int put(int v,int l,int r,int x,int y)

    if(l==r)
    
        tree[v].v+=y;
        return 0;
    
    int mid=(l+r)/2;
    if(x<=mid)
    
        if(!tree[v].l)
            tree[v].l=++sum;
        put(tree[v].l,l,mid,x,y);
    
    else
    
        if(!tree[v].r)
            tree[v].r=++sum;
        put(tree[v].r,mid+1,r,x,y); 
    
    tree[v].v=max(tree[tree[v].l].v,tree[tree[v].r].v);

int work(int x,int y,int z)

    int lc=lca(x,y);
    if(!f[x])
    
        f[x]=++sum;
    
    put(f[x],1,tot,z,1);
    if(!f[y])
    
        f[y]=++sum;
    
    put(f[y],1,tot,z,1);
    if(!f[lc])
    
        f[lc]=++sum;
    
    put(f[lc],1,tot,z,-1);
    if(g[lc][0])
    
        if(!f[g[lc][0]]) f[g[lc][0]]=++sum;
        put(f[g[lc][0]],1,tot,z,-1);
    

int mesh(int x,int y,int l,int r)

    if(l==r)
    
        tree[x].v+=tree[y].v;
        return 0;                                                    
    
    int mid=(l+r)/2;
    if(tree[y].l)
    
        if(!tree[x].l)
            tree[x].l=tree[y].l;
            else
        mesh(tree[x].l,tree[y].l,l,mid);
    
    if(tree[y].r)
    
        if(!tree[x].r)
            tree[x].r=tree[y].r;
            else
        mesh(tree[x].r,tree[y].r,mid+1,r);
    
    tree[x].v=max(tree[tree[x].l].v,tree[tree[x].r].v);

int find(int v,int l,int r)

    if(l==r)
    
        return l;
    
    if(tree[tree[v].l].v==0 && tree[tree[v].r].v==0)
        return 0;
    int mid=(l+r)/2;
    if(tree[tree[v].l].v>=tree[tree[v].r].v)
    
        return find(tree[v].l,l,mid);
    
    else
    
        return find(tree[v].r,mid+1,r); 
    

int merge(int x)

    for(int i=last[x];i;i=next[i])
    
        int j=to[i];
        if(j!=g[x][0])
        
            merge(j);
            if(!f[x])
                   
                f[x]=++sum;
               
            if(!f[j])
                   
                f[j]=++sum;
            
            mesh(f[x],f[j],1,tot);
        
    
    ans[x]=find(f[x],1,tot);

int main()

    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=1;i<=n-1;i++)
    
        int x,y;
        scanf("%d%d",&x,&y);
        bj(x,y);
        bj(y,x);
    
    deep[1]=1;
    dg(1);
    prelca();
    for(int i=1;i<=m;i++)
    
        scanf("%d%d%d",&re[i].x,&re[i].y,&re[i].z);
    
    sort(re+1,re+m+1,cmp);
    tot=0;
    sum=0;
    for(int i=1;i<=m;i++)
    
        if(re[i].z==t[tot])
        
            re[i].z=tot;
        
        else
        
            t[++tot]=re[i].z;
            re[i].z=tot;
        
    
    for(int i=1;i<=m;i++)
    
        work(re[i].x,re[i].y,re[i].z);
    
    merge(1);
    for(int i=1;i<=n;i++)
    
        if(!f[i])
               
            f[i]=++sum;
           
        printf("%d\n",t[ans[i]]);

gdoi模拟雨天的尾巴树套树

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

[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 查看详情

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

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

雨天的尾巴(代码片段)

考试的时候直接扎第一题上了这到题连暴力都没打出来T_T;心路历程：当时想到了离散化（很慌没打出来。。。），树上差分，lca倍增，当时觉滴倍增很难打，一看n<100000,于是选择用向上标记法，然而少了一行代码，，，，爆... 查看详情

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

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

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

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

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

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

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

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

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

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

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

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

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

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类型的物品。完成所有发放后，每个点存放最多的是哪种物品。... 查看详情

bzoj-3307:雨天的尾巴

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

[gdoi2014]拯救莫莉斯(代码片段)

题目描述莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x,y)表示一座城市吗，两座城市间相邻的定义为：对于城市(A... 查看详情