AT_abc484_d.Move One Card Left
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a sequence A=(A1,A2,…,AN) of length N consisting of positive integers.
The following operation is performed on the sequence A exactly once.
- Choose one element of A, take it out, and insert it into the remaining sequence at its original position or earlier. More formally, perform the following two steps in order.
- Choose an integer i satisfying 1≤i≤N, let the sequence X=(X1,X2,…,XN−1) of length N−1 be (A1,A2,…,Ai−1,Ai+1,Ai+2,…,AN), and let the integer Y be Ai.
- Choose an integer j satisfying 1≤j≤i, and let the sequence (X1,X2,…,Xj−1,Y,Xj,Xj+1,…,XN−1) of length N be the new A.
Note that in some cases the element can be inserted at the left end or the right end of the sequence.
Find the number of distinct sequences that can be obtained as a result of the operation.
Even if the pairs (i,j) chosen in the operation are different, the results are counted as the same if they are equal as sequences.
给你一个长度为 N 的正整数序列 A=(A1,A2,…,AN)。
对序列 A 恰好执行一次如下操作:
- 选择 A 中的一个元素,将其移出,并插入到剩余序列的原位置或更靠前的位置。更准确地说,按顺序执行以下两步:
- 选择满足 1≤i≤N 的整数 i,令长度为 N−1 的序列 X=(X1,X2,…,XN−1) 为 (A1,A2,…,Ai−1,Ai+1,Ai+2,…,AN),并令整数 Y 为 Ai。
- 选择满足 1≤j≤i 的整数 j,并将长度为 N 的序列 (X1,X2,…,Xj−1,Y,Xj,Xj+1,…,XN−1) 作为新的 A。
注意:在某些情况下,该元素可被插入到序列最左端或最右端。
求通过该操作所能得到的不同序列的个数。
即使操作中所选的 (i,j) 对不同,只要所得序列相同,就视为同一种结果(即仅按序列本身是否相等来计数)。
输入格式
The input is given from Standard Input in the following format:
N
A1 A2 … AN
输入从标准输入中按以下格式给出:
N
A1 A2 … AN
输出格式
Print the answer.
输出答案。
输入输出样例
输入#1
6 1 4 1 4 2 1
输出#1
12
输入#2
5 1 1 1 1 1
输出#2
1
输入#3
30 24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20
输出#3
303
说明/提示
Sample 1 Explanation:
For example, performing the operation with i=6,j=4 yields (1,4,1,1,4,2).
Besides this, the following 11 sequences can be obtained.
- (1,1,4,1,4,2)
- (1,1,4,4,2,1)
- (1,2,4,1,4,1)
- (1,4,1,2,4,1)
- (1,4,1,4,1,2)
- (1,4,1,4,2,1)
- (1,4,2,1,4,1)
- (1,4,4,1,2,1)
- (2,1,4,1,4,1)
- (4,1,1,4,2,1)
- (4,1,4,1,2,1)
Thus, print 12.
Sample 2 Explanation:
Note that sequences obtained by different pairs (i,j) are counted as one if they are equal as sequences.
Constraints
- 1≤N≤2×105
- 1≤Ai≤N (1≤i≤N)
- All input values are integers.
样例 1 解释:
例如,对 i=6,j=4 执行该操作可得到序列 (1,4,1,1,4,2)。
除此之外,还可得到以下 11 个序列:
- (1,1,4,1,4,2)
- (1,1,4,4,2,1)
- (1,2,4,1,4,1)
- (1,4,1,2,4,1)
- (1,4,1,4,1,2)
- (1,4,1,4,2,1)
- (1,4,2,1,4,1)
- (1,4,4,1,2,1)
- (2,1,4,1,4,1)
- (4,1,1,4,2,1)
- (4,1,4,1,2,1)
因此,输出 12。
样例 2 解释:
注意:若由不同数对 (i,j) 得到的序列作为序列完全相同,则仅计为一种。
约束条件
- 1≤N≤2×105
- 1≤Ai≤N (1≤i≤N)
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?