問題

配列がある。 以下のクエリを順次処理し、結果の配列を出力せよ。

  • 区間$[l, r]$中の$x$番目以外の要素で、まだ代入がなされていない要素に関し、$x$を代入する。

解法

skip量配列を横に持つ。$O(N)$。

連続した区間がまとめて処理されるので、そこを飛ばしたい。 各位置に関して、次の未代入の要素の位置を持って、これを適当に更新しながら処理する。

実装

#include <iostream>
#include <vector>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<int> a(n);
    vector<int> skip(n); repeat (i,n) skip[i] = i+1;
    function<int (int,int,int)> rec = [&](int l, int r, int x) {
        if (r <= l) return r;
        if (not a[l]) a[l] = x;
        return skip[l] = rec(skip[l], r, x);
    };
    repeat (query,m) {
        int l, r, x; cin >> l >> r >> x; -- l; -- x;
        rec(l,   x, x+1);
        rec(x+1, r, x+1);
    }
    repeat (i,n) { if (i) cout << ' '; cout << a[i]; } cout << endl;
    return 0;
}