https://codeforces.com/contest/1136/problem/EIf we have a segment tree which can perform the following operations, we can directly solve this problem.1. For $l \le i \le r$, $A_i \gets \max(A_i, x)$ 2. For $l \le i \le r$, $A_i \gets A_i +…