JavaScriptを有効にしてください

【ABC217 E問題】セグ木にindexを保持させるテク

 ·  ☕ 5 min read

はじめに

競プロを1年以上サボっているYuWdです.

長らく競プロから遠ざかっていたのですが, 今日から気楽に競プロを再開しようと思います. 手始めに今日は, サボり期間で受けていなかったコンテストを解いてみました. (ABC217)
しかし, 解いてみた所感として, 思考力とやらはそこまで廃れきってはいないようなのですが, どうやら競プロの"勘"のようなものがゴッソリと抜け落ちているようです. というのも, E問題で「セグ木にindex持たせるのってどうやってやるんだっけ？」となってしまったのでした.

ということで, 備忘録程度に「セグ木にインデックスを保持させる方法」を記しておこうと思います.

問題文

解法

まさか毎回ソートするわけにも行かないので, なんらかの形で配列はそのまま管理しつつ先頭の値を取り出すデータ構造があれば嬉しいということになります.

どういうのが嬉しいかと考えていくと, “3"が呼ばれるごとに仕切りを右側に動かしていき, 仕切りから左側から最小値が取れれば良いことがわかります. また, 一度取り出した最小値はINFなどで潰してあげれば良いです(ここでセグ木ならindexが必要). priority queueでも良かったのですが, 今回はセグ木を使ってみます.

インデックスを保持させるRMQ (Segment-Tree)

結論から言うと, long longでクソデカ数字$B$をindexに掛け合わせたもの $x \leftarrow x + B \times \text{index}$ を用意し,
モノイド同士の作用処理のときだけ $x \bmod B$ を本来の値かのように振る舞わせるだけで良いです.

クソデカ数字$B$をどう設定するかということなのですが, $x$ の範囲が $ 0 \le x \le 10^9$ なので, $B := 10^9 + 10$ をクソデカ数字$B$として, $x \leftarrow x + B \times \text{index}$とすれば良いです.

また, モノイドの単位元はINF-INF%B + B-1 等, $x \bmod B$で評価してもmaxであるように設定すべき点に留意してください.

このようなモノイドに設定すれば, $x \bmod B$ から本来の値が, $\frac{x}{B}$ からindexを取り出すことができます. 実装もただただ大きい値を掛けるだけなのでとてもコスパが良いです.

ということで解法です.

 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

struct S {
    ll a;
    ll size;
};

ll B = 1e9+10;
#define val(x) (x%B)
#define idx(x) (ll(x/B))

S op(S l, S r) { return S{(val(l.a) < val(r.a)) ? l.a : r.a ,l.size+r.size}; } // S * S

S e() { return {INF-INF%B + B-1,0}; } // モノイドの単位元


int solve(ostringstream &cout) {
    #ifdef LOCAL
    ifstream in("../../input.txt");
    cin.rdbuf(in.rdbuf());
    #endif

    ll l,q;
    cin>>q;

    segtree<S,op,e> seg(1e6);
    ll p = 0,thr = 1;
    rep(_,q) {
        ll c;
        cin >>c;
        if (c == 1) {
            ll x;
            cin >>x;
            x += B * p;
            seg.set(p++,S{x,0});
        }
        else {
            if (c==2) {
                ll ans = e().a;
                while (ans == e().a) {
                    ans = seg.prod(0,thr).a; // [0,p)
                    if (ans == e().a) thr++;
                }
                cout << val(ans) << endl;
                seg.set(idx(ans),e());
            }
            else {
                if (p > 0) thr = p;
            }
        }
    }

    return 0;
}
  • 全文
  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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258

#include <bits/stdc++.h>
using namespace std;
// #define LOCAL // 提出時はコメントアウト
#define DEBUG_

typedef long long ll;
const double EPS = 1e-9;
const ll INF = ((1LL<<62)-(1LL<<31));
typedef vector<ll> vecl;
typedef pair<ll, ll> pairl;
template<typename T> using uset = unordered_set<T>;
template<typename T, typename U> using mapv = map<T,vector<U>>;
template<typename T, typename U> using umap = unordered_map<T,U>;

