AOJの RMQ and RUQ の問題でTLEが出てしまう(競プロ)

発生している問題

AOJの、データの集合とクエリ処理 - 2_F: RMQ and RUQ (https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_F) を自作した遅延セグ木で解こうとしたのですが、途中でTLEが出てしまいどうしてもAC出来ません。どなたか原因を教えていただけますでしょうか。

ソースコード

https://onlinejudge.u-aizu.ac.jp/recent_judges/DSL_2_F/judge/5704837/okamens/C++17

C++
1#include <bits/stdc++.h>
2using namespace std;
3
4#define stp(var, init, end) for (auto var = init; var < end; ++var)
5#define stpe(var, init, end) for (auto var = init; var <= end; ++var)
6#define stpi(iter, array) for (auto iter = array.begin(); iter != array.end(); ++iter)
7#define ll long long
8
9template <typename T>
10class lazy_rmq
11{
12private:
13    vector<T> _tree, _lazy_tree;
14    int _size, _t_size, _INF;
15    T _func(T l, T r) { return min(l, r); }
16
17    void init(void)
18    {
19        _t_size = 1;
20        while (_t_size < _size)
21        {
22            _t_size *= 2;
23        }
24        _t_size *= 2, --_t_size;
25        _tree.assign(_t_size, _INF);
26        _lazy_tree.assign(_t_size, _INF);
27    }
28    void init(vector<T> &array)
29    {
30        this->init();
31        for (int i = 0; i < _size; ++i)
32        {
33            _tree[_t_size / 2 + i] = array[i];
34        }
35        build();
36    }
37    void build(void)
38    {
39        for (int i = _t_size / 2 - 1; i >= 0; --i)
40        {
41            _tree[i] = _func(_tree[2 * i + 1], _tree[2 * i + 2]);
42        }
43    }
44    void propagate(int now)
45    {
46        if (_lazy_tree[now] != _INF)
47        {
48            _tree[now] = _lazy_tree[now];
49            if (now < _t_size / 2)
50            {
51                _lazy_tree[2 * now + 1] = _lazy_tree[now];
52                _lazy_tree[2 * now + 2] = _lazy_tree[now];
53            }
54            _lazy_tree[now] = _INF;
55        }
56    }
57    void range_update_inside(int l, int r, int L, int R, int now, T value)
58    {
59        propagate(now);
60        if (R <= l || r <= L)
61            return;
62        else if (l <= L && R <= r)
63            _lazy_tree[now] = value;
64        else
65        {
66            range_update_inside(l, r, L, (L + R) / 2, 2 * now + 1, value);
67            range_update_inside(l, r, (L + R) / 2, R, 2 * now + 2, value);
68        }
69    }
70    T query_inside(int l, int r, int L, int R, int now)
71    {
72        T ret;
73        propagate(now);
74        if (R <= l || r <= L)
75            ret = _INF;
76        else if (l <= L && R <= r && _t_size / 2 <= now)
77            ret = _tree[now];
78        else
79            ret = _func(query_inside(l, r, L, (L + R) / 2, 2 * now + 1), query_inside(l, r, (L + R) / 2, R, 2 * now + 2));
80        if (now < _t_size / 2)
81            _tree[now] = _func(_tree[2 * now + 1], _tree[2 * now + 2]);
82        return ret;
83    }
84
85public:
86    explicit lazy_rmq(int size, T INF) : _size(size), _INF(INF) { this->init(); }
87    explicit lazy_rmq(vector<T> &array, T INF) : _size((int)array.size()), _INF(INF) { this->init(array); }
88    void assign(int size, T INF)
89    {
90        _size = size, _INF = INF;
91        this->init();
92    }
93    void assign(vector<T> &array, T INF)
94    {
95        _size = (int)array.size(), _INF = INF;
96        this->init(array);
97    }
98    const T &operator[](int i) { return _tree[_t_size / 2 + i]; }
99    void range_update(int l, int r, T value) { range_update_inside(l, r, 0, _t_size / 2 + 1, 0, value); }
100    T query(int l, int r) { return this->query_inside(l, r, 0, _t_size / 2 + 1, 0); }
101    //void debug(void){int width=3,size=_t_size,t=log2(size);int n,index;for(int i=(1<<t+1)-2;i>=0;--i){for(int j=0;j<t+1;++j){if((i-(1<<t-j)+1)%(1<<t+1-j)==0){n=(i-(1<<t-j)+1)/(1<<t+1-j);index=(1<<j)+n-1;if(index<size){cout<<"[";if(_tree[index]==_INF)cout<<"INF";else cout<<_tree[index];cout<<"/";if(_lazy_tree[index]==_INF)cout<<"INF";else cout<<_lazy_tree[index];cout<<"]";}}else cout<<string(width+2,' ');}cout<<"\n";}}
102};
103
104int main(void)
105{
106    int n, q;
107    cin >> n >> q;
108    lazy_rmq<ll> seg(n, (1ll << 31) - 1ll);
109    int a, s, t;
110    ll x;
111    stp(i, 0, q)
112    {
113        cin >> a >> s >> t;
114        switch (a)
115        {
116        case 0:
117            cin >> x;
118            seg.range_update(s, t + 1, x);
119            break;
120        case 1:
121            cout << seg.query(s, t + 1) << "\n";
122            break;
123        }
124    }
125    return 0;
126}

