시간을 달리는 직선들
다이아몬드 III의견: 0
\(N\)개의 직선이 있다. \(i\)번째 직선은 시각 \(t\)에서 값 \(f_i(t) = a_i \cdot t + b_i\) 를 가진다 (\(a_i \ge 0\)). 현재 시각은 \(0\)에서 시작한다.
다음 세 종류의 연산을 총 \(Q\)번 처리한다.
-
1 T: 현재 시각을 \(T\)로 진행시킨다. \(T\)는 현재 시각 이상임이 보장된다(시각은 절대 줄지 않는다). -
2 l r: 현재 시각에서 \(\max_{l \le i \le r} f_i(\text{현재 시각})\) 을 출력한다. -
3 i a b: \(i\)번째 직선을 \(a_i = a\), \(b_i = b\)로 바꾼다 (\(a \ge 0\)).
시각은 절대 줄지 않고 단조 증가한다.
\(1 \le N, Q \le 100{,}000\)
\(0 \le a_i \le 10^6\)
\(-10^9 \le b_i \le 10^9\)
\(0 \le T \le 10^9\)
\(1 \le l \le r \le N\), \(1 \le i \le N\)
첫 줄에 \(N\)과 \(Q\)가 주어진다.
다음 \(N\)개의 줄에 각 직선의 \(a_i\), \(b_i\)가 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 연산이 주어진다.
각 2 연산마다 구간 내 직선 값의 최댓값을 한 줄에 하나씩 출력한다.
3 5
2 0
0 5
1 1
2 1 3
1 3
2 1 3
3 2 3 0
2 1 3
5
6
9직선: f1=2t, f2=5, f3=t+1. 시각0에서 [0,5,1]의 최댓값 5. 시각3으로 진행: [6,5,4] 최댓값 6. 2번 직선을 3t로 변경 후 시각3: [6,9,4] 최댓값 9.
1 5
0 7
2 1 1
1 1000000000
2 1 1
3 1 1 0
2 1 1
7
7
1000000000직선 하나 f1=7(상수). 시각과 무관하게 7. 직선을 f1=t로 바꾸면 시각 10^9에서 10^9.
riseoj 작성
출처 Original
평가 및 의견
시간을 달리는 직선들
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
시간을 달리는 직선들