RMQ 2 [ACPC2017 Day2 L]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=L

前提知識

• 平方分割

解法

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2538481&cid=ACPC2017Day2

平方分割で解く。
バケット毎にAorB配列（Aの状態かBの状態か）を設定しておき、それを遅延評価しながら平方分割していく。

int N, A[201010], B[201010], Q;
//--------------------------------------------------------------------------------------------------
#define INF INT_MAX/2
int S, Ami[1010], Bmi[1010];
int AorB[1010]; // -1:none 0:A 1:B
void update(int s) {
    int L = s * S, R = (s + 1) * S;
 
    Ami[s] = Bmi[s] = INF;
    rep(i, L, R) if (i < N) {
        Ami[s] = min(Ami[s], A[i]);
        Bmi[s] = min(Bmi[s], B[i]);
    }
}
void lazy(int s) {
    int L = s * S, R = (s + 1) * S;
 
    if (AorB[s] == 0) {
        rep(i, L, R) if (i < N) B[i] = A[i];
        AorB[s] = -1;
    }
    if(AorB[s] == 1) {
        rep(i, L, R) if (i < N) A[i] = B[i];
        AorB[s] = -1;
    }
}
void init() {
    S = sqrt(N);
    rep(i, 0, N / S + 1) update(i);
    rep(i, 0, N / S + 1) AorB[i] = -1;
}
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
 
    init();
 
    cin >> Q;
    rep(i, 0, Q) {
        int x, y, z; cin >> x >> y >> z;
 
        if (x == 1) {
            y--;
            int s = y / S;
            lazy(s);
            A[y] = z;
            update(s);
        }
 
        if (x == 2) {
            y--;
            int s = y / S;
            lazy(s);
            B[y] = z;
            update(s);
        }
 
        if (x == 3) {
            y--;
 
            int ans = INF;
            rep(i, 0, N / S + 1) {
                int a = i * S, b = (i + 1) * S;
                if (y <= a && b <= z) {
                    if (AorB[i] == 1) ans = min(ans, Bmi[i]);
                    else ans = min(ans, Ami[i]);
                }
                else {
                    if (max(a, y) < min(b, z)) {
                        lazy(i);
                        update(i);
                        rep(j, max(a, y), min(b, z)) ans = min(ans, A[j]);
                    }
                }
            }
 
            printf("%d\n", ans);
        }
 
        if (x == 4) {
            y--;
 
            int ans = INF;
            rep(i, 0, N / S + 1) {
                int a = i * S, b = (i + 1) * S;
                if (y <= a && b <= z) {
                    if (AorB[i] == 0) ans = min(ans, Ami[i]);
                    else ans = min(ans, Bmi[i]);
                }
                else {
                    if (max(a, y) < min(b, z)) {
                        lazy(i);
                        update(i);
                        rep(j, max(a, y), min(b, z)) ans = min(ans, B[j]);
                    }
                }
            }
 
            printf("%d\n", ans);
        }
 
        if (x == 5) {
            rep(i, 0, N / S + 1) if (AorB[i] != 0) AorB[i] = 1;
        }
 
        if (x == 6) {
            rep(i, 0, N / S + 1) if (AorB[i] != 1) AorB[i] = 0;
        }
    }
}