Masala #0758
Kadane (so'rovli) (HARD)
Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov beriladi, har bir so'rovda massivning \(K\)-elementi qiymati \(X\) ga o'zgaradi.
Sizning vazifangiz o'zgargan massivdan eng katta yig'indiga ega qism massiv topish (bu turdagi masalani eng tez yechib beruvchi algoritm nomi: Kadane) !
Siz qism massiv summasini chop eting
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] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.
Keyingi \(Q\) ta qatorda so'rovlar beriladi.
Chegaralar:
\(1 ≤ N, Q ≤ 2 * 10^5\)
\(-10^9 ≤ A[i], X ≤ 10^9\)
\(1 ≤ K ≤ N\)
Chiquvchi faylda har bir so'rovdan keyin massivda eng katta Kadane qiymatini chiqarish!
# | input.txt | output.txt |
---|---|---|
1 |
1 1 1 1 10 |
10 |