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

发布于 2017-09-30  4.29k 次阅读


[toggle hide="yes" title="题目" color=""]

Description
佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。注意:每种变化最多只有一个值发生变化。在样例输入1中,所有的变化是:
1 2 3
2 2 3
1 3 3
1 1 3
1 2 4
选择子序列为原序列,即在任意一种变化中均为不降子序列在样例输入2中,所有的变化是:
3 3 3
3 2 3
选择子序列为第一个元素和第三个元素,或者第二个元素和第三个元素,均可满足要求

Input
输入的第一行有两个正整数n,m,分别表示序列的长度和变化的个数。接下来一行有n个数,表示这个数列原始的状态。接下来m行,每行有2个数x, y,表示数列的第x项可以变化成y这个值。1<=x<=n。所有数字均为正整数
,且小于等于100000

Output
输出一个整数,表示对应的答案

Sample Input
3 4
1 2 3
1 2
2 3
2 1
3 4

Sample Output
3

[/toggle]

刚开始做的时候没好好地当作三维偏序来做,只是乱搞,后来膜了CDQ的思路,大概有了点套路,于是决定用树状数组套无旋treap来搞这道题(其实是因为还没打过CDQ呵呵)。

按照最长不降子序列的DP做法,DP方程显然为F[i]=max{f[j]}+1。问题转为了如何寻找最优的转移点j。

首先,按照套路,先列要搞的式子:设s[i]:i在原序列的值,mx[i]:i能达到的最大值,mn[i]:i能达到的最小值。

考虑到每次只能修改一次,满足如下三个式子即为合法的转移位置。

1.j<i

2.mx[j]<=s[i]

3.s[j]<=mn[i]

这样问题就转为了三维偏序,可以搞了。

第一维即为在序列中的下标,直接扫一遍即可。

第二维的限制需满足第二个式子,建立树状数组,在树状数组对应的treap里查找满足条件2、3的对应的最大f值。

第三位的限制需满足第三个式子,给树状数组每个节点对应一棵无旋treap,按照要搞的权值建树,同时保存当前点的f值以及子树最大值,这样,在一棵treap里只需提取满足条件3的一段前缀最大f值即可。

 

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974