ComplexPug

未归档

做题记录(1)

/ 注册

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

可持久化fhq-treap学习笔记

目录可持久化fhq-treap----- 支持查询历史版本的非旋treap 先看看为啥他可以可持久化过程别的注意&&出错&&吐槽模板->luoguP3835代码可持久化...

学习笔记可持久化 fhqtreap

2018-12-01

0 647

fhq treap抄袭笔记

目录碎碎念点一下注意！！！模板 fhq treap 碎碎念我咋感觉合并这么像左偏树呢 ps：难道你们的treap都是小头堆的吗 fhq真的是神人现在看以前学的splay是有点恶心，尤其是压行压不过fhqtreap 点...

fhqtreap 学习笔记

2018-11-29

0 499

P3466 [POI2008]KLO-Building blocks

目录题目思路错误代码题目 luogu csdn好像限制了展开博客次数，真的好xx 思路显然一段区间内的值一定是他的中位数少一点比多一点好然后就可以枚举区间了区间答案为 val[mid]-小于val[mid]的+...

fhqtreap

2018-12-01

0 489

文艺平衡树

思路 splay确实有点绕还是fhq-treap牛逼啊，构造完美二叉树(他们说笛卡尔树)，就不用rand的，直接计算就好时间也不慢代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) u...

fhqtreap

2018-12-01

0 487

luogu P4396 [AHOI2013]作业

目录题目思路错误&&傻叉代码题目 luogu 思路每次都是插入比之前所有数字大的数，所以之前的答案就不会改变用fhq-treap求出原序列，然后用树状数组依次算出每个值得lis(显然g[i]=g[i...

fhqtreap lis

2018-12-04

0 470

P1533 可怜的狗狗

思路终于做了一个简单题，233 先对区间拍个序因为他说所有区间互不包含所以排序之后可以双指针l,r指呀指容易得到这样每个值最多插入删除一边一次操作logn 总复杂度nlogn 代码 #include <bits/stdc++.h> #define FOR(i,a,b) ...

fhqtreap

2018-12-09

0 535

P3224 [HNOI2012]永无乡

思路并查集+fhqtreap 合并的时候由于是大小不一，所以不能直接合并所以我们就暴力合并喽对，就是那种很暴力的把小的往大的身上靠他们说是启发式合并抄一波博客启发式合并启发式合并核心思想就一句话：把小集合的合并到大的里。启发式合并思想可以放到很多数据结构里，链表、线段树、甚至平衡...

fhqtreap 启发式合并

2018-12-09

0 449

P3380 【模板】二逼平衡树（树套树）

思路若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4，之后有三个数l...

线段树 fhqtreap 树套树

2018-12-11

0 579

3545: [ONTAK2010]Peaks 平衡树，最小生成树

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3545 离线询问，按照权值排个序就是在克鲁斯卡尔时候维护个treap，到时候挨个查询一下就好了 nb的gzy说要要在线才是呢，nb 代码 /********************...

最小生成树 fhqtreap

2019-02-12

0 493

bzoj 1251: 序列终结者平衡树，fhqtreap

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1251 思路好简单的模板题不过还是wrong了好几发叶子节点要注意下,不能使用遇到就不管写的fhq-treap，OI中常数最大的平衡树，中间还T了一发代码 #include...

fhqtreap

2019-02-10

0 480