#P12262. 『STA - R9』交错
『STA - R9』交错
题目描述
称一个长度为 的序列 为交错序列,当且仅当其具有 的形式,且 。
给定一个长度为 的序列 和 次修改,每次修改会给定两个正整数 和 ,并令 。你需要在初始时(即第一次修改前)以及每次修改之后求出 的最长的交错子序列的长度。
输入格式
第一行一个正整数 。
第二行 个正整数,表示 。
第三行一个非负整数 。
接下来 行,每行两个正整数 ,表示一次修改。
输出格式
输出 行。
第一行表示初始时 的最长的交错子序列的长度。
接下来 行,第 行表示第 次修改后 的最长的交错子序列的长度。
5
2 3 1 3 3
1
2 3
3
3
提示
本题使用捆绑测试,子任务信息如下:
子任务编号 | 特殊性质 | 分值 | ||
---|---|---|---|---|
0 | 无 | |||
1 | ||||
2 | ||||
3 | 无 | |||
4 | ||||
5 | ||||
6 | ||||
7 |
对于 的数据,保证 ,,。