Informatica Online Judge

  디지털 숫자 카드 #3 [2221 / 08AD]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 10


The Champion of this Problem (C++) : gs16103 - ms / 560byte
My Best Submission (C++) : N/A

[35th 황선우]
Writer ID : [gs17126]

Background

청주초등학교에 다니는 2학년 민제는 숫자를 너무 좋아한다.

어느 날 민제의 어머니는 민제가 숫자를 좋아하는 것을 눈치 채고 N장의 디지털 숫자 카드를 사주었다. 민제는 이 숫자 카드들을 자랑하기 위해 경렬이를 집에 초대했다.

민제와 경렬이는 숫자 카드로 수열을 만들거나 숫자 카드의 값을 바꾸면서 놀고 있었다.

수열을 주의깊게 살펴보던 경렬이는 ‘이 수열의 연속된 부분수열 중에서(크기가 2이상) 수열의 양끝 숫자의 값이 같고 내부 숫자들의 값은 양끝 숫자의 값보다 작은 부분수열은 모두 몇 개일까’라는 궁금증이 생겼고 민제는 이를 기존의 수열에서 수들을 하나씩 변경하였을 때에도 구해보자는 제안을 하였다.

여러분들은 아직 코딩을 잘 하지 못하는 경렬이와 민제를 도와 위 문제를 해결하는 소스코드를 작성해야 한다.

Input

첫 번째 줄에는 숫자 카드의 개수를 의미하는 자연수 N(1<=N<=300000)과 쿼리의 수 Q(0<=Q<=3000)가 주어진다.

두 번째 줄에는 초기 수열을 구성하는 N개의 숫자 카드가 주어진다. (단, 숫자 카드의 수는 int 범위를 넘어가지 않는다)

세 번째 줄부터 Q+2번째 줄에 걸쳐 Q개의 쿼리가 주어진다. 각 쿼리는 A B의 형태로 들어오는데 A는 바뀌는 숫자 카드의 위치, B는 바뀌는 숫자 카드의 값을 의미한다.

부분 문제 3
0<=Q<=3000
1<=N<=10000

Output

첫 번째 줄에는 초기 수열에서 경렬이가 구하고자 하는 부분 수열의 개수를 출력한다.

두 번째 줄부터 Q+1번째 줄에는 각 쿼리를 통해 변한 수열에서 경렬이가 구하고자 하는 부분 수열의 개수를 출력한다.

IO Example

예제 1
입력
4 1
4 2 2 4
2 5
출력
2
0

예제 2
입력
8 2
5 4 3 2 1 2 3 5
5 3
1 6
출력
3
3
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]