10922번: 말

https://www.acmicpc.net/problem/10922

대회 당시 인터렉티브 문제로 출제되었으므로 입력을 미리 받아야 쓸 수 있는 풀이는 자제하자.


$O(n\lg n+m\lg (n+m)\lg X)$ // X는 X[i],Y[i]의 최댓값

X[i], Y[i]가 수정될 수 있을 때, f(x)=X[0]*X[1]*...*X[x]*Y[x]의 최댓값을 구하는 문제이다.
단순히 구간 갱신 쿼리를 관리하는 문제로 바꿔 풀면 누적되는 수가 너무 커질 수 있다.
X[i], Y[i]가 자연수이며 10억 이하인 점을 주목하자.
f(x)가 x=i일 때 최댓값을 가진다고 해보자.
그렇다면 X[j]>1 (j>i)를 만족하는 j는 30개 보다 작아야 한다.
그렇지 않으면,
f(n)/f(i) = X[i+1]*X[i+2]*...*X[n]*Y[n]/X[i] <= 1이어야 하는데
10^9 < 2^30 <= X[i+1]*X[i+2]*...*X[n] <= X[i]/Y[n] <= 10^9 이므로 모순이기 때문이다.

X[x]>1인 x를 내림차순 정렬한 수열을 {x_i}라 하자.(x_0=n, 예외로 이 수열의 마지막 항은 항상 0이다.)
X[1]*x[2]*...*X[i]*Y[k] (k는 x_i<=j<x_i-1일 때 최대 Y[j]를 만드는 j)
i<=30에 대한 k가 최대 f(x)를 만드는 x의 후보가 될 수 있다. xi는 우선순위 큐를 이용해 관리할 수 있을 것이다.

최댓값은 x[1]*x[2]*...*x[i]와 y[i...j]의  최댓값을 구하는 세그먼트 트리를 활용하여 구할 수 있다.

#include<cstdio>
#include<queue>
#include<algorithm>
#define mod 1000000007
using namespace std;
const int MXN = 5e5;
int n, m, x[MXN], tmul[MXN * 4], tmax[MXN * 4];
priority_queue<int> pq;
void upmax(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l == r) {
        tmax[h] = x;
        return;
    }
    upmax(h * 2 + 1, l, (l + r) / 2, g, x);
    upmax(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    tmax[h] = max(tmax[h * 2 + 1], tmax[h * 2 + 2]);
}
int qmax(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 1;
    if (gl <= l&&r <= gr) return tmax[h];
    return max(qmax(h * 2 + 1, l, (l + r) / 2, gl, gr), qmax(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
void upmul(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l == r) {
        tmul[h] = x;
        return;
    }
    upmul(h * 2 + 1, l, (l + r) / 2, g, x);
    upmul(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    tmul[h] = (long long)tmul[h * 2 + 1] * tmul[h * 2 + 2] % mod;
}
int qmul(int h, int l, int r, int g) {
    if (g < l) return 1;
    if (r <= g) return tmul[h];
    return (long long)qmul(h * 2 + 1, l, (l + r) / 2, g)*qmul(h * 2 + 2, (l + r) / 2 + 1, r, g) % mod;
}
void res() {
    int last = n, use[30], ucnt = 0;
    long long maxi = 1;
    for (int i = 0; i < 30 && maxi <= 1e9; i++) {
        while (!pq.empty() && (x[pq.top()] == 1 || pq.top() == last)) pq.pop();
        if (pq.empty()) break;
        maxi = max(maxi, 1LL * qmax(0, 0, n - 1, pq.top(), last - 1));
        maxi *= x[pq.top()];
        use[ucnt++] = last = pq.top();
        pq.pop();
    }
    if (pq.empty()) maxi = max(maxi, 1LL * qmax(0, 0, n - 1, 0, last - 1)), last = 0;
    printf("%lld\n", maxi%mod*qmul(0, 0, n - 1, last - 1) % mod);
    while (ucnt--) pq.push(use[ucnt]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", x + i);
        pq.push(i);
        upmul(0, 0, n - 1, i, x[i]);
    }
    for (int i = 0, y; i < n; i++) {
        scanf("%d", &y);
        upmax(0, 0, n - 1, i, y);
    }
    scanf("%d", &m);
    res();
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1) {
            pq.push(b);
            upmul(0, 0, n - 1, b, x[b] = c);
        }
        else upmax(0, 0, n - 1, b, c);
        res();
    }
    return 0;
}