문제 설명
길이 N의 배열이 주어진다. (1 <= N <= 53129)
각 배열의 원소는 928374623이하이고, 0 이상이다.
여기에 연산 Q개를 처리해야 한다. (Q <= 57253)
주어지는 연산들은 다음 중 하나이다. 아래에서 [l, r]은 배열의 l, l+1, ..., r번째 원소로 이루어진 부분배열을 말하고, 배열의 원소는 1번부터 시작한다. (1-based index)
1 l r : 수열의 [l, r]을 뒤집는다. (1<=l<=r) 단, l, r 중 하나라도 배열의 크기를 초과하면 아무것도 하지 않는다.
2 l r : 수열의 [l, r]구간을 전부 삭제한다. (1<=l<=r) 단, l, r 중 하나라도 배열의 크기를 초과하면 아무것도 하지 않는다.
3 i k : 수열의 i번 원소부터 시작하여 인접한 k개 원소씩 짝을 짓고, 둘 중 최소인 값을 남기고 나머지를 전부 지운다. (마지막에 k개 미만의 원소가 짝지어질 수 있음을 유의하라) i가 배열의 크기를 초과하면 아무것도 하지 않는다. (i>=1, k>=2)
4 i k : 수열의 i번 원소부터 시작하여 인접한 k개 원소씩 짝을 짓고, 둘 중 최대인 값을 남기고 나머지를 전부 지운다. (마지막에 k개 미만의 원소가 짝지어질 수 있음을 유의하라) i가 배열의 크기를 초과하면 아무것도 하지 않는다. (i>=1, k>=2)
5 l r : 수열의 [l, r]구간을 뽑은 후, 수열의 맨 앞으로 보낸다. 단, l, r 중 하나라도 배열의 크기를 초과하면 아무것도 하지 않는다. (1<=l<=r)
6 l r : 수열의 [l, r]구간을 뽑은 후, 수열의 맨 뒤로 보낸다. 단, l, r 중 하나라도 배열의 크기를 초과하면 아무것도 하지 않는다. (1<=l<=r)
7 x : 수열의 제일 왼쪽 원소를 뽑아 제일 뒤로 보내는 과정을 x회 반복한다. 배열이 비어 있다면 아무것도 하지 않는다.
8 x : 수열의 제일 오른쪽 원소를 뽑아 제일 앞으로 보내는 과정을 x회 반복한다. 배열이 비어 있다면 아무것도 하지 않는다.
9 l r x : 수열의 [l, r]구간의 원소에 전부 x를 더한다. 단, l, r 중 하나라도 배열의 크기를 초과하면 아무것도 하지 않는다. (1<=l<=r)
10 l r x : 수열의 [l, r]구간의 원소를 전부 x로 바꾼다. 단, l, r 중 하나라도 배열의 크기를 초과하면 아무것도 하지 않는다. (1<=l<=r)
11 i x : 수열의 i번째 원소 바로 뒤에 x를 추가한다. 단, i=0이면 맨 앞에 추가한다. 단, i가 0이 아니면서 배열의 크기를 초과하면 아무것도 하지 않는다.
12 l r : 수열의 [l, r]구간의 최솟값을 출력하라. 단, l, r 중 하나라도 배열의 크기를 초과하면 –1을 출력하라.
13 l r : 수열의 [l, r]구간의 최댓값을 출력하라. 단, l, r 중 하나라도 배열의 크기를 초과하면 –1을 출력하라.
14 l r : 수열의 [l, r]구간의 합을 출력하라. 단, l, r 중 하나라도 배열의 크기를 초과하면 –1을 출력하라.
15 : 수열의 크기를 출력하라.
16 x : x 이상이며 가장 앞에 있는(인덱스가 최소인) 원소의 인덱스를 출력하라. 배열이 비어 있거나 x이상인 원소가 없다면 –1을 출력한다.
출제자는 아직 문제가 너무 간단해서 연산을 더 추가하려 했으나, 그만 아이디어가 바닥나버렸다!
출제자가 연산들을 더 추가하기 전에 빨리 이 문제를 풀어버리자.
(단, 연산이 실행되는 전체 과정에서 배열의 모든 원소는 1148392648574930293을 초과하지 않는다. 또한, 입력으로 주어지는 모든 수는 0 이상 958375323이하의 자연수이다. 즉, 각 쿼리에서 l이 1억이 넘는 값이 들어올 수 있다.
채점 데이터의 20%는 전체 데이터 수의 1/5를 초과하지 않음을 보장할 수 있다.
입력 설명
첫 줄에 N이 입력된다.
두 번째 줄에 초기 상태의 배열이 입력된다.
세 번째 줄부터 Q+2번째 줄까지 위에서 주어진 16가지의 쉽고 간단한 쿼리들 중 하나가 주어진다.
입력값의 범위는 문제에 명시되어 있다.
출력 설명
매 쿼리마다 연산을 실행한 결과를 출력하라.
입력 예시 Copy
10 21
1 2 3 4 5 6 7 8 9 10
14 1 1
1 1 5
14 1 1
10 1 5 3
14 3 4
5 6 10
12 1 5
13 1 5
10 1 5 1
12 1 5
13 1 5
15
2 6 10
15
11 1 2
14 1 2
15
6 1 2
14 1 2
16 1
16 100000
출력 예시 Copy
1
5
6
6
10
1
1
10
5
3
6
2
1
-1