Educational Segment Tree Contest - ITEZ1

View as PDF
Submit solution
Points: 0.10
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
Educational Segment Tree Contest - Anh Long
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hảo Hảo, cảm nhận từng giây hạnh phúc

Bạn là chủ một hệ thống nhà hàng chuyên bán mì ăn liền. Tại sao lại là mì ăn liền, đó là vì "dẫu thời gian mang đến nhiều đổi thay, những điều tuyệt vời vẫn còn đó trên mảnh đất này. Hảo Hảo, cảm nhận từng giây hạnh phúc".

Khi xem các quảng cáo mì ăn liền, ta đều thấy cả nhà cùng ngồi ăn mì và cười hạnh phúc, hay là người mẹ đi làm và mua mì về thì cả nhà cùng nhau reo hò. Mì thường được làm từ "trứng vàng" (~\le~15g/1kg) hay khoai tây (~\approx~20g/1kg) rất tốt cho sức khỏe, trong khi đó thành phần sắn thì chỉ là thành phần phụ (~\approx~900g/1kg). Nhà hàng của bạn có n gói mì đủ loại, mỗi gói có độ ngon là ~a_i~ (~|a_i|\le10^9~). Bạn cần xử lý 2 loại truy vấn như sau:

  • Loại 1 có dạng ~1~ ~x~ ~y~: Nấu gói mì ở vị trí thứ ~x~ và mua gói mì có độ ngon ~y~ thay vào đó. (~1\le x \le n,|y|\le10^9~)
  • Loại 2 có dạng ~2~ ~l~ ~r~: In ra độ ngon lớn nhất của các gói mì từ vị trí ~l~ đến ~r~ (~1\le l\le r\le n~)

Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input

  • Dòng đầu tiên là số ~n~ là số các gói mì (~1\le n\le10^5~)
  • Dòng 2 là ~n~ số nguyên là độ ngon của các gói mì (~|a_i|\le10^9~)
  • Dòng 3 là 1 số ~q~ là số truy vấn(~1\le q \le10^5~)
  • ~q~ dòng sau, mỗi dòng là một truy vấn thuộc một trong hai loại trên.

Output

Với mỗi truy vấn loại 2, in ra câu trả lời trên một dòng

Sample Input

5
1 4 2 3 5
6
2 1 3
1 3 3
2 1 5
2 3 5
1 2 3
2 2 4

Sample Output

4
5
5
3

Comments

Please read the guidelines before commenting.


  • -1
    nictysine1  commented on Feb. 12, 2025, 3:04 p.m.

    ai nghĩ ra bài này nhặn e 1 lạy hay quá ahihi


  • -4
    ngthvnh123  commented on Dec. 12, 2024, 2:08 p.m.

    Code không dùng segment tree vẫn ac :))


  • -28
    Tuandunglopa1  commented on Oct. 12, 2024, 2:58 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -4
      yh_nguyenthaian  commented on Oct. 13, 2024, 3:07 a.m.

      comment bait ác


    • -8
      hh123123  commented on Oct. 12, 2024, 3:50 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -7
    khiemgia1105  commented on Oct. 4, 2024, 7:48 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -15
    Hugcodega  commented on Sept. 3, 2024, 2:56 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 1
    k30hongvuong  commented on July 30, 2024, 10:59 a.m.

    cảm ơn b nhiều kekeke


  • -1
    quan08  commented on July 25, 2024, 2:05 p.m.

    do de kho hay do toi qua bel vay😭


  • 16
    KAKOII  commented on Feb. 16, 2024, 6:14 a.m. ← edited

    Code Scratch 💀💀💀:

    code


    • -2
      pppssslc  commented on Dec. 24, 2024, 3:46 p.m.

      amazing


  • -3
    thethethe  commented on Sept. 21, 2023, 3:09 a.m. ← edited

    hum


  • -6
    hieuhfgr  commented on Sept. 6, 2023, 11:43 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -4
      xingyi  commented on March 12, 2024, 12:03 p.m. ← edited

      Minh cung the


    • -3
      HaoNoChetChua  commented on Dec. 30, 2023, 3:13 a.m.

      minh thich an mi hao no


    • -11
      vdtue  commented on Sept. 27, 2023, 8:42 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -5
      tonblan  commented on Sept. 13, 2023, 9:57 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -1
    UruLuka  commented on Aug. 15, 2023, 2:22 p.m.

    😋


  • 129
    ntkiet  commented on June 10, 2022, 2:48 a.m.

    vì có cả số âm nên mọi người nhớ trong hàm get return là -1e9 chứ đừng là 0 nhe :(