xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

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

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

树链剖分动态开点线段树

2019-05-23

0 527

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

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

树链剖分动态开点线段树

2019-05-23

0 327

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

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

树链剖分线段树

2019-05-23

0 427

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

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

树链剖分线段树

2019-05-23

0 389

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 2243 [SDOI2011]染色树链剖分+线段树

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

线段树树链剖分

2019-05-23

0 384

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 386

2019南昌网络赛 J Distance on the tree 主席树+lca

题意给一颗树，每条边有边权，每次询问\(u\)到\(v\)的路径中有多少边的边权小于等于\(k\) 分析在树的每个点上建\(1\)到\(i\)的权值线段树，查询的时候同时跑\(u,v,lca(u,v)\)三个版本的线段树，查询\(1\)到\(k\)的树上差分和\(val[u]+...

主席树 LCA

2019-05-23

0 412

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

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

BZOJ 线段树树链剖分

2019-05-23

0 426

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

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

BZOJ 线段树树链剖分

2019-05-23

0 410