WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #174 Div2 C "Cows and Sequence"

問題

http://codeforces.com/contest/284/problem/C

シーケンス(配列)を使った遊びがある。
シーケンスは最初、0が1つだけ入った状態(サイズは1)であり、
以下のような3つの操作のいずれかをN回行う。

1. 数値Xを先頭からA個目までの要素全てに足す。
2. シーケンスのおしりに数値Kを追加する。(シーケンスのサイズは1増える)
3. シーケンスのおしりの要素を削除する。(シーケンスのサイズは1減る)
  また、この操作はシーケンスのサイズが2つ以上の時にのみ行う事が出来る。

それぞれの操作の後、シーケンスの平均の値を出力せよ。

制約

1 <= N <= 2 * 10^5
-1000 <= X, K <= 1000
1 <= A

考えた事

素直に実装すると最悪O(N * N)ぐらいかかっちゃうな。
ここは前に蟻本でチラ見したセグメント木を使おう!
どうやって実装すればいいかよく知らないけど、
ま、蟻本見なくても考えれば自分で実装できるっしょ!


2時間後

よし、(蟻本参考にして)セグメント木の実装は把握した。
これができればもう出来たようなもんだな。楽勝w


さらに4時間後

よ、余裕だったし!
f:id:Ekaing:20130320222201j:plain
※原因はオーバーフローとセグメント木の配列サイズが小さすぎた事
※2500ms → 1000msとなっているのは、coutをprintfに変えたため

これでOK・・じゃない!

区間全体に数値を足す操作があるので
セグメント木を使わなきゃいけない・・と思いきや、
区間は先頭からという制約があるし、
要素の追加や削除も末尾のみ、ということで、
セグメント木という大げさなものはいらなかった。

操作1,2はもともと問題ない。
単純に前までの合計値に追加分を足すだけで操作後の合計値はでる。

問題は操作3だが、
a[i] インデックスiに最初に追加した時の値
s[i] 先頭からそのインデックスiまで、まとめて追加した数値の合計
この2つの情報を持っておく。
削除する要素のインデックスをiとすると、
sum - (a[i] + s[i])で操作後の合計値がでる。
しかしこのままだと、
0からiの要素全体にs[i]足したよ!という事実が失われてしまうので、
s[i-1] += s[i]とするとよい。

ソースコード

typedef long long ll;

const int N = 200050;

int a[N]; // インデックスiに最初に追加した時の値
int s[N]; // 先頭からそのインデックスiまで、まとめて追加した数値の合計

int main() {

    fill( a, a + N, 0 );
    fill( s, s + N, 0 );
    int size = 1; // サイズ
    ll sum = 0;   // 合計

    int n, op, x, m;
    cin >> n;
    for( int i = 0; i < n; i++ ){
        cin >> op;
        if( op == 1 ){     // 区間に数値を追加
            cin >> m >> x;
            s[m-1] += x;
            sum += m * x;
        }
        if( op == 2 ){     // 末尾に要素追加 
            cin >> x;
            a[size++] = x;
            sum += x;
        }
        if( op == 3 ){     // 末尾の要素を削除
            size--;
            sum -= a[size] + s[size];
            s[size-1] += s[size];
            s[size] = 0;
        }

        printf( "%.6lf\n", (sum+0.0)/size );
    }
}
セグメント木を使った時のソースコード
typedef long long ll;

// プロトタイプ関数
void add(int, int, int, int, int, int );
ll   sum(int, int, int, int, int );


const int N = 200050; // セグメント木の最大要素数

ll TREE_A[1 << 19]; // 区間に一様に足されなかった数値の合計 
ll TREE_B[1 << 19]; // 区間に一様に足された数値の合計

int main() {
    // セグメント木の初期化
    fill( TREE_A, TREE_A + (1<<19), 0 );
    fill( TREE_B, TREE_B + (1<<19), 0 );
    int size = 1;

    int n;
    in >> n;
    for( int i = 0; i < n; i++ ){
        int op;
        in >> op;
        if( op == 1 ){
            int x, m;
            in >> m >> x;
            // [0,m)にxを追加する
            add(0, m, x, 0, 0, N );
        }
        if( op == 2 ){
            int k;
            in >> k;
            // 追加するインデックスだけに区間を限ってkを追加する
            add(size, size+1, k, 0, 0, N );
            size++;
        }
        if( op == 3 ){
            // 削除するインデックスの値を求める
            int s = static_cast<int>(sum(size-1, size, 0, 0, N ));
            // それをそのインデックスの部分だけから引く
            add(size-1, size, -s, 0, 0, N );
            size--;
        }

        ll s = sum(0, N, 0, 0, N);
        printf( "%.6lf\n", (s+0.0)/size );
    }
}

/*
 * 区間[a,b)に値vを追加する
 *
 * パラメータ
 * a b 追加する区間(ただしbは含まない) 
 * v   追加する値
 * i   現在いる区間に対応するインデックス
 * l r 現在いる区間(ただしrは含まない)
 */
void add( int a, int b, int v, int i, int l, int r ){
    if( a <= l && r <= b ){
        TREE_B[i] += v;
    }else if( a < r && l < b ){
        TREE_A[i] += v * (min(r,b) - max(l,a));
        add( a, b, v, i * 2 + 1, l, (l+r)/2 );
        add( a, b, v, i * 2 + 2, (l+r)/2, r );
    }
}

/*
 * 区間[a,b)の合計値を返す
 *
 * パラメータ
 * a b 目的の区間(ただしbは含まない) 
 * i   現在いる区間に対応するインデックス
 * l r 現在いる区間(ただしrは含まない)
 */
ll sum( int a, int b, int i, int l, int r ){
    if( a <= l && r <= b ){
        return TREE_A[i] + TREE_B[i] * (r - l);
    }else if( r <= a || b <= l ){
        return 0;
    }
    ll res = sum( a, b, i * 2 + 1, l, (l+r)/2 ) + sum( a, b, i * 2 + 2, (l+r)/2, r );
    res += TREE_B[i] * (min(b,r) - max(a,l));
    return res;
}