For given \(N\) numbers \(D_1 , \cdots D_N \), write a program runs procedure \(f(X)\) for given \(Q\) queries, \(X_1 , X_2 , \cdots X_Q \).
procedure f(X):
for i = 1 .. N:
X = floor ( X / D[i] )
return X
양의 정수 \(X,a,b\)에 대해 다음의 식이 성립한다.
$ (X / a) / b = X / ab $
(/는 정수 나눗셈)
따라서 \(D_i\)들을 다 곱해두는데, 그냥 무식하게 곱하면 당연히 \(10^{900000}\)으로 오버플로우가 나게 된다.
\(X\)도 제한이 \(10^9\)로 작으므로(!), 곱한 값이 \(10^{9}\)보다 커지게 되면 어떤 \(X\)에 대해서도 답이 0이 된다. 따라서 \(10^{9}\)보다 커지게 되는 순간 곱하는 것을 멈춰도 무방하다.
쿼리는 미리 구해놓은 \(\prod D\)로 \(O(1)\)에 처리할 수 있다.
This special equality holds for natural numbers \(X,a,b\) and integer quotient operation /.
$ (X/a)/b = X/ab $
So we multiply all \(D_i\)s, but we need another idea to avoid overflow.
We have another constraint that \(X\) cannot exceed \(10^9\), then we know if the product of \(D_i\) exceeds \(10^{9}\), the value of \(f(X)\) will be always 0. So in this case, we have no difference whether we consider \(\prod_{i=1}^{j} D_{i}\) as \(\prod_{i=1}^{N} D_{i}\) or not.
We can run each query in \(O(1)\) time with precalculated \(\prod D\).
\(O(N + Q)\)
2. L - R Queries (LRQUER)
Tag : Data Structure, Merge Sort Tree, Segment Tree
수열 \(A_{1}, A_{2}, \cdots A_{N}\)이 주어져 있다. 다음의 쿼리를 \(Q\)번 수행하는 프로그램을 작성하여라.
1 L R : \(M \in [L,R]\)에 대해 \((A_M-A_L) \cdot (A_R-A_M)\)의 최댓값을 출력한다.
2 i v : \(A_i\)를 \(v\)로 바꾼다.
\(1 \le \text{TESTCASE} \le 1000\)
\(1 \le \sum N \le 2 \cdot 10^{5}\)
\(1 \le \sum Q \le 2 \cdot 10^{5}\)
\(1 \le A_i , v \le 10^{9}\)
Construct a Special Segment tree whose each node \([s,e]\) contains a binary search tree, such as std::multiset that I used,which stores all numbers in \(A_s , \cdots , A_e \) in ascending order.
Running the second query (update query) is very simple : Just update all BSTs contains \(A_i\).
We need to observe the shape of formula stated in problem. If we expand it and sort it by descending order on \(A_m\), we can get the equation of parabola \(-A_{m}^{2} + (A_l + A_r)A_m - A_{l}A_{r}\). So the query eventually requires \(A_m\), which belongs to \(A_l \cdots A_r\) and the closest to \(\frac{A_l + A_r}{2}\). And it can be implemented with BST easily, or std::multiset::lower_bound() function if you use std::multiset.