是晓毅

未归档

学习笔记(2) 树链剖分(1) 算法(1)

/ 注册

全部文章 / 未归档（共5篇）

POJ - 3237 题解（树链剖分）

题目传送门题意给n个点，有n-1条边连起来，每条边有自己的权值，多个操作：改变第i条边的权值；将a到b的链的边的权值取相反数；查询a到b的链上最大的权值。题解树链剖分，维护最大最小值，要取相反数的时候，最大最小值交换，再取相反数即可。 #include <algorithm...

2019-02-18

0 726

POJ 2763 题解 (树链剖分维护边权)

目录题目题意题解代码题目传送门题意给n个点，n-1条边，初始点为s，q个询问，操作0是s到u的距离，操作1是改变第i条边的权值为w。 (边权模板题) 题解将每条边的权值存到更深的点上，跑树链剖分即...

2019-02-17

0 866

HDU 3966 题解（树链剖分维护点权）

题意：给定个营地，营地i有个敌人，有条边将个营地连起来。总共有p个操作，I操作是在C1到C2的链上的每个营地都增加K个敌人；D操作是在C1到C2的链上的每个营地都减少K个敌人；Q操作是在C营地上有多少个敌人。树链剖分模板题，树链剖分后，用线段树或者树状数组维护即可。线段树写得有点丑...

2019-02-17

0 703

Binary-Index-Tree

注意!!!:这不是树状数组的详解,而是利用树状数组做区间修改的方法,当然能区间修改了也能单点修改先来个简单的树状数组啊功能: 单点更新区间查询(单点查询也就是特殊的区间查询啦) int n; int a[100005]; void add(int x...

2018-12-28

0 461

Gym-101955C题解

题目传送门C - Insertion Sort 不重复题意了，直接写解的过程，场上推不出来，赛后看题解才推出来的网上题解说存在 k ≥ ...

2018-12-28

1 683