ComplexPug

未归档

做题记录(1)

/ 注册

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

线段树合并学习笔记

顾名思义就是两颗线段树合成一个线段树那合成的线段树是适合所有线段树吗当然不是，是动态开点线段树建树这里建n个节点的时候，每个节点建一棵树而且要按照一定的形态建立一条链就是说如果最终形态是有n个数字的树，那你初始化的那一条链子一定是这颗树上扣下来的这样才方便合并 merge操...

线段树合并学习笔记

2018-12-10

0 400

luogu1110[ZJOI2007]报表统计

思路这里的初始化就不讲了,看完操作讲解就应该明白了，再不行就去看代码对于操作1 由于操作2的需要，vector[n]存下数对于操作2的维护查询相邻两个元素的之间差值（绝对值）的最小值先把所有答案存入一个小头堆里比如 a,c之间你要插入b 那么，你就要删除|c-a|,然后加入|a...

伸展树splay STL

2018-12-10

0 442

P3224 [HNOI2012]永无乡

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

fhqtreap 启发式合并

2018-12-09

0 449

P1533 可怜的狗狗

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

fhqtreap

2018-12-09

0 535

P2596 [ZJOI2006]书架

思路一开始写fhq-treap 感觉越写越感觉splay好些，就去splay 然后维护序列注意前驱后继的不存在的情况但不用插入虚拟节点(那插入岂不太麻烦) 跑的真慢的一批，splay太多了错误好多错误只好对拍代码 //这个题用treap似乎小题大做了,所以我用splay #...

伸展树splay

2018-12-09

0 461

P2042 [NOI2005]维护数列

思路超级恶心的pushdown 昏天黑地的调让我想起了我那前几个月的线段树2 错误这恶心的一道题终于过了太多错误，简直说不过来 pushup pushdown 主要就是这俩不太清晰，乱pushdown 其他的写的还没啥毛病(能看出来) 代码 #include <iostrea...

treap

2018-12-08

0 427

替罪羊树深坑学习笔记

目录前言要点||摘录模板前言其实我感觉俩就够了，lmc还得让学替罪羊旋转维持分裂维护拍扁维护齐全了请点击ikka大爷的讲解我不会指针，所以数组模拟、、回收可真麻烦，看来以后还得学指针那感觉写完就会弃掉 up...

替罪羊树学习笔记

2018-12-06

0 425

luogu P4396 [AHOI2013]作业

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

fhqtreap lis

2018-12-04

0 470

文艺平衡树

思路 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

可持久化fhq-treap学习笔记

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

学习笔记可持久化 fhqtreap

2018-12-01

0 647