CF Croc Champ 2013 - Round 1 E. Copying Data

Codeforces Croc Champ 2013 - Round 1 E. Copying Data

Problem - E - Codeforces

数列a[i]とb[i]が与えられる。これらの数列について、以下の２種類のクエリを実行していくという問題。
・aのx番目からk個をbのy番目からk個にコピーする
・b[x]を出力する
以下前者をコピーのクエリと呼ぶ。

まず、b[u]を求めるときに、その位置の数が最後にいつ変更されたか（＝その位置を含む最後のコピーのクエリはどれか）がわかれば、答えがわかりそうである。実際、そのコピーのクエリが何番目だったかがわかれば、そのクエリのx, yより、a[x + (u - y)]がb[u]に等しいことがわかる。なぜならば、そのコピーする部分の先頭がa[x]であり、u - yはその位置が先頭からどれくらい進んでいるかを表すので、a[x + u - y]がその位置にコピーされた数値に等しいのである。したがって、セグメントツリーなどをつくり、コピーのクエリがくるたびに、その区間をそのクエリが何番目であるかを上書きしていけばよい。

以下のサイトを参考にさせていただき、区間をある数で塗りつぶす実装をした。
Lazy Propagation Segment Tree

get関数はなんとなくで書いた。出力のクエリがくるごとに上記サイトのfixに相当するようなことをしている。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb                    push_back
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.141592653589793238462643383279;

#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; scanf("%d", &_x); return _x; }
long long lin() {long long _x; scanf("%lld", &_x); return _x; };

struct SegmentTree {
        vector<int> lazy;
        int n;
        SegmentTree(int x) {
                n = pow(2, ceil(log2(x)));
                lazy.resize(2 * n - 1);
                for (int i = 0; i < 2 * n - 1; i ++) lazy[i] = INF;//初期化
        }
        void push(int k) {
                if (lazy[k] == INF) return;
                lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
                lazy[k] = INF;
        }
        int get(int k) {
                int res = INF;
                k += n - 1;//葉から根までを見ていき、INFじゃないものがあるたびにresを更新している。上にあるもののほうがあとで上書きされた値だからである
                if (lazy[k] != INF) res = lazy[k];
                while (k > 0) {
                        k = (k - 1) / 2;
                        if (lazy[k] != INF) res = lazy[k];
                }
                return res;
        }
        // [l, r))
        void fill(int a, int b, int val) { fill(a, b, val, 0, 0, n); }//区間[a, b)をvalで塗りつぶす
        void fill(int a, int b, int val, int k, int l, int r) {
                if (r <= a || b <= l) return;
                if (a <= l && r <= b) {
                        lazy[k] = val;
                        return;
                }
                push(k);
                int m = (l + r) / 2;
                fill(a, b, val, k * 2 + 1, l, m);
                fill(a, b, val, k * 2 + 2, m, r);
        }
};

struct Q {
        int x, y;
};

signed main() {
        int n, q;
        cin >> n >> q;
        vi a(n), b(n);
        rep(i, n) cin >> a[i];
        rep(i, n) cin >> b[i];
        SegmentTree st(n);
        vector<Q> query;
        rep(i, q) {
                int t;
                cin >> t;
                if (t == 1) {
                        int x, y, k;
                        cin >> x >> y >> k;
                        x --, y --;
                        query.pb({x, y});
                        st.fill(y, y + k, query.size() - 1); //yからk個をquery.size() - 1（＝クエリ番号）で塗りつぶす
                } else {              
                        int u;
                        cin >> u;
                        u --;
                        if (st.get(u) == INF) cout << b[u] << endl; //そのままなら、一回もその位置にはコピーされていない
                        else {
                                int q = st.get(u); //クエリ番号を取り出してクエリを復元
                                int qx = query[q].x;
                                int qy = query[q].y;
                                cout << a[qx + u - qy] << endl;
                        }
                }
        }
        return 0;
}