You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

6个子任务 problem.pdf

sample.rar

摘抄文档

题目描述

Snakes 阅读完文章后，决定摘抄其中的优美文章。

文章用长度为 $n$ 的数列表示。

优美文章用数列 $B$ 表示（B for Beautiful）。

现在 Snakes 已经“写”好了一篇文章 $C$（C for Copy），Snakes 决定在此基础上修改文章 $C$。

修改方法如下：每次选择一个长度为 $2$ 的区间，将其中所有的数字变成区间最大值。

Snakes 可以修改文章 $C$ 任意多次，他想知道，文章 $C$ 经过修改后，最多有多少个对应位置上的数字和 优美文章 $B$ 相同(满足$B_i=C_i$的下标$i$的个数)。

输入格式

第一行，一个正整数 $n$，表示文章长度。

第二行，$n$ 个整数 $C_1,\dots,C_n$。

第三行，$n$ 个整数 $B_1,\dots,B_n$。

输出格式

一个整数表示答案。

3
1 2 3
2 2 2

2

对区间[1,2]进行操作，变成 2 2 3，2个数和优美文章一样。

4
10 1 9 1
10 9 10 9

3

对区间[2,3]进行操作，再对[3,4]进行操作，文章变成10 9 9 9，3个数和优美文章一样。

数据范围与评分

子任务1(14分)： $n \leq 10$

子任务2(12分)： $n \leq 10^5$，所有 $B_i$ 相等。

子任务3(13分)： $n \leq 5000$， $C_i$ 严格单调递增。

子任务4(23分)： $n \leq 10^5$， $C_i$ 互异。

子任务5(16分)： $n \leq 200$

子任务6(22分)： $n \leq 5000$