这将是一篇只有重点内容的学习笔记。 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...

大概是对着网上的模板敲了一遍吧。。。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939...

传送门 这道题比较有意思 考虑记录一个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...

建议先做SP1043 GSS1 - Can you answer these queries I 传送门 我们可以用FHQTreapFHQ TreapFHQTreap做这道题。 首先，FHQTreapFHQ TreapFHQTreap最重要的是Merge和Split操作，Split按照权值split 但是这道题插入删除修改时，要按照分出序列前kkk个值，是不是没法做？ 没关系，我们采用类似于...

平衡树模板题 Splay写法： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586// luogu-judger-en...