BZOJ4553 [Tjoi2016&Heoi2016]序列 树套树+三维偏序 数据结构

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

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

BZOJ3339&3585 mex 莫队+树状数组

一开始想用动态开点线段树来维护最小未出现自然数,然而瞄了一眼题解告诉我会T掉,因为莫队算法(基本上)只适用于转移的复杂度为O(1)的操作,也就是说强行加个log2n比较难卡过去,所以考虑换用更高效的转移。 首先,即使是在极限情况下,我们最多只需要记录O(n)的出现信息,而不用考虑更大的数,因为最小未···