主题

主题

 
   

4553: [Tjoi2016&Heoi2016]序列

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4553/http://cogs.pro/cogs/problem/problem.php?pid=2275

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。所有数均为正整数,且小于等于100,000

Output

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

Sample Input

3 4

1 2 3

1 2

2 3

2 1

3 4

Sample Output

3


个人解法:

smg题面标点换行乱打,看了半天题目才看懂。

一个很棒棒的性质就是一个时刻只会有一个位置的数字变化。那么我们不难参考普通的最长不降子序列,写出一个方程:

F[i]=max{F[j]}+1,其中A[j]<=min[i]且max[j]<=A[i](minn与maxn为这个位置变化的最小值与最大值)

我们发现这是二维的限制,不能单纯用一个BIT,所以我们可以使用树套树或者CDQ+BIT这样的方法来处理。

写了一个代码(相对而言)短的CDQ+BIT。


代码如下:

https://code.csdn.net/snippets/2291143

 
 
评论
 
 
热度(1)