Giải quyết mỗi truy vấn với độ phức tạp \(O(n)\), bằng cách làm theo đúng như mô tả đề bài (dùng vòng lặp)
Độ phức tạp: \(\mathcal{O}(n \cdot q)\)

Trong mọi thời điểm, mảng \(a\) sẽ bao gồm những đoạn các phần tử liên tiếp có giá trị giống nhau. Do \(a_i, y \le 2 \times 10^13\) nên tối đa cũng chỉ có \(\log(a) \le 51\) đoạn giá trị khác nhau là \(1,2,4,8, \dots, 2^50\).
Ta lưu mảng dưới dạng: đoạn các phần tử, từ \(l_i\) tới \(r_i\) và có giá trị là \(v_i\). Với mỗi truy vấn, ta duyệt qua toàn bộ đoạn này để xử lý:

• Với truy vấn cập nhật: Ta duyệt trong mọi đoạn có \(l_i \le x\) và tăng giá trị lên, có thể sẽ cần gộp hoặc xóa đoạn.
• Với truy vấn hỏi: Ta xem trong từng đoạn giá trị có \(r_i \ge u\), xem thử số \(c\) hiện tại có thể trừ cho tối đa bao nhiêu giá trị \(v_i\) thuộc đoạn này?

Vì độ dài của dãy giá trị trên luôn \(\le O(\log)\) tại mỗi thời điểm, đây cũng là độ phức tạp mỗi truy vấn.

Độ phức tạp: \(\mathcal{O}(q \log_2(a+y))\)

Tại vị trí \(u\), ta dùng TKNP để có được vị trí \(v\) xa \(u\) nhất mà tổng \(a_u + a_{u+1} + \dots + a_v \le c\). Sau đó, đặt \(c \leftarrow c - (a_u+\dots+a_v)\).
Tiếp theo, lại tìm một vị trí \(u'\) đầu tiên sau \(u\) mà \(a_{u'} \le c\), rồi gán \(u \leftarrow u'\) .
Nhận xét: Sau mỗi lần trừ \(c\) đi một đoạn liên tiếp, giá trị của nó giảm đi ít nhất một nửa. Vậy chỉ có tối đa \(O(\log a)\) lần ta phải tìm kiếm như trên.
Độ phức tạp: \(\mathcal{O}(q\log n \log a)\).

Để tính nhanh các thao tác loại \(1\), ta dùng trick của mảng prefix-sum. Tạo mảng \(b\) ban đầu có \(b_i = 0\). Với truy vấn \(\text{1 x y}\), ta gán b[x] = max(b[x], y);. Sau mọi truy vấn loại 1, cập nhật b[i] = max(b[i], b[i+1]); rồi gán a[i] = max(a[i], b[i]);
Độ phức tạp: như subtask 3

Dựng một cây Segment Tree lazy update, cài đặt kỹ thuật TKNP trên cây (Segment tree walk). Cây này cần hỗ trợ những thao tác sau:

• Cập nhật giá trị của một đoạn
• Tìm vị trí đầu tiên trong mảng, có \(a_i \le X\) với \(X\) cho trước
• Tìm vị trí \(v\) xa \(u\) nhất trong mảng, có tổng \(a\) từ \(u\) tới \(v\) bé hơn bằng giá trị \(X\) với \(u,X\) cho trước

Độ phức tạp*: \(\mathcal{O}((n+q)\log n \log a)\).