rprp

数据结构

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 未归档(2) 贪心(5) 配置(2)

/ 注册

全部文章 / 数据结构（共18篇）

李超线段树复习笔记

复习笔记就离谱好吧用途大概是给你一个序列，然后插入一条线段，然后查询某一个位置上与所有线段交点的纵坐标的的最大值或者最小值。然后就没了。实现定义一个区间的"优势线段"为在这个区间里面有超过一半的点在这个线段上取到最值。考虑维护一个线...

李超线段树

2020-11-20

0 538

LCT板子

#define ls(x) ch[x][0] #define rs(x) ch[x][1] int fa[N], ch[N][2], sum[N], val[N], rev[N]; inline void update(int x) { sum[x] = sum[ls(x)] ^ sum[rs(x)...

Link-Cut-Tree

2020-06-16

0 359

高精度板子

//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstring> #include<stack> #include<string> ...

高精度

2020-06-09

0 367

「JOISC 2016 Day 3」回转寿司

「JOISC 2016 Day 3」回转寿司这题我无力吐槽了... 强烈谴责出题人用脚造数据解法其实这题主要还是部分分启发正解吧。看到有个\(s_i = 1, t_i= n\)的做法就是维护一个堆就可以了，所以扩展下就是分块，然后每个块维护一个堆。散块暴力，大块直接查。但是有个很坑爹的问题...

堆

2020-05-18

0 723

CF1093G Multidimensional Queries

这题妙啊。学会了一个新\(trick\)。题解 \[|x_1 - x_2|+|y_1 - y_2| = \\ max (x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y2,-x_1+x_2-y_1+y_2) = \\max((x_1+y_1)...

线段树位运算妙啊

2020-05-16

0 431

CF1045G AI robots

\(CDQ\)分治的妙题。考虑按视野从大到小排序，那右边的可以看见左边的话左边一定看得见右边的，直接\(CDQ\)就行了。对于这种\([x-K,x+K]\)的区间维护可以在统计的时候差分也可以直接在更新的时候差分。本代码使用后者。 #include <cstdio> #include...

cdq分治

2020-05-15

0 383

CF1175E Minimal Segment Cover

一个很妙的操作，求出每个点通过一条边可以向右边覆盖的最远距离，然后倍增。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define R reg...

妙啊倍增

2020-05-15

0 418

Luogu P3703 [SDOI2017]树点涂色

Luogu P3703 [SDOI2017]树点涂色用LCT中每一个Splay维护颜色相同的点集，则从一个点到根节点的轻边的条数就是这个点的到根的权值。至于路径查询的搞个差分就好，用树剖实现。至于为什么可以直接这样查，是因为LCT里面涉及子树的权值变化只有access函数。在splay中的子树的...

树链剖分 Link-Cut-Tree

2020-05-13

0 393

BZOJ2568 比特集合

题目链接 BZOJ2568 比特集合思路首先考虑不带区间加的情况，显然容易想到对每个数的每一个二进制位维护一个树状数组。设一个树状数组维护的是二进制的第\(k\)位，那就每次往里面存\(num\)的时候在这个树状数组的第\(num\ mod \ 2^k\)这个位置\(+1\)，那么我们...

树状数组位运算

2020-05-08

0 542

P6329 【模板】点分树 | 震波

前言由于这篇题解思路并没有什么区别，所以这篇题解的意义在于稍稍更细致地讲下思路和卡常方法。估计也只有我常数这么大了思路第一感由于题目要查询到一个点距离为\(k\)以内的所有点的权值和，一个显然的想法就是对每个点开一个线段树维护权值和，下标维护距离，然后暴力查询。显然这是\(MLE+T...

线段树动态点分治

2020-05-06

0 659