zzzzzz just use cream

현재 온라인 마켓에 있는 상품을 $1$번 크림부터 $n$번 크림이라고 하자. 어떤 두 상품 $i,j$가 $A_i < A_j$이고 $D_i \leq D_j$를 만족한다면, $i$번 크림은 어떤 날짜에서도 $j$번 크림보다 나은 선택이 될 수 없다. 따라서 실제로 사용될 가능성이 있는 크림만 남기면, 남은 크림들은 유통기한 오름차순으로 보았을 때 효과가 엄격히 내림차순이다.

이 남은 크림들의 집합을 $C$라고 하자. $C = \{i_1,i_2,\ldots,i_r\}$이고 $D_{i_1} < D_{i_2} < \cdots < D_{i_r}$라면, 최적 사용에서는 $i_t$번 크림을 총 $D_{i_t}-D_{i_{t-1}}$일 동안 사용한다. 여기서 $D_{i_0}=0$이다. 따라서 실제로 사용한 크림들의 가격 합은

$$S=\sum_{t=1}^{r} P_{i_t}(D_{i_t}-D_{i_{t-1}})$$

이다.

온라인 마켓의 모든 상품 가격 합을 $T$라고 하면, 다다스가 구매한 크림들의 전체 가격 합은 $XT$이다. 그러므로 각 2번 질의의 답은 $XT-S$이다.

집합 $C$는 유통기한을 기준으로 정렬된 std::set으로 관리한다. 새 상품 $(a,d,p)$가 추가될 때, $C$에서 유통기한이 $d$ 이상인 첫 원소를 찾는다. 이 원소의 효과가 $a$보다 크면 새 상품은 지배되므로 $C$에 넣지 않는다. 그렇지 않으면 유통기한이 $d$ 이하이면서 효과가 $a$보다 작은 원소들을 뒤에서부터 지운 뒤 새 상품을 삽입한다.

$S$는 각 원소가 자신의 직전 원소와 만드는 구간 길이에 기여하는 값을 이용해 국소적으로 갱신할 수 있다. 원소 하나를 삭제하거나 삽입할 때 영향을 받는 항은 그 원소와 바로 다음 원소의 항뿐이다. 각 상품은 $C$에 최대 한 번 삽입되고 최대 한 번 삭제되므로 전체 시간 복잡도는 $O((N+Q)\log(N+Q))$이다.

Solution written by GPT5.5