Range Update Query 時間超過を解決したい

Question

AOJのRUQのジャッジで時間超過しました。
この問題を解決したいです。

該当のソースコード

#include <iostream>
#include <vector>
using namespace std;

#define INF 2147483647

vector<int> node;
int N;

void update(int s, int t, int x) {
    s += N - 1;
    t += N - 1;

    //cout << "update s = " << s << " t = " << t << endl;

    while(s <= t){
        //cout << s << endl;
        node[s] = x;
        s++;
    }

}


int find(int i) {
    //cout << "find " << i + N - 1 << endl;
    return node[i + N - 1];
}



int main() {

    int n, q;
    cin >> n >> q;
    N = 1;

    while (N < n) N *= 2;

    node = vector<int>(2 * N - 1, INF);

    for (int j = 0; j < q; j++) {

        int com;
        cin >> com;

        if (com == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            update(s, t, x);
        }

        else {
            int i;
            cin >> i;
            cout << find(i) << endl;
        }
    }
    return 0;
}

Answer 1

単なる配列では無理なので、何らかのデータ構造を駆使する必要があります。

vectorのサイズの計算からして、セグメント木を使おうとしていたと思われるので、
セグメント木の応用による解法を示します。
(AOJには登録していないのでTLEが解消できるかまでは確認できていません)

更新時に範囲内の個々の数値を全て書き換えるのは大変なので、
範囲を代表する値(セグメント木のノード)を1つ書き換えるだけですまそうというアイデアです。

当然範囲内の値がばらばらの場合もあるので、そのような場合は-1を保存するというルールとします。

このようなルールにしておけば、findについては、
根から葉までたどって、-1以外が出てきたらその値を返すだけで実装できます。

updateは、根から葉までたどって、自ノードの範囲が更新範囲外なら何もしない、
自ノードの範囲が更新範囲に完全に含まれるなら自ノードの値を更新、
そうでなければ子ノードをupdateする感じです。

子ノードをupdateする際に、自ノードに-1以外の値が設定されていたら、
範囲内の値がすべて同じという前提が崩れるので、
子ノードに自ノードの値をコピーしたうえで自ノードを-1に更新します。

void update(int s, int t, int x, int k = 0, int l = 0, int r = N - 1) {
    if (t < l || r < s)
        return;
    if (s <= l && r <= t) {
        node[k] = x;
        return;
    }
    if (node[k] >= 0) {
        node[k * 2 + 1] = node[k];
        node[k * 2 + 2] = node[k];
        node[k] = -1;
    }
    int m = (l + r + 1) / 2;
    update(s, t, x, k * 2 + 1, l, m - 1);
    update(s, t, x, k * 2 + 2, m, r);
}


int find(int i) {
    int k = 0, l = 0, r = N - 1;
    while (node[k] < 0) {
        int m = (l + r + 1) / 2;
        if (i < m) {
            r = m - 1;
            k = k * 2 + 1;
        }
        else {
            l = m;
            k = k * 2 + 2;
        }
    }
    return node[k];
}