Optimal Milking

Çiftçi Jonh içinde N tane süt sağma makinesı olan yeni bir çiftlik satın aldı (1 <= N <= 40,000), tabi ki makineler 1'den N'e kadar numaralandırılmış ve yan yana dizilmiştir. Makine i'nin günlük süt sağma kapasitesi M(i) birimdir (1 <= M(i) <= 100,000).

Ancak makineler birbirlerine çok yakın kuruldukları için i. makinenin çalıştırıldığı günlerde i-1. ve i+1. makineler kullanılamamaktadır. Çiftçi John az önce belirtilen kurala sadık kalarak her gün istediği makineleri çalıştırabilmektedir.

Çiftçi John önümüzdeki D (1 <= D <= 50,000) gün boyunca her gün maksimum kaç birim süt sağabileceğini merak etmektedir. Her günün başlangıcında Çiftçi John seçtiği bir makineyi onarmakta ve bu makinenin sağabileceği süt miktarını değiştirmektedir.

Size önümüzdeki D gün boyunca Çiftçi John'un onaracağı makinelerin listesi verildiğinde D günün sonunda sağabileceği maksimum süt miktarını çıktıya bastırmanızdır (bu değer INT_MAX değerini aşabilir).

Soru adı: optmilk

Girdi Formatı: 

* Satır 1: Sırasıyla N ve D değerleri 

* Satır 2..1+N: Satır i+1 M(i) nin başlangıç değerini içerir. 

* Lines 2+N..1+N+D: Satır 1+N+d i ve m değerlerini içerir. Çiftçi John'un d. gün değiştireceği makinenin indisi i, i makinesinin yeni süt sağma kapasitesi m'dir. Başka bir deyişle M(i)=m olur. 

Örnek Girdi (dosya optmilk.in): 

5 3

1

2 

3 

4 

5 

5 2 

2 7 

1 10 

Girdi Açıklaması: 

Başlangıçtaki süt sağma değerleri sırasıyla 1,2,3,4,5 olan 5 makine vardır. İlk gün makine 5'in süt sağma değeri 2 birime olmuştur vs.


Çıktı Formatı: 

* Tek bir satırda Çiftçi John'un D günde sağabileceği maksimum süt miktarı 

Örnek Çıktı (dosya optmilk.out): 

32 

Çıktı Açıklaması: 

Birinci gün en iyi yol 2. ve 3. makieneleri kullanmaktır 2+4=6 (1. 3. ve 5. makineler de kullanılabilir 1+3+2=6).

İkinci gün 2. ve 4. makineler kullanılır 7+4 = 11.

Üçüncü gün, 1. 3. ve 5. makineler kullanılır 10+3+2=15.

----------------------------------------------------------------------------------------

Soru linki: http://www.usaco.org/index.php?page=viewproblem2&cpid=365&lang=en

Girdi - Çıktı: http://www.usaco.org/current/data/optmilk.zip

----------------------------------------------------------------------------------


Çözüm

Eğer problemimizde update kısmı olmasaydı Dp[i] = max(Dp[i-1],M[i]+Dp[i-2]) şeklinde basit bir dinamik programlama sorusu olacaktı. Fakat her adımda bu dinamiği tekrar hesaplarsak çözüm O(N^2) ye gideceğinden bu dinamiği çözümde kullanmak mantıklı değil.

Problemimizin updatesiz çözmenin bir diğer yolu ise şudur: Elimizde bir Segment Tree olduğunu ve her elemanın 4 değer tuttuğunu düşünelim ; Segment Tree nin a....b node'u için bu değerler
[a,b] aralığında a. ve b. indisteki sayıyı çözümümde kullanıp kullanmama durumuma göre belirlenecek (ikisini de kullandığım durum, sadece ilkini kullandığım durum vs.). Bu değerlerden herhangi birini altımdaki 2 çocuğa bakarak karar verebilirim. Sonuç olarak her node için 4 değeri de altımdaki çocuklardan belirlediğimde 1.....N node'u için bu 4 değerin maksimumu benim çözümüm olur.


Yukarıdaki Segment Tree çözümünü anladıktan sonra problemin update'li hali görüldüğü üzere çok kolay oluyor. Eğer D gün boyunca değeri değişen makineyi ve Segment Tree'de bu makineyi kapsayan nodeları update edersek soruyu DlogN de çözmüş oluruz.


----------------------------------------------------------------------------------

Çözüm Kodu

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n, d, a, b;
int bb[1<<17], bp[1<<17], pb[1<<17], pp[1<<17], SIZE=(1<<16);

void update(int node) {
    int l=node*2, r=node*2+1;
    pp[node] = max(pb[l]+pp[r], pp[l]+bp[r]);
    pb[node] = max(pb[l]+pb[r], pp[l]+bb[r]);
    bp[node] = max(bb[l]+pp[r], bp[l]+bp[r]);
    bb[node] = max(bb[l]+pb[r], bp[l]+bb[r]);
}

main() {
    freopen("optmilk.in", "r", stdin);
    freopen("optmilk.out", "w", stdout);
    scanf("%d %d", &n, &d);
    for(int i=0;i<n;i++) scanf("%d\n", &bb[SIZE+i]);
    for(int i=SIZE-1;i>0;i--) update(i);
    long long ans=0;
    for(int i=0;i<d;i++) {
 scanf("%d %d", &a, &b); a--;
 bb[SIZE+a] = b;
 for(int j=(SIZE+a)/2;j>0;j/=2) update(j);
 ans += bb[1];
   }
   printf("%lld\n", ans);
}