zoj 3633 – Alice’s present

问题: 给出一个长度为 n(n <= 500000) 的整数数组,然后 m(m <= 50000) 个区间查询。 对每个查询,从右向左扫描区间,如果区间有重复元素,输出第一个重复的是啥,如果没有,输出 OK。 这道题可以归约成一个 RMQ 问题,但不是太明显,具体看代码注释。 整体时间空间复杂度均为 O(mnlog(n))。

具体 RMQ 相关请参见 Wikipedia

/* 3488118 2013-12-09 22:26:50 Accepted 3633 C++ 720 48020 呆滞的慢板

这题实际上是一道 RMQ,不过归约不是十分的明显:
1. 先预处理出一个数组,表示前一个与其相同的位置;
2. 然后对这个数组预处理 RMQ,用于查询区间最大值;
3. 每给定一个区间,查询的 RMQ 最大值即从右往左最先出现重复的位置;
4. 如果这个位置在 l 之后,说明有重复,输出该位置的数字;
5. 否则,说明在这个区间没用重复,输出 OK。
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

int n, m, a[500000];
int rmq[19][500000];

int bit_length(int b) {
    int ans = 0;
    while(b) {
        ++ans;
        b >>= 1;
    }
    return ans;
}

void rmq_build() {
    for(int i = 1; (1<<i) < n; ++i)
        for(int j = 0; j + (1<<i) <= n; ++j)
            rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
}

int rmq_query(int l, int r) {
    if(l == r) return -1;
    int len = bit_length(r - l) - 1;
    return max(rmq[len][l], rmq_query(l+(1<<len), r));
}

int main() {

    while(scanf("%d", &n) != EOF) {

        map<int, int> pre;
        memset(rmq, -1, sizeof(rmq));

        for(int i = 0, s = 0; i < n; ++i) {
            scanf("%d", a+i);
            map<int, int>::iterator it = pre.find(a[i]);
            if(it != pre.end()) rmq[0][i] = it->second;
            pre[a[i]] = i;
        }

        rmq_build();

        for(scanf("%d", &m); m--;) {
            int l, r, p;
            scanf("%d%d", &l, &r);
            p = rmq_query(l-1, r);
            if(p < l-1) puts("OK");
            else printf("%d\n", a[p]);
        }

        puts("");

    }

}

【转载请附】愿以此功德,回向 >>

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3633.html【zoj 3633 – Alice’s present】

发表评论

电子邮件地址不会被公开。 必填项已用*标注