Masala #69U9WBLNGT

Xotira 512 MB Vaqt 1000 ms
14
Muallif: Xajiyev

Persistent Segment Tree (HARD)

Ushbu masalada massivlar soni ko'payib boradi.

Sizga dastlab N va Q mos ravishda N ta elementdan iborat A massiv uzunligi va shu massiv ustida amalga oshiriladigan Q ta so'rovlar soni beriladi, quyidagi so'rovlarning 3-turida massiv yana bittaga ko'payadi.

Sizning vazifangiz quyidagi so'rovlarga javob beruvchi ma'lumotlari tuzilmasini tuzish albatta o'z o'rnida har bir 2-turdagi so'rovga javob qaytarish:

  • 1 ID X Y bu so'rovda siz ID-massivning X-elementini Y ga o'zgartirishing
  • 2 ID L R bu so'rovda siz ID-massivning [L, R] oraliqdagi elementlari yig'indisini chiqarish
  • 3 ID bu so'rovda siz ID-massivda yana bir nusxa oling shunda sizning massivlaringiz soni yana bittaga ko'payadi

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q(1≤N,Q≤2*10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i](1≤A[i]≤10^9)\) sonlari.

Keyingi \(Q\) ta qatorda so'rovlar beriladi.

Chegaralar:

\(1≤N,Q≤2∗10^5\)

\(1 ≤A[i],Y≤10^9\)

\(1≤L≤R,X≤N\)


Chiquvchi ma'lumotlar:

Chiquvchi faylda faqat 1-testdagi javobni chiqaring.


Misollar
# input.txt output.txt
1
3 15
1 2 3
3 1
3 2
3 3
3 4
1 1 1 5
1 2 1 50
1 3 1 500
1 4 1 5000
1 5 1 50000
2 1 1 3
2 2 1 3
2 3 1 3
2 4 1 3
2 5 1 3
3 5
10
55
505
5005
50005