Code 備忘錄►Data Structure

TIOJ::IOI::1887 . 【IOI2015】Horses 一堆猴兒斯

這題是IOI 2015 Day2的題目，簡單的線段樹題。

題目給你一推X還有Y，Xi代表今天的倍率，Yi代表今天的價錢，你一開始只有一個東西，每過完一天就會變成Xi倍，然後在那天結束時你可以用Yi的價錢賣出，你可賣任意數量的東西。求最好的策略下，你最多能賺多少錢。
除了一開始給定的X跟Y，題目還會有一些X和Y的更新，每次更新都要輸出現在的最佳解。

觀察一下就會發現，把所有東西在最好的那天賣出一定是一種最好的解。因為要是留到之後再賣會更好，那乾脆全部留下來賣。

於是我們得到一個DP式子，就是如果DP[i]是 0 到 i 中，最適合把東西全部賣掉的時間，那對於DP[i+1]，如果 $ Y[DP[i]] > X[DP[i]+1] \times X[DP[i]+2] \times … \times X[i+1] \times Y[i+1] $，那DP[i+1] = DP[i] ，不然 DP[i+1] = i+1。
上面的意思是說，現在有兩個可能的最佳適合時間可以賣東西，選左邊的條件是，左邊的價錢會比放到右邊那天時，東西變多的被率和那天的價錢的乘積還要大，不然我就放到那天然後賣掉一定比現在好。

有了上述性質，可以得到一個O（n）的解法，可是題目要更新，所以我們再看一下，發現這個DP可以用分治去做，也就是可以從中間對切，所以我們可以建一棵線段樹去維護答案，每次更新只要更新有改變的節點就好了，更新複雜度O（logn）。

實際上的作法就是，紀錄現在這格的最佳座標，還有這個座標左邊的X的乘積還有右邊X的乘積，從下面合併答案時，就是看左邊小孩的右邊X乘積和右邊小孩的左邊X乘積（也就是兩個最佳座標的中間那塊乘積），然後用上面的DP式去決定留哪個，然後把這塊的左邊X乘積和右邊X乘積也維護好。

這裡會遇到一個問題，就是你不知道那個數字爆掉了沒，如果爆了你就要取mod，然後就無法比大小了。
這裡有兩種作法，第1種是，每次mod一個數字前，先檢查他是不是大於1e9+7，如果是就紀錄一個tag（每個數字都要一個），如果tag是true，就當這個數字是無限大，而無限大乘以任何數都還是無限大，這樣上面的DP式，會有一邊一定是普通數字（Y），一邊是普通數字（Y）乘以一個可能是無限大的數字，這樣就可以比大小了。這個作法比較難是難在要維護每個數字的tag會有一些細節要注意。
第2種是，直接對數字取log，這樣乘法就會變成加法了，然後比大小也就沒問題了。這個作法的問題是可能有誤差，不過官方測資是可以輕鬆通過的。

我是用第1種。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 500001, MN = 4*N;
const long long Q = 1e9 + 7;
long long X[N],Y[N];
long long do_mod(long long a, bool &tag){
    if(a>=Q)tag = true;
    return a % Q;
}
struct Seg{
    static Seg ST[MN], *p;
    long long lsz,rsz;
    int mxi;
    bool lmod,rmod;
    Seg *lc,*rc;
    Seg(){ }
    Seg(int l,int r):lmod(false),rmod(false){
        if(l==r){
            lsz = X[l];
            rsz = 1;
            lmod = rmod = false;
            mxi = l;
            return;
        }
        int mid = (l+r)/2;
        lc = new(p++) Seg(l, mid);
        rc = new(p++) Seg(mid+1, r);
        pull();
    }
    void pull(){
        lmod = rmod = false;
        long long msz;
        bool mmod = lc->rmod || rc->lmod;
        msz = do_mod(lc->rsz * rc->lsz, mmod);
        if(lc->rmod || rc->lmod || mmod || Y[lc->mxi] < msz * Y[rc->mxi]){
            mxi = rc->mxi;
            lsz = do_mod(lc->lsz * msz, lmod);
            lmod |= lc->lmod || mmod;
            rsz = rc->rsz;
            rmod = rc->rmod;
        }else{
            mxi = lc->mxi;
            lsz = lc->lsz;
            lmod = lc->lmod;
            rsz = do_mod(msz * rc->rsz, rmod);
            rmod |= rc->rmod || mmod;
        }
    }
    void update(int l, int r, int x){
        if(x<l||x>r)return;
        if(l==r){
            lsz = X[l];
            return;
        }
        int mid = (l+r)/2;
        lc->update(l, mid, x);
        rc->update(mid+1,r,x);
        pull();
    }
    long long getAns(){
        return lsz * Y[mxi] % Q;
    }
}Seg::ST[MN], *Seg::p = Seg::ST;
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t,n,q,a,b,c;
    cin>>t;
    while(t--){
        cin>>n;
        F(n)cin>>X[i];
        F(n)cin>>Y[i];
        Seg::p = Seg::ST;
        Seg *RT = new(Seg::p++) Seg(0,n-1);
        cout<<RT->getAns()<<'\n';
        cin>>q;
        while(q--){
            cin>>a>>b>>c;
            if(a==1)X[b] = c;
            else Y[b] = c;
            RT->update(0,n-1,b);
            cout<<RT->getAns()<<'\n';
        }
    }
}