Salary Queries

Xem PDF



Tác giả:
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một công ty có \(N\) nhân viên với với mức lương nhất định. Nhiệm vụ của bạn là theo dõi mức lương và thực hiện truy vấn.

Input

  • Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1\) tới \(N\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) là lương của mỗi người.
  • \(Q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong hai dạng sau:
  • \(!\) \(k\) \(x\): thay đổi lương của người thứ \(k\) thành \(x\).
  • \(?\) \(a\) \(b\): đếm số người có mức lương từ \(a\) tới \(b\).

Output

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

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 2.10^3\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^5\) với \(\forall i, 1 \leq i \leq N\).
  • Subtask \(3\) (\(40\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).

Example

Test 1

Input
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3 
Output
3
2

Bình luận


  • 0
    TMT    5:07 p.m. 9 Tháng 12, 2021

    khok that r ae oi
    =((


    • 5
      BeTapDi    10:00 a.m. 6 Tháng 9, 2020

      bài này làm nlog^2 qua k nhỉ :v, e thấy làm set khá hay 🙂

      2 phản hồi