Cây phân đoạn (Segment Tree)

Submit solution
Points: 4 (partial)
Time limit: 2.0s
Memory limit: 977M
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Xyene tham gia cuộc thi lập trình có một bài tập như sau:

Cho dãy \(n\) \((1 \le n \le 100000)\) phần tử được đánh chỉ số từ \(1\) đến \(n\) và có \(q\) \((1 \le q \le 500000)\) thao tác tiến hành trên dãy này.

Mỗi thao tác là một trong bốn dạng sau:

\(C\:x\:v\) thay phần tử tại vị trí \(x\) bằng giá trị \(v\)

\(M\:l\:r\) xuất ra giá trị nhỏ nhất của tất cả các phần tử trong dãy từ chỉ số \(l\) đến chỉ số \(r\) kể cả hai mút.

\(G\:l\:r\) Xuất ra ước chung lớn nhất của tất cả các phần tử trong dãy từ chỉ số \(l\) đến chỉ số \(r\) kể cả hai mút.

\(Q\:l\:r\) Xuất ra số các phần tử trong dãy có giá trị bằng kết quả của phép truy vấn \(G\) \(l\) \(r\) kể các hai mút.

Biết rằng tại mọi thời điểm thì các phần tử của dãy nằm trong đoạn từ \([1, 10^9]\) .

Xyene đã biết bài này phải lập trình bằng cấu trúc dữ liệu cây phân đoạn (Segment Tree). Anh ấy vẫn thường xuyên luyện tập về cấu trúc này nhưng thi thoảng vẫn bị mắc lỗi, bạn hãy giúp anh ấy nhé.

Đầu vào

Dòng đầu chứa hai số \(n\) và \(q\).

Dòng thứ hai chứa \(n\) số nguyên dương là các phần tử của dãy ban đầu.

\(q\) dòng tiếp theo được mô tả theo định dạng ở trên.

Đầu ra

Với mỗi thao tác xuất ra câu trả lời tương ứng trên từng dòng

Ví dụ 1

Đầu vào:

5 5
1 1 4 2 8
C 2 16
M 2 4
G 2 3
C 2 1
Q 1 5

Đầu ra:

2
4
2

Ví dụ 2

Đầu vào:

5 2
1 1 2 2 2
Q 1 4
Q 3 5

Đầu ra:

2
3
Don Mills Online Judge

Comments


  • 1
    shioiori  commented on Oct. 30, 2022, 1:22 p.m.

    Mình vừa update lại test bài này, mọi người có thể thử submit nhé :D


    • 1
      nqson  commented on Oct. 31, 2022, 12:48 a.m.

      chị update thêm 1 test bé để kiểm tra với thuật toán vét cạn chắc chắn cây chạy đúng đi


    • 1
      nqson  commented on Oct. 31, 2022, 12:42 a.m.

      sáng dậy tự nhiên thấy AC thêm 1 bài mà không cần submit :v


      • 0
        ZeroCoder  commented on Oct. 31, 2022, 3:20 a.m.

        Hết nước chấm


  • 1
    TICHPX  commented on Nov. 19, 2019, 12:10 a.m.

    Test chưa chuẩn cần kiểm tra lại