악마와 예쁜 수열 サブタスク 3秒 512MB
問題
길이 n 짜리 수열 a[1] ~ a[n] 이 있을 때, "예쁜 수열" 은 아래와 같이 정의한다.
" 1 ≤ i ≤ n 인 모든 i 에 대해, a[i] ≥ i 이면, 수열 a 는 예쁜 수열이다. "
예를 들어, [2, 5, 4] 는 예쁜 수열이다. a[1] ≥ 1, a[2] ≥ 2, a[3] ≥ 3 이 모두 성립하기 때문이다.
[5, 1, 4] 는 예쁜 수열이 아니다. a[2] ≥ 2 가 성립하지 않기 때문이다.
자연수로 구성된 길이 N 수열이 입력된다.
우리의 목표는, 모든 ‘연속 부분 수열’ 중 예쁜 수열의 개수를 구하는 것이다.
예를 들어, [2, 4, 2, 3] 의 모든 연속 부분 수열을 나열하면
[2], [4], [2], [3]
[2, 4], [4, 2], [2, 3]
[2, 4, 2], [4, 2, 3]
[2, 4, 2, 3] 으로 총 10개다.
이 중 예쁜 수열은
[2], [4], [2], [3], [2, 4], [4, 2], [2, 3], [4, 2, 3] 으로 8개다.
단, 우리를 방해하는 악마가 Q 마리 있다.
각 악마는, 1 ≤ x ≤ N 인 x 를 하나 정해서, 입력 수열의 x 번째 수를 강제로 p 로 바꾼다.
즉, a[x] = p 가 된다.
각 악마의 방해 공작 후, 연속 부분 수열 중 예쁜 수열의 개수를 출력하자.
모든 악마는 서로 독립적이다.
즉, 한 악마의 방해 공작 후, 수열은 다시 처음 상태로 돌아간다. 그 후, 다음 악마의 방해 공작이 시작된다.
入力
첫 줄에 수열의 길이 N 이 입력된다. ( 1 ≤ N ≤ 20만 )
두 번째 줄에 N 개의 숫자 a[1], a[2], ..., a[N] 이 입력된다. ( 각 숫자들은 1 이상 N 이하의 자연수 )
세 번째 줄에 악마의 개수 Q 가 입력된다. ( 0 ≤ Q ≤ 20만 )
네 번째 줄부터, Q 개의 줄에 걸쳐 각 악마의 정보 x, p 가 입력된다. ( 1 ≤ x, p ≤ N 인 자연수 )
이는 a[x] 를 p 로 바꾼다는 것을 의미한다.
다시 한 번, 각 악마는 서로 독립적이라는 것에 주의하자.
出力
출력은 총 Q+1 개의 줄로 구성된다.
첫 줄에는, 악마의 방해 공작이 시작되기 전의 예쁜 연속 부분 수열 개수를 출력한다.
그 후, K 번째 줄에는, K - 1 번째 악마의 방해 공작이 이루어진 이후의 예쁜 연속 부분 수열 개수를 출력한다. ( 2 ≤ K ≤ Q + 1 )
部分問題
| 番号 | 点数 | 条件 |
|---|---|---|
| #1 | 10点 | N ≤ 10, Q ≤ 10 |
| #2 | 40点 | Q = 0 |
| #3 | 50点 | 제약 조건 없음 |
例題
4
2 4 2 3
3
1 3
4 1
4 2
8
8
6
7
악마가 방해하기 전 수열은 [2, 4, 2, 3] 이고, 문제 지문에 의해 이 경우 답은 8 이다.
첫 번째 악마가 방해하면 [3, 4, 2, 3] 이 되고, 이 경우 답은 8 이다.
두 번째 악마가 방해하면 [2, 4, 2, 1] 이 되고, 이 경우 답은 6 이다.
세 번째 악마가 방해하면 [2, 4, 2, 2] 가 되고, 이 경우 답은 7 이다.
ログインしないとコードを書けません。