Masala Tarjimasi:

Levko massivlar bilan o'ynashni yaxshi ko'rar ekan. Unda a1, a2, a3 ... an ko'rinishidagi massiv bor ekan. U massiv bilan o'ynash davomida, shu massiv ustida 2 xil amal bajarar ekan.

Bu amallar:
1. Birinchi turdagi amal bu: massivdagi indekslari L dan R gacha bo'lgan elementlarni D ga oshirish. ya'ni dasturlash tili bilan aytganda:

for(int i = L; i<=R; i++)
    a[i]+=D;

1. Ikkinchi turdagi amal: massivdagi indekslari L dan R gacha bo'lgan elementlar ichidan maksimalini topish.

for(int i = L; i<=R; i++)
   mx = max(mx, a[i]);

Levko sevimli massivini yo'qotib qo'yibdi shuning uchun u sizdan yordam so'rayapdi. Unda faqat massiv ustida bajarilgan amallar ro'yhati bor holos. Levkoga massivni tiklashda yordam bering.

Kiruvchi ma'lumotlar:

Birinchi bo'lib bizga n va m ketma ket kiritiladi.

n -> massiv elementlari soni; 1<=n<=5000
m -> massiv ustida bajarilgan amallar soni; 1<=m<=5000

Keyingi m qatorda quyidagi tartibda ma'lumotlar kiritiladi:
1. t -> bajarilgan operatsiya tipi. Agar t = 1 bo'lsa u holda birinchi turdagi amal bajarilgan(qo'shish), agar t = 2 bo'lsa ikkinchi turdagi amal bajarilgan(maksimal topish). 1<=t<=2
2. l -> chap chegara 1<=l<=n
3. r -> o'ng chegara 1<=r<=n
4. d yoki m -> bajarilayotgan amal turiga qarap, agar birinchi turdagi amal bo'lsa qo'shilayotgan son, agar ikkinchi turdagi amal bo'lsa topilgan maksimal son.

Chiquvchi ma'lumotlar:

YES -> agar yechim bo'lsa
NO -> agar yechim bo'lmasa
Agar yechim bo'lsa YES yozuvi ostida massiv elementlari chiqarilsin. Massiv elementlari modul jihatda 1e9 dan oshmaydi. |ai|<=1e9

O'zlaringizda g'oya chiqarib ishlashga urinib ko'ringlar!!! Agar bo'lmasa quyidagi yechimda foydalaninglar.

Masala Yechimi:

for(int i = L; i<=R; i++)
    diff[i]+=D;

Bu kodni bajarish orqali biz diff massivda hozirgi holatdagi massiv boshlang'ich massiv elementlaridan qanchaga farq etishini saqlab qo'yamiz. Masalan hozirda diff[2] = 4 bo'lsa demak a massivning 2 elementi boshlang'ich holatda 4 ga katta.

Endi ikkinchi turdagi amallarni ko'rib chiqsak. Bu amallarni qayta ishlash murakkabroq va bu amallar yordamida biz qidirilayotgan massivni hosil qilib olishimiz mumkin. Bu amallarni qayta ishlash uchun bizga javob massivni saqlab qo'yuvchi massiv kerak bo'ladi. Bu massivni ans deb nomlaymiz (ans -> answer -> javob) va uni masala shartidagi massiv elemntlaringing maksimal qiymati bilan to'ldiramiz ya'ni:

for(int i = 0; i<=5000; i++){
    ans[i] = 1e9;
}

Massivning bu holatda turishi bizga keyingi operatsiyalarda kerak bo'ladi. Endi eng qiziqarli qismi. Agar bizga ikkinchi turdagi amal berilsa, L -> R oraliqdagi faqatgina topilgan maksimal elementdan katta bo'lganlarini, shu topilgan maksimal bilan almashtiramiz. Ammo almashtirish davomida shu massiv elementi boshlang'ich holatda qancha siljiganinigam hisobga olamiz:

for(int i = L; i<=R; i++)
    ans[i] = min(ans[i], M - diff[i]);

M -> bu yerda L — R oraliqda topilgan maksimal.

Shu tarzda barcha amallarni qayta ishlab chiqsak biz natijaviy massivni qo'lga kiritamiz. Ammo bu hali javob degani emas. Biz bu massivni to'g'ri hosil qilinganligiga ishonch hosil qilishimiz kerak. Massivni tekshirish uchun biz diff massivni tozalatmiz ya'ni nollar bilan to'ldiramiz va ok nomli mantiqiy o'zgaruvchi hosil qilamiz. Keyinchalik amallardan yana bir marta o'tib chiqamiz. Agar birinchi turdagi amal kelsa diff massivini yangilaymiz. Agar ikkinchi turdagi element kelsa L — R oraliqda M kamida bir marta uchraydimi yo'qmi tekshiramiz akar bu element uchramay qolsa demak javob NO. Agar barcha M lar uchrasa YES javobini chiqaramiz va massivni chiqaramiz. Tekshirish kodi quyidagicha:

    for(int i = 0; i<= r[i]; j++)
                if(ans[j] + diff[j] == d[i])
                {
                    ok = 1;
                    break;
                }
        }
    }

Shu yechimdan foydalanib kodni o'zingiz yozishga urinib ko'ring. Agar o'xshamasa quyidagi ko'dni o'rganib chiqishingiz mumkin.