Polynomial Queries

View as PDF



Author:
Problem types
Points: 1900 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Cho một mảng gồm \(N\) phần tử. Nhiệm vụ của bạn là thực hiện các truy vấn sau:

  • \(1\) \(a\) \(b\): Tăng phần tử đầu tiên trong đoạn \([a, b]\) lên \(1\), phần tử thứ hai lên \(2\), phần tử thứ ba lên \(3\), \(\ldots\)
  • \(2\) \(a\) \(b\): Tính tổng các phần tử trong đoạn \([a, b]\).

Input

  • Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) \((N, Q \leq 2 \times 10^{5})\): kích thước mảng và số truy vấn.
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1}, A_{2}, \ldots, A_{N}\) \((1 \leq A_{i} \leq 10^9)\).
  • \(Q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng sau:
    • \(1\) \(a\) \(b\) \((1 \leq a \leq b \leq N)\).
    • \(2\) \(a\) \(b\) \((1 \leq a \leq b \leq N)\).

Output

  • In ra kết quả cho các truy vấn \(2\).

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2 \times 10^{3}\).
  • Subtask \(2\) (\(50\%\) số điểm): không có rằng buộc gì thêm.

Example

Test 1

Input
5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5 
Output
17
32

Comments


  • 0
    Haidepzai    3:35 p.m. 1 aug, 2024

    tưởng gì chứ bài này thì tôi KHÔNG LÀM ĐƯỢC


    • -11
      minhtuanitk20    1:21 p.m. 27 oct, 2021

      This comment is hidden due to too much negative feedback. Click here to view it.