Informatica Online Judge

  비범한 기범이 (Large) [1951 / 079F]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (33rd 윤혁중)]
Writer ID : [gs15075]

Background

n차원의 벡터는 일반적으로 $R^n$의 벡터로 표현할 수 있는데, $R^n$의 벡터란 n개의 실수의 순서쌍이다.

예를 들어 (3, 4)나 (-1, 0)은 $R^2$의 벡터이고, (0, 1, 2, 3)은 $R^4$의 벡터다.

선형대수학에서, 보통 $R^n$의 두 벡터 v=(v_1, v_2, …, v_n)와 u=(u_1, u_2, …, u_n) 사이의 거리(distance)는 다음과 같이 정의된다.



그러나 너무나 비범한 머리를 가진 기범이는 그 것이 마음에 들지 않아버렸고, 두 벡터 사이의 거리를 새롭게 정의하려 한다.

기범이는 선형대수학을 좋아하는 아이답게 때문에 상수를 좋아한다. 그래서 가장 먼저 정상수의 노래를 들으며 n차원의 상수 테이블을 준비했고, 두 벡터 v와 u의 거리를 두 벡터의 "내부에 있는" 상수들의 총합으로 정의했다.

어떤 상수 c = (c_1, c_2, …, c_n)가 두 벡터 v=(v_1, v_2, …, v_n)와 u=(u_1, u_2, …, u_n)의 ‘내부에 있는’ 것은 모든 $i = 1, 2, …, n$에 대하여 $c_i$가 폐구간 [$min(v_i, u_i)$, $max(v_i, u_i)$] 사이에 속한다는 것을 의미한다.

그러던 어느 날 정상수의 랩 스타일이 너무 진부하여 화가난 정상수의 팬 기범이는 대리만족을 위해 자신의 상수 테이블이 계속 바뀌게 하였다.

Input

차원 n, 좌표의 최댓값 m이 주어지고, 상수테이블이 주어진다.
쿼리의 개수 q가 주어진다.

그 후 q개의 입력이 추가로 들어온다.

0 -> n개의 좌표와 상수 == 상수체인지

1 -> n개의 좌표 두개(각 좌표는 1 이상 m 이하) == 두 벡터사이의 거리 출력

[Sub-Task Info]
#Small : n=1, m <= 1000, q <= 50000
#Large: n=1 or n=2, m <= 1000, q <= 50000

Output

1로 시작하는 쿼리에 대한 두 벡터 사이의 거리를 차례로 출력한다.

IO Example

입력
1 100
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
5
1 2 29
1 1 100
1 100 1
1 2 2
1 52 37

출력
154
550
550
2
92

입력2
2 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
5
1 2 1 8 1
1 1 2 1 8
1 1 1 10 10
1 1 10 10 1
1 3 3 8 6

출력2
7
35
550
550
108

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