ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

luogu P2617 Dynamic Rankings

前置知识: 普通主席树，树状数组大概待修主席树和静态的一样只不过还要加一颗树来维护你修改的值这棵树就是是树状数组,每个节点上再维护一颗动态开点线段树 (就是所说的树套树，不过没啥可怕的，就是麻烦一丢丢) 查询的时候老样子不过要多加上树状数组中的值罢了代码还算好些，如果主席树，...

线段树离散化数据结构-主席树树套树可持久化

2018-12-11

0 508

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 581

P4556 [Vani有约会]雨天的尾巴

目录思路优化过程中的问题/疑问错误代码思路每个节点维护一课线段树(当然是动态开点) 线段树的作用是统计这个节点有多少种粮食型号，以及最多的粮食型号然后树上差分，u和v点 +1，lca(u,v)和f[lca(u...

线段树线段树合并数据结构 ST表 lca 差分

2018-12-10

0 477

luogu P3605 [USACO17JAN]Promotion Counting晋升者计数

题目链接 luogu 思路可以说是线段树合并的练手题目吧也没啥说的，就是dfs，然后合并、、、看代码吧错误和写主席树错的差不多都是变量写错、、、、代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=...

线段树线段树合并

2018-12-10

0 394

线段树合并学习笔记

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

线段树合并学习笔记

2018-12-10

0 408

luogu1110[ZJOI2007]报表统计

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

伸展树splay STL

2018-12-10

0 445

P3224 [HNOI2012]永无乡

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

fhqtreap 启发式合并

2018-12-09

0 452

P1533 可怜的狗狗

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

fhqtreap

2018-12-09

0 542

P2596 [ZJOI2006]书架

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

伸展树splay

2018-12-09

0 467

P2042 [NOI2005]维护数列

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

treap

2018-12-08

0 431