Levko and Array Recovery masalasi yechimi

Правка en11, от Muhammad_Rahimov, 2017-07-28 17:17:25

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:

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.

kod

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en19 Английский Muhammad_Rahimov 2017-07-28 17:51:26 0 (published)
en18 Английский Muhammad_Rahimov 2017-07-28 17:51:11 207 (saved to drafts)
en17 Английский Muhammad_Rahimov 2017-07-28 17:31:12 0 (published)
en16 Английский Muhammad_Rahimov 2017-07-28 17:30:41 102
en15 Английский Muhammad_Rahimov 2017-07-28 17:29:41 90 Tiny change: '"<<endl;\n ' -> '"<<endl;\n\n '
en14 Английский Muhammad_Rahimov 2017-07-28 17:25:03 1118
en13 Английский Muhammad_Rahimov 2017-07-28 17:21:36 140
en12 Английский Muhammad_Rahimov 2017-07-28 17:18:07 10 Tiny change: 'od">\n\n</kod>\n\n</spo' -> 'od">\n\n</spoiler>\n\n</spo'
en11 Английский Muhammad_Rahimov 2017-07-28 17:17:25 1204
en10 Английский Muhammad_Rahimov 2017-07-28 16:43:42 642
en9 Английский Muhammad_Rahimov 2017-07-28 16:33:38 556
en8 Английский Muhammad_Rahimov 2017-07-28 16:29:02 254
en7 Английский Muhammad_Rahimov 2017-07-28 16:26:45 32
en6 Английский Muhammad_Rahimov 2017-07-28 16:26:04 381
en5 Английский Muhammad_Rahimov 2017-07-28 16:23:10 156
en4 Английский Muhammad_Rahimov 2017-07-28 16:01:28 2 Tiny change: 'ytganda:\n<pre>\n<' -> 'ytganda:\n\n<pre>\n<'
en3 Английский Muhammad_Rahimov 2017-07-28 15:59:10 141 Tiny change: ' aytganda:<br>\n<pre>\n<' -> ' aytganda:\n<pre>\n<'
en2 Английский Muhammad_Rahimov 2017-07-28 15:54:16 1009
en1 Английский Muhammad_Rahimov 2017-07-28 15:43:47 691 Initial revision (saved to drafts)