xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共11篇）

BZOJ 4034 [HAOI2015]树上操作线段树+树剖或dfs

题意直接照搬原题面有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。 ...

BZOJ 线段树树链剖分

2019-05-23

0 410

BZOJ 2243 [SDOI2011]染色树链剖分+线段树

题意给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。请你写一个程序依次完成这m个操作。分析用...

线段树树链剖分

2019-05-23

0 385

BZOJ 1984 月下“毛景树” 树链剖分+线段树

题意 bzoj好像把这题删了，在洛谷里找的毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，...

树链剖分线段树

2019-05-23

0 389

BZOJ 3531 [Sdoi2014]旅行树链剖分+动态开点线段树

题意 S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信...

树链剖分动态开点线段树

2019-05-23

0 327

2019 ACM-ICPC 西安全国邀请赛 E-Tree 树链剖分+线段树

题意给一颗带点权的树，三种操作 \(1~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]|t\) \(2~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]\&t\) \(3~s~t\) 询问将1到s的路径上的所有点作为石头堆，再加上一个个数...

线段树树链剖分

2019-05-29

0 410

gym-102082，2018-2019, ICPC, Asia Yokohama Regional Contest 2018 J Colorful Tree

题意给定一个\(n\)个点的树，每个点有个初始颜色\(c_i\)，有\(m\)次询问，询问有两种： \(U~x_k~y_k\)，将第\(x_k\)个点的颜色改为\(y_k\)。 \(Q~y_k\)，找到一个边数最少的子图，使得这个子图包括所有颜色为\(y_k\)的点，输出这个子图的边...

树链剖分 LCA

2020-06-29

0 653

BZOJ 4034 [HAOI2015]树上操作线段树+树剖或dfs

题意直接照搬原题面有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。 ...

BZOJ 线段树树链剖分

2019-05-23

0 426

BZOJ 2243 [SDOI2011]染色树链剖分+线段树

题意给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。请你写一个程序依次完成这m个操作。分析用...

线段树树链剖分

2019-05-23

0 498

BZOJ 1984 月下“毛景树” 树链剖分+线段树

题意 bzoj好像把这题删了，在洛谷里找的毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，...

树链剖分线段树

2019-05-23

0 427

BZOJ 3531 [Sdoi2014]旅行树链剖分+动态开点线段树

题意 S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信...

树链剖分动态开点线段树

2019-05-23

0 527