IOI 15 Horses ( Segment Tree )

終於做出來了。。
首先要直覺地想到，如果有一個日期是值得賣的，那麼一定會將所有都在這一天賣出去，因為如果留到後面的價值更高，這一天就根本不會是值得賣的。
如果要比較兩個不同日期賣出的錢，舉例來說比較 day i 和 day j，且不失一般性 i < j ，那麼若且唯若
x[ 1 ] * x[ 2 ] * x[ 3 ] * .. x[ i ] * y[ i ] > x[ 1 ] * x[ 2 ] * .. * x[ i ] * x[ i + 1 ] * .. * x[ j ] * y[ j ]
會有 day i 賣得比較好的情形，簡化一下不等式得
y[ i ] > x[ i + 1 ] * x[ i + 2 ] * .. * x[ j ] * y[ j ]
所以我們只要能快速求得累乘便能解決。很顯然線段樹會是很好的做法，不過要注意到數據範圍可能會過大，因此不能直接計算。
一種解決方法是用 long double 和 log，便能輕易地用前綴和解決比較的部分。
但這裡我是用線段樹，分別紀錄兩個值，cmpv 和 modv，cmpv 只需紀錄負責的區間是否超過 y的值域( 觀察一下不等式便可得知 )，然後因為輸出最後要求的是取模後的總價值，會需要另外存它來應付。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXA = 1e9 + 9;
const int MOD = 1e9 + 7;
typedef long long ll;

int n, m;
int x[ MAXN ], y[ MAXN ];

struct itvt{
    int cmpv, modv;
    int bst_idx;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = -1, int _r = -1): lb(_l), rb(_r), lc(NULL), rc(NULL){}
    int qryp(int ql, int qr, bool cmp){
        if( qr < lb || rb < ql ) return 1;
        if( ql <= lb && rb <= qr ) return cmp ? cmpv : modv;
        if( cmp )
            return min( (ll)MAXA, 1LL * lc->qryp( ql, qr, cmp ) * rc->qryp( ql, qr, cmp ) );
        else
            return ( 1LL * lc->qryp( ql, qr, cmp ) * rc->qryp( ql, qr, cmp ) ) % MOD;
    }
    void pull(){
        cmpv = min( (ll)MAXA, 1LL * lc->cmpv * rc->cmpv );
        modv = ( 1LL * lc->modv * rc->modv ) % MOD;
        if( y[ lc->bst_idx ] > 1LL * qryp( lc->bst_idx + 1, rc->bst_idx, true ) * y[ rc->bst_idx ] )
            bst_idx = lc->bst_idx;
        else
            bst_idx = rc->bst_idx;
    }
    void update(int k){
        if( lb == rb ){
            cmpv = modv = x[ k ];
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ) lc->update( k );
        else rc->update( k );
        pull();
    }
} *root;

itvt* buildItvt(int lb, int rb){
    itvt *t = new itvt( lb, rb );
    if( lb == rb ){
        t->cmpv = t->modv = x[ lb ];
        t->bst_idx = lb;
        return t;
    }
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    t->pull();
    return t;
}

void solve(){
    int idx = root->bst_idx;
    printf("%lld\n", ( 1LL * root->qryp( 0, idx, false ) * y[ idx ] ) % MOD);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", x + i);
    for(int i = 0; i < n; ++i)
        scanf("%d", y + i);
    root = buildItvt( 0, n - 1 );
    solve();
    scanf("%d", &m);
    while( m-- ){
        int t, pos, val; scanf("%d%d%d", &t, &pos, &val);
        if( t == 1 ) x[ pos ] = val;
        else y[ pos ] = val;
        root->update( pos );
        solve();
    }
    return 0;
}