P2048 [NOI2010] 슈퍼 피아노

연속 부분 수열의 합을 전처리하고 RMQ를 사용하여 최대값을 찾습니다.

우선순위 큐를 사용하여 최적의 답을 저장합니다.

힙의 맨 위 요소를 꺼내서 계산한 후, 해당 지점을 제외하고 두 개의 새로운 구간을 다시 큐에 추가합니다. 이 과정을 k번 반복합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#define MAXN 500010
#define INF 0x3f3f3f3f
#define ll long long

using namespace std;

int n, k, L, R;
ll ans;
ll prefix[MAXN];
int st[MAXN][20];
struct Interval {
    int start, end, left, right;
    bool operator<(const Interval &b) const {
        return prefix[end] - prefix[start-1] < prefix[b.end] - prefix[b.start-1];
    }
};

int readInt() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int rangeMaxQuery(int l, int r) {
    int len = log2(r - l + 1);
    int x = st[l][len], y = st[r - (1 << len) + 1][len];
    return prefix[x] > prefix[y] ? x : y;
}

int main() {
    n = readInt(); k = readInt(); L = readInt(); R = readInt();
    for (int i = 1; i <= n; i++) {
        int val = readInt();
        prefix[i] = prefix[i-1] + val;
        st[i][0] = i;
    }
    
    int logN = log2(n);
    for (int j = 1; j <= logN; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int x = st[i][j-1], y = st[i + (1 << (j-1))][j-1];
            st[i][j] = prefix[x] > prefix[y] ? x : y;
        }
    }
    
    priority_queue<Interval> pq;
    for (int i = 1; i <= n; i++) {
        if (i + L - 1 <= n) {
            int end = min(n, i + R - 1);
            pq.push({i, rangeMaxQuery(i + L - 1, end), i + L - 1, end});
        }
    }
    
    for (int i = 1; i <= k; i++) {
        Interval cur = pq.top();
        pq.pop();
        ans += prefix[cur.end] - prefix[cur.start-1];
        
        if (cur.left != cur.end) {
            int newEnd = cur.end - 1;
            pq.push({cur.start, rangeMaxQuery(cur.left, newEnd), cur.left, newEnd});
        }
        if (cur.right != cur.end) {
            int newStart = cur.end + 1;
            pq.push({cur.start, rangeMaxQuery(newStart, cur.right), newStart, cur.right});
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}

UVA11235 빈도 값

비감소 수열이므로 각 숫자의 값과 빈도를 직접 계산할 수 있습니다. 즉, 숫자 구간의 길이를 계산합니다.

각 구간의 시작과 끝, 그리고 각 위치가 속한 구간 번호를 기록합니다.

(l, r) 구간을 조회할 때, 중간의 여러 구간과 양쪽의 부분 구간을 확인할 수 있습니다. 중간 구간은 ST 테이블을 사용합니다.

#include <iostream>
#include <vector>
#include <cmath>
#define MAXN 100010

using namespace std;

int n, q, le, ri, ans;
int arr[MAXN], segment[MAXN], leftBound[MAXN], rightBound[MAXN];
int st[MAXN][20];

int readInt() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int rangeMaxQuery(int l, int r) {
    int len = log2(r - l + 1);
    return max(st[l][len], st[r - (1 << len) + 1][len]);
}

int main() {
    while (scanf("%d", &n) == 1) {
        if (n == 0) break;
        q = readInt();
        
        for (int i = 0; i < n; i++) arr[i] = readInt();
        arr[n] = arr[n-1] + 1;
        
        int start = -1;
        vector<int> lengths;
        
        for (int i = 1; i <= n; i++) {
            if (i == 0 || arr[i] > arr[i-1]) {
                if (i > 0) {
                    lengths.push_back(i - start);
                    for (int j = start; j < i; j++) {
                        segment[j] = lengths.size() - 1;
                        leftBound[j] = start;
                        rightBound[j] = i - 1;
                    }
                }
                start = i;
            }
        }
        
        int segCount = lengths.size();
        for (int i = 0; i < segCount; i++) st[i][0] = lengths[i];
        
        for (int j = 1; (1 << j) <= segCount; j++) {
            for (int i = 0; i + (1 << j) - 1 < segCount; i++) {
                st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
        
        while (q--) {
            le = readInt() - 1;
            ri = readInt() - 1;
            
            if (segment[le] == segment[ri]) {
                ans = ri - le + 1;
            } else {
                ans = max(ri - leftBound[ri] + 1, rightBound[le] - le + 1);
                if (segment[le] + 1 < segment[ri]) {
                    ans = max(ans, rangeMaxQuery(segment[le] + 1, segment[ri] - 1));
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

UVA11297 인구 조사

2차원 RMQ 문제입니다.

한 방향으로 세그먼트 트리를 만들고, 각 노드를 다른 방향의 새로운 세그먼트 트리로 설정합니다.

#include <iostream>
using namespace std;

int n, m;
int grid[501][501];
int maxTree[2001][2001], minTree[2001][2001];

int readInt() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

void buildY(int xIdx, int yIdx, int l, int r, int node) {
    if (l != r) {
        int mid = (l + r) >> 1;
        buildY(xIdx, yIdx, l, mid, node << 1);
        buildY(xIdx, yIdx, mid + 1, r, (node << 1) + 1);
        maxTree[xIdx][node] = max(maxTree[xIdx][node << 1], maxTree[xIdx][(node << 1) + 1]);
        minTree[xIdx][node] = min(minTree[xIdx][node << 1], minTree[xIdx][(node << 1) + 1]);
    } else {
        if (xIdx == yIdx) {
            maxTree[xIdx][node] = minTree[xIdx][node] = grid[xIdx][l];
        } else {
            maxTree[xIdx][node] = max(maxTree[xIdx << 1][node], maxTree[(xIdx << 1) + 1][node]);
            minTree[xIdx][node] = min(minTree[xIdx << 1][node], minTree[(xIdx << 1) + 1][node]);
        }
    }
}

void buildX(int node, int l, int r) {
    if (l != r) {
        int mid = (l + r) >> 1;
        buildX(node << 1, l, mid);
        buildX((node << 1) + 1, mid + 1, r);
    }
    buildY(node, 1, 1, n, 1);
}

void queryY(int xIdx, int yIdx, int l, int r, int ql, int qr, int node) {
    if (l >= ql && r <= qr) {
        maxTree[0][0] = max(maxTree[0][0], maxTree[xIdx][node]);
        minTree[0][0] = min(minTree[0][0], minTree[xIdx][node]);
    } else {
        int mid = (l + r) >> 1;
        if (ql <= mid) queryY(xIdx, yIdx, l, mid, ql, qr, node << 1);
        if (qr > mid) queryY(xIdx, yIdx, mid + 1, r, ql, qr, (node << 1) + 1);
    }
}

void queryX(int node, int l, int r, int xl, int xr, int yl, int yr) {
    if (l >= xl && r <= xr) {
        queryY(node, 1, 1, n, yl, yr, 1);
    } else {
        int mid = (l + r) >> 1;
        if (xl <= mid) queryX(node << 1, l, mid, xl, xr, yl, yr);
        if (xr > mid) queryX((node << 1) + 1, mid + 1, r, xl, xr, yl, yr);
    }
}

void updateY(int xIdx, int yIdx, int l, int r, int pos, int val, int node) {
    if (l == r) {
        if (val == -1) {
            maxTree[xIdx][node] = max(maxTree[xIdx << 1][node], maxTree[(xIdx << 1) + 1][node]);
            minTree[xIdx][node] = min(minTree[xIdx << 1][node], minTree[(xIdx << 1) + 1][node]);
            return;
        }
        maxTree[xIdx][node] = minTree[xIdx][node] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) updateY(xIdx, yIdx, l, mid, pos, val, node << 1);
    else updateY(xIdx, yIdx, mid + 1, r, pos, val, (node << 1) + 1);
    maxTree[xIdx][node] = max(maxTree[xIdx][node << 1], maxTree[xIdx][(node << 1) + 1]);
    minTree[xIdx][node] = min(minTree[xIdx][node << 1], minTree[xIdx][(node << 1) + 1]);
}

void updateX(int node, int l, int r, int x, int y, int val) {
    if (l == r) updateY(node, 1, 1, n, y, val, 1);
    else {
        int mid = (l + r) >> 1;
        if (x <= mid) updateX(node << 1, l, mid, x, y, val);
        else updateX((node << 1) + 1, mid + 1, r, x, y, val);
        updateY(node, 1, 1, n, y, -1, 1);
    }
}

int main() {
    n = readInt();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            grid[i][j] = readInt();
        }
    }
    buildX(1, 1, n);
    m = readInt();
    
    for (int i = 1; i <= m; i++) {
        char op;
        cin >> op;
        if (op == 'q') {
            int x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt();
            maxTree[0][0] = 0;
            minTree[0][0] = 1e9;
            queryX(1, 1, n, x1, x2, y1, y2);
            printf("%d %d\n", maxTree[0][0], minTree[0][0]);
        } else {
            int x = readInt(), y = readInt(), val = readInt();
            updateX(1, 1, n, x, y, val);
        }
    }
    return 0;
}