Cộng đoạn và truy vấn tổng, cực đại

Buổi 28 — Segment Tree Lazy Buổi 69-70 — Mock Tổng hợp Data-structures
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho dãy gồm $N$ số nguyên $A_1, A_2, \dots, A_N$ và $Q$ truy vấn:

  • 1 l r v: Cộng thêm $v$ vào tất cả các phần tử $A_i$ với $l \le i \le r$.
  • 2 l r: In ra hai số: tổng $\sum_{i=l}^r A_i$ và giá trị lớn nhất $\max_{l \le i \le r} A_i$.
Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$.
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng và giá trị lớn nhất trên một dòng.

Ví dụ
Input Output
5 3
1 2 3 4 5
2 1 5
1 2 4 3
2 1 5
15 5
24 7
Giới hạn

$1 \le N, Q \le 10^5$, $|A_i|, |v| \le 10^9$.

Draft saved