021017模拟 string 无旋Treap+并查集 数据结构

021017模拟 string 无旋Treap+并查集

区间翻转非常水,搞个无旋treap就好了,但是垃圾出题人居然卡常,没办法只能强开O3+节点内存池了。可以看出,在操作过后,问号之间形成了若干联通块,同一联通块内部所填字符必须相同,所以如果一个节点已经确定,那么整个联通块也就确定了,否则整个联通块随便填26个字母。 如果要求字典序第k小,就给并查集加···
BZOJ1500 [NOI2005]维修数列 无旋Treap 数据结构

BZOJ1500 [NOI2005]维修数列 无旋Treap

裸题,但是非常鬼畜,和线段树的“CPU监控”是同一程度的,都是要维护很多标记。 首先,先考虑要维护的标记: ml:最大左缀和,mr:最大右缀和,ms:最大中缀和; ※本题要求最大连续和不能为空。 sum:区间和; setv:区间修改标记; rev:区间翻转标记。 接着,考虑标记的作用范围。如果只考虑···
BZOJ4553 [Tjoi2016&Heoi2016]序列 树套树+三维偏序 数据结构

BZOJ4553 [Tjoi2016&Heoi2016]序列 树套树+三维偏序

刚开始做的时候没好好地当作三维偏序来做,只是乱搞,后来膜了CDQ的思路,大概有了点套路,于是决定用树状数组套无旋treap来搞这道题(其实是因为还没打过CDQ呵呵)。 按照最长不降子序列的DP做法,DP方程显然为F[i]=max{f[j]}+1。问题转为了如何寻找最优的转移点j。 首先,按照套路,先···
BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash 字符串 数据结构

BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash

题意就是给出字符串,动态插入、修改字符。我们需要数据结构,动态维护序列的哈希值。 $$H(l,r)=\sum _{i=l} ^{r} S[i]*base^{i-l}$$ 考虑这个计算一段字符串hash值的公式,可以通过维护子树hash值,再利用Treap的分裂合并操作动态维护,最后二分答案就好啦。 ···