这将是一篇只有重点内容的学习笔记。 Merge 因为每个节点实际上代表了一段区间，我们以这种形式表示一个节点： 考虑Merge，我们要维护堆性质，这里认为是大根堆。 1.pri(x)>pri(y) 问题转化为Merge(rc(x),y) 这样可以递归下去 现在根节点变为x 2.pri(x)<=pri(y) 不再赘述 Split 1.k<=sz(lc) ...

传送门 洛谷上面翻译有毒，一是没有数据范围，其实n≤200000n \le 200000n≤200000，二是没有样例，这里粘贴一组SPOJ\rm SPOJSPOJ样例，和自己的对拍数据。 SPOJ\rm SPOJSPOJ样例 12345678910111213141516input:41 2 3 57Q 0 2 0I 3 4Q 2 4 1D 0Q 0 3 1R 1 2Q 0 1 0outp...

传送门 这道题比较有意思 考虑记录一个tagtagtag表示员工工资应该加上多少。 加工资的操作不会导致员工离开 但是扣工资的操作会导致工资所有小于min−tagmin-tagmin−tag的员工离开 怎么删除所有小于min−tagmin-tagmin−tag的值呢？ yy一下，发现FHQ Treap中numnumnum左子树的值都小于num 于是每次删除所有小于min−tagmin-tag...

传送门 平衡树模板题 模拟整个过程，每次找numnumnum的前驱后继，注意特判numnumnum在集合中的情况 // luogu-judger-enable-o2 #include <bits/stdc++.h> #define MAXN 500005 #define MOD 1000000 using namespace std; inline int read() ...

传送门 平衡树模板题 也是模拟题 宠物和人会相互抵消，所以不存在一次操作后集合中既存在人也存在宠物 分情况讨论当前是人集合还是宠物集合 如果加进来的是同类，直接InsertInsertInsert 如果是不同类，查询前驱后继，按题目意思模拟即可 12345678910111213141516171819202122232425262728293031323334353637383940414...

传送门 注意：XkX_kXk​为位置，而kkk才是真正加进去的数。 加入的序列为1,2,3,......1,2,3,......1,2,3,...... 也就是说，每次加入的数都是当前最大的。 那么我们很快就可以推出dpdpdp方程： dp[i]=max(dp[i],dp[j]+1)j<idp[i]=max(dp[i],dp[j]+1) j<idp[i]=max(dp[i],dp...

传送门 树套树模板题（线段树套FHQTreap\rm FHQ TreapFHQTreap） 一开始听说FHQTreap\rm FHQ TreapFHQTreap常数大，会TLE\rm TLETLE，就没敢写，最后发现FHQTreap\rm FHQ TreapFHQTreap还是能过的。 好了步入正题： 考虑在线段树的每个节点开一棵FHQTreap\rm FHQ TreapFHQTreap，...