F - Variety Split Hard Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550550

問題文

この問題は C 問題の強化版です。分割する個数が 33 個になります。

長さ NN の整数列 A=(A1,A2,,AN)A=(A_1,A_2,\ldots,A_N) が与えられます。

AA22 か所で区切って 33 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めてください。

より厳密には、1i<jN11 \leq i < j \leq N-1 を満たす整数の組 (i,j)(i,j) について (A1,A2,,Ai),(Ai+1,Ai+2,,Aj),(Aj+1,Aj+2,,AN)(A_1,A_2,\ldots,A_i) , (A_{i+1},A_{i+2},\ldots,A_j) , (A_{j+1},A_{j+2},\ldots,A_{N}) のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。

制約

  • 3N3×1053 \leq N \leq 3 \times 10^5
  • 1AiN1 \leq A_i \leq N (1iN1 \leq i \leq N)
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

NN
A1A_1 A2A_2 \ldots ANA_N

出力

答えを出力せよ。


入力例 1Copy

Copy
5
3 1 4 1 5

出力例 1Copy

Copy
5

(i,j)=(2,4)(i,j)=(2,4) とし、(3,1)(3,1)(4,1)(4,1)(5)(5)33 つの連続する部分列に分割すると、それぞれに含まれる整数の種類数は 2,2,12,2,1 でこれらの和は 55 です。また、55 より大きい値は取り得ないので、答えは 55 です。他にも、(i,j)=(1,3),(2,3),(3,4)(i,j)=(1,3),(2,3),(3,4) などでも種類数の和は 55 になります。


入力例 2Copy

Copy
10
2 5 6 4 4 1 1 3 1 4

出力例 2Copy

Copy
9

Score : 550550 points

Problem Statement

This problem is a harder version of Problem C. Here, the sequence is split into three subarrays.

You are given an integer sequence of length NN: A=(A1,A2,,AN)A = (A_1, A_2, \ldots, A_N).

When splitting AA at two positions into three non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following three values for a pair of integers (i,j)(i,j) such that 1i<jN11 \leq i < j \leq N-1: the count of distinct integers in (A1,A2,,Ai)(A_1, A_2, \ldots, A_i), the count of distinct integers in (Ai+1,Ai+2,,Aj)(A_{i+1},A_{i+2},\ldots,A_j), and the count of distinct integers in (Aj+1,Aj+2,,AN)(A_{j+1},A_{j+2},\ldots,A_{N}).

Constraints

  • 3N3×1053 \leq N \leq 3 \times 10^5
  • 1AiN1 \leq A_i \leq N (1iN1 \leq i \leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

NN
A1A_1 A2A_2 \ldots ANA_N

Output

Print the answer.


Sample Input 1Copy

Copy
5
3 1 4 1 5

Sample Output 1Copy

Copy
5

If we let (i,j)=(2,4)(i,j) = (2,4) to split the sequence into three subarrays (3,1)(3,1), (4,1)(4,1), (5)(5), the counts of distinct integers in those subarrays are 22, 22, 11, respectively, for a total of 55. This sum cannot be greater than 55, so the answer is 55. Other partitions, such as (i,j)=(1,3),(2,3),(3,4)(i,j) = (1,3), (2,3), (3,4), also achieve this sum.


Sample Input 2Copy

Copy
10
2 5 6 4 4 1 1 3 1 4

Sample Output 2Copy

Copy
9


2025-03-17 (Mon)
21:36:11 +00:00