追記

query_inside()内の

C++
1else if (l <= L && R <= r && _t_size / 2 <= now)

の条件_t_size / 2 <= nowがTLEの要因になっているということですが、
この条件を削除すると、下記の例のように更新が上手く反映されない場合があると思うのですが、この場合どうすればよいのでしょうか。

[ 配列(_tree)/遅延評価用配列(_lazy_tree) ]
/*--------------------------------------------*/
例:
[                     2/-                     ]
[         3/-         ] [         2/-         ]
[   4/-   ] [   3/-   ] [   2/-   ] [   5/-   ]
[4/-] [5/-] [3/-] [6/-] [2/-] [3/-] [8/-] [5/-]
↓
区間[4,5)を1に更新
[                     2/-                     ]
[         3/-         ] [         2/-         ]
[   4/-   ] [   3/-   ] [   2/-   ] [   5/-   ]
[4/-] [5/-] [3/-] [6/-] <2/1> [3/-] [8/-] [5/-]
↓
区間[4,8)の最小値を求める
<                     2/-                     >
<         3/-         > <         2/-         >←これ以上query関数は下に進まない
[   4/-   ] [   3/-   ] [   2/-   ] [   5/-   ]
[4/-] [5/-] [3/-] [6/-] [2/1] [3/-] [8/-] [5/-]
↓
(正しい結果は1だが)2が返される

行動規範の内容に同意します

回答1件

ベストアンサー

遅い原因は、query_inside内の以下の条件文でしょう。
最後の条件のせいで、query_insideが必ず葉まで参照しに行ってしまっています。

c++
1        else if (l <= L && R <= r && _t_size / 2 <= now)

とりあえず、最後の条件を削除したうえで、正常動作するように調整すべきだと思われます。

#追記
遅延セグメント木の更新処理を勘違いしています。
(検索して見つかる図が処理途中段階のものが多いで仕方ないかもしれませんが)
更新範囲内で最も葉に近いノードのみ更新するわけではなく、その親も一通り更新します。

追記の例だと、更新結果は通常のセグメント木と結果は変わりません。(<>が参照・更新されたノード)

text
1[ 配列(_tree)/遅延評価用配列(_lazy_tree) ]
2/*--------------------------------------------*/
3例:
4[                     2/-                     ]
5[         3/-         ] [         2/-         ]
6[   4/-   ] [   3/-   ] [   2/-   ] [   5/-   ]
7[4/-] [5/-] [3/-] [6/-] [2/-] [3/-] [8/-] [5/-]
8↓
9区間[4,5)を1に更新
10<                     1/-                     >
11[         3/-         ] <         1/-         >
12[   4/-   ] [   3/-   ] <   1/-   > [   5/-   ]
13[4/-] [5/-] [3/-] [6/-] <1/-> [3/-] [8/-] [5/-]
14↓
15区間[4,8)の最小値を求める
16<                     1/-                     >
17[         3/-         ] <         1/-         >
18[   4/-   ] [   3/-   ] [   1/-   ] [   5/-   ]
19[4/-] [5/-] [3/-] [6/-] [1/-] [3/-] [8/-] [5/-]

更新も範囲でないと遅延木の効果は見えません。

text
1[ 配列(_tree)/遅延評価用配列(_lazy_tree) ]
2/*--------------------------------------------*/
3例:
4[                     2/-                     ]
5[         3/-         ] [         2/-         ]
6[   4/-   ] [   3/-   ] [   2/-   ] [   5/-   ]
7[4/-] [5/-] [3/-] [6/-] [2/-] [3/-] [8/-] [5/-]
8↓
9区間[3,8)を1に更新
10<                     1/-                     >
11<         1/-         > <         1/-         >
12[   4/-   ] <   1/-   > <   2/1   > <   5/1   >
13[4/-] [5/-] [3/-] <1/-> [2/-] [3/-] [8/-] [5/-]
14↓
15区間[4,6)の最小値を求める
16<                     1/-                     >
17[         1/-         ] <         1/-         >
18[   4/-   ] [   1/-   ] <   1/-   > [   5/1   ]
19[4/-] [5/-] [3/-] [1/-] <2/1> <3/1> [8/-] [5/-]

[4,8)のノードではなく、その子のノードが遅延されるのは、
[4,8)のノードの値が[0,8)のノードの値の計算に必要だからです。

投稿2021/07/18 10:19

編集2021/07/18 21:05

actorbug

総合スコア2431

luuguas

2021/07/18 14:52

_t_size / 2 <= now の条件を削除したとして、そこからどうすればよいか悩んでいます。例えば、長さ8の数列を表すセグ木があり、区間[4,5)を更新します。すると、遅延評価用配列の、区間[4,5)を示す要素の値が書き換えられます。その直後に区間[4,8)における最小値をquery関数で求めるとき、関数は区間[4,8)を示すセグ木の頂点まで進み、それ以上葉の方向には進まないため、区間[4,5)が更新されているという情報が関数に伝わらないと思うのですが、その場合はどうすればよいのでしょうか。 (質問本文にも例を書きました)

luuguas

2021/07/19 11:57

なるほど、ノードの遅延だけでなく、その祖先ノードの更新も必要だったのですね。ようやく疑問が解決しました。丁寧な解説本当にありがとうございます！

行動規範の内容に同意します