【GDOI2014模拟】雨天的尾巴 题解+代码

2024-05-29 03:32

本文主要是介绍【GDOI2014模拟】雨天的尾巴 题解+代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

5 3
1 2
3 1
3 4
5 4
2 3 3
1 5 2
3 3 3

Sample Output

2
3
3
2
2

Data Constraint

对于20% 的数据,1<= n,m <= 100
对于50% 的数据,1 <= n,m <= 2000
对于100% 的数据,1 <= n;m <= 100000; 1 <= a, b, x, y <= n; 1 <= z <= 10^9

Solutions

一颗树,区间改变,可以考虑树链剖分。
但是,这题不用树链剖分。
对于每个节点,开一颗动态开节点的权值线段树,存的是每种救济粮的数目。
但是显然不能每次操作都把x到y之间的所有点维护一次线段树,那么可以用到一个很神奇的东西叫做:线段树合并。
如果一个点x,设它的父亲为fa[x],那么把x与fa[x]合并,就可以把x的状态加到fa[x]里面即x的每个救济粮的数目可以复制到fa[x]中,那么每次操作的时候就只用把点x和y对应位置+1,lca(x,y)和fa[lca(x,y)]对应位置-1,就行了。
那么怎么线段树合并呢?
简单来说:对于两个线段树,如果一个为空,就返回另一个,否则就两个线段树分别左儿子合并,右儿子合并就行了,在叶子节点操作。在这道题中,在叶子节点的操作就是加起来。
线段树合并代码

void merge(int v,int v1,int i,int j)
{if (i==j) {tree[v].data+=tree[v1].data;return;}int mid=(i+j)/2;if (tree[v1].l!=0) if(tree[v].l==0) tree[v].l=tree[v1].l;else merge(tree[v].l,tree[v1].l,i,mid);if (tree[v1].r!=0)if(tree[v].r==0) tree[v].r=tree[v1].r;else merge(tree[v].r,tree[v1].r,mid+1,j);tree[v].data=max(tree[tree[v].l].data,tree[tree[v].r].data);
}

code

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAX 202000
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 101000
using namespace std;
int deep[N],fa[N],last[N*10],next[N*10],to[N*10],n,hash[N*10],tot=0,a[N],ans[N],g[N],f[N][17];
bool bz[N];
struct abcde{int l,r,data;
};
abcde tree[N*100];
void putin(int x,int y)
{next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
int lsh(int x)
{int y=x%MAX;while (hash[y]!=0 && hash[y]!=x) y=(y+1)%MAX;hash[y]=x;return y;}
void dg1(int x)
{for(int i=last[x];i;i=next[i]){int k=to[i];if (deep[k]!=0) continue;fa[k]=x;deep[k]=deep[x]+1;dg1(k);}
}
void insert(int v,int i,int j,int x,int y)
{if (i==j){tree[v].data+=y;return;}int mid=(i+j)/2;if (x<=mid){if (tree[v].l==0) tree[v].l=++tot;insert(tree[v].l,i,mid,x,y);}else{if (tree[v].r==0) tree[v].r=++tot;insert(tree[v].r,mid+1,j,x,y);}tree[v].data=max(tree[tree[v].l].data,tree[tree[v].r].data);
}
void merge(int v,int v1,int i,int j)
{if (i==j) {tree[v].data+=tree[v1].data;return;}int mid=(i+j)/2;if (tree[v1].l!=0) if(tree[v].l==0) tree[v].l=tree[v1].l;else merge(tree[v].l,tree[v1].l,i,mid);if (tree[v1].r!=0)if(tree[v].r==0) tree[v].r=tree[v1].r;else merge(tree[v].r,tree[v1].r,mid+1,j);tree[v].data=max(tree[tree[v].l].data,tree[tree[v].r].data);
}
int lca(int x,int y)
{fd(i,16,0) if(deep[f[x][i]]>=deep[y]) x=f[x][i];fd(i,16,0) if(deep[f[y][i]]>=deep[x]) y=f[y][i];fd(i,16,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];if (x!=y) x=f[x][0],y=f[y][0];return x;
}
int find(int v,int i,int j)
{if (i==j) return i;int mid=(i+j)/2;if (tree[tree[v].l].data>=tree[tree[v].r].data) return find(tree[v].l,i,mid);else return find(tree[v].r,mid+1,j);
}
void dfs(int x,int fa)
{for(int i=last[x];i;i=next[i]){int k=to[i];if (k==fa) continue;dfs(k,x);merge(x,k,1,MAX);}ans[x]=find(x,1,MAX);
}
int main()
{int m;scanf("%d%d",&n,&m); fo(i,1,n-1){int x,y;scanf("%d%d",&x,&y);putin(x,y);putin(y,x);}deep[1]=1;dg1(1);tot=n;fo(i,1,n) f[i][0]=fa[i];fo(j,1,16)fo(i,1,n) f[i][j]=f[f[i][j-1]][j-1];fo(i,1,m) {int x,y,z;scanf("%d%d%d",&x,&y,&z);z=lsh(z);int lc=lca(x,y);insert(x,1,MAX,z,1);insert(y,1,MAX,z,1);insert(lc,1,MAX,z,-1);insert(fa[lc],1,MAX,z,-1);}dfs(1,0);fo(i,1,n) printf("%d\n",hash[ans[i]]);
}

这篇关于【GDOI2014模拟】雨天的尾巴 题解+代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012523

相关文章

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》:本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务,并使用ngrok暴露到公网。#sql_tools.pyfrom