cho.sh

수열과 쿼리 41

아직 제출이 없습니다시간 제한5초메모리 제한1024 MB

문제

길이가 NN인 수열 A_1,A_2,…,A_NA\_1, A\_2, \ldots, A\_N 이 주어진다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 0 l r x: l≤i≤rl \le i \le r 에 대해 A_i=max(A_i,x)A\_i = max(A\_i, x) 를 배정한다.
  • 1 l r: max(0,max_l≤u≤v≤r(∑_i=uvA_i))max(0, max\_{l \le u \le v \le r} (\sum\_{i = u}^{v} A\_i)) 를 출력한다.

입력

첫 번째 줄에 수열의 길이 NN 과 쿼리의 수 QQ 가 주어진다.

두 번째 줄에 수열 AA 의 원소 A_1,A_2,...,A_NA\_1, A\_2, ..., A\_N 이 주어진다.

이후 QQ 개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다.

출력

모든 1 l r 형태의 쿼리에 대해 정답을 한 줄에 출력하라.

제한

  • 1≤N≤100,0001 \leq N \leq 100\\,000
  • 1≤Q≤200,0001 \leq Q \leq 200\\,000
  • −109≤A_i,x≤109-10^9 \le A\_i, x \le 10^9
  • 1≤l≤r≤N1 \le l \le r \le N