#define ALL(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define sz(x) (ll)x.size()
#define pb(x) push_back(x)
ll llceil(ll a,ll b) { return (a+b-1)/b; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> vector<vector<T>> genarr(ll n, ll m, T init) { return vector<vector<T>>(n,vector<T>(m,init)); }

///// DEBUG
#define DUMPOUT cerr
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
template<typename T>istream&operator>>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<typename T,typename U>ostream&operator<<(ostream&os,pair<T,U>&pair_var){os<<"("<<pair_var.first<<", "<<pair_var.second<<")";return os;}
template<typename T>ostream&operator<<(ostream&os,vector<T>&vec){os<<"{";for(int i=0;i<vec.size();i++){os<<vec[i]<<(i+1==vec.size()?"":", ");}
os<<"}";return os;}
template<typename T,typename U>ostream&operator<<(ostream&os,map<T,U>&map_var){os<<"{";repi(itr,map_var){os<<*itr;itr++;if(itr!=map_var.end())os<<", ";itr--;}
os<<"}";return os;}
template<typename T>ostream&operator<<(ostream&os,set<T>&set_var){os<<"{";repi(itr,set_var){os<<*itr;itr++;if(itr!=set_var.end())os<<", ";itr--;}
os<<"}";return os;}
template<typename T>ostream&operator<<(ostream&os,uset<T>&set_var){os<<"{";repi(itr,set_var){if(itr!=set_var.begin())os<<", "; os<<*itr;}
os<<"}";return os;}
template<typename T,typename U>ostream&operator<<(ostream&os,umap<T,U>&map_var){os<<"{";repi(itr,map_var){if(itr!=map_var.begin())os<<", "; os<<*itr;}
os<<"}";return os;}
void dump_func(){DUMPOUT<<endl;}
template<class Head,class...Tail>void dump_func(Head&&head,Tail&&...tail){DUMPOUT<<head;if(sizeof...(Tail)>0){DUMPOUT<<", ";}
dump_func(std::move(tail)...);}
#ifndef LOCAL
#undef DEBUG_
#endif
#ifdef DEBUG_
#define DEB
#define dump(...)                                                          \
DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
        << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
        << endl                                                            \
        << "    ",                                                         \
    dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

//////////

#ifndef DEBUG_
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif


// SegTree: https://atcoder.github.io/ac-library/document_ja/segtree.html

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}


template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) { // O(logn)
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) { // O(1)
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) { // [l,r): O(logn)
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; } // [0,n)

    template <bool (*f)(S)> int max_right(int l) { // segtree上で二分探索 O(logn)
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) { // segtree上で二分探索 O(logn)
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) { // segtree上で二分探索 O(logn)
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) { // segtree上で二分探索 O(logn)
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

// (S,*): 結合律の成立と単位元の存在を満たせばOK
// 交換律は必要ないので演算の向きを恣意的に決めてOK

struct S {
    ll a;
    ll size;
};

ll B = 1e9+10;
#define val(x) (x%B)
#define idx(x) (ll(x/B))

S op(S l, S r) { return S{(val(l.a) < val(r.a)) ? l.a : r.a ,l.size+r.size}; } // S * S

S e() { return {INF-INF%B + B-1,0}; } // モノイドの単位元


int solve(ostringstream &cout) {
    #ifdef LOCAL
    ifstream in("../../input.txt");
    cin.rdbuf(in.rdbuf());
    #endif

    ll l,q;
    cin>>q;

    segtree<S,op,e> seg(1e6);
    ll p = 0,thr = 1;
    rep(_,q) {
        ll c;
        cin >>c;
        if (c == 1) {
            ll x;
            cin >>x;
            x += B * p;
            seg.set(p++,S{x,0});
        }
        else {
            if (c==2) {
                ll ans = e().a;
                while (ans == e().a) {
                    ans = seg.prod(0,thr).a; // [0,p)
                    if (ans == e().a) thr++;
                }
                cout << val(ans) << endl;
                seg.set(idx(ans),e());
            }
            else {
                if (p > 0) thr = p;
            }
        }
    }

    return 0;
}


int main() {
    ostringstream oss;
    int res = solve(oss);

    cout << oss.str();
    return res;
}
共有
YuWd (Yuiga Wada)
著者
YuWd (Yuiga Wada)
機械学習・競プロ・iOS・Web

関連記事

©2023, All Rights Reserved