[ZJ][塊狀表] d476. 区间查询＠Morris' Blog

2012-10-17 19:54:17| 人氣1,121| 回應0 | 上一篇 | 下一篇

[ZJ][塊狀表] d476. 区间查询

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

一个长度为n的序列，支持两种操作：
1.输出[A, B]区间第k小的数(从小到大排序后第k个)
2.修改第I个数为W

輸入說明：

第二行N个数A[I](1<=A[I]<=1000000000)
以下M行，每行一个操作
Q i j k（查询[I,J]中第k小的数）或 C i W(把第I个数改成W）

輸出說明：

对于每个查询操作，输出每个查询结果

範例輸入：

範例輸出：

2
3

提示：

经典题目

出處：

vijos (管理：vijos_car)

寫完這題我發現我需要鍛煉二分，因為不想用太多的 IF，所以在二分的終止條件就相當的困難。

題解位址

1. 操作調查是 O(sqrt(n) * log(sqrt(n)))。
2. 切成 sqrt(n) 塊，每個使用插入排序法。
3. 記錄 1 1 2 3 3 中的 3 排名時，答案是 5
4. 對於區間[i, j], 設答案為 k, 暴力尋遍i,j所處"不完整的塊"的, 接著二分搜其中完整的塊。

#include <cstdio>
#include <algorithm>
#define oo 0xfffffff
using namespace std;
const int SIZE = 256;
int A[SIZE*SIZE];
int p[SIZE][SIZE];
int getIdx(int pd, int v) {
    static int l, r, m;
    l = 0, r = SIZE-1;
    while(l <= r) {
        m = (l+r)>>1;
        if(p[pd][m] == v)
            return m;
        if(p[pd][m] < v)
            l = m+1;
        else
            r = m-1;
    }
    return -1;
}
int getRank(int x, int y, int k) {
    int s = 0, l, r, m;
    while(x%SIZE && x <= y) {
        if(A[x] <= k)    s++;
        x++;
    }
    while((y+1)%SIZE && x <= y) {
        if(A[y] <= k)    s++;
        y--;
    }
    if(x > y)   return s;
    x /= SIZE, y /= SIZE;
    while(x <= y) {
        l = 0, r = SIZE-1, m;
        while(l < r) {
            m = (l+r+1)>>1;
            if(p[x][m] <= k)
                l = m;
            else
                r = m-1;
        }
        if(p[x][l] > k) l--;
        s += l+1;
        x++;
    }
    return s;
}
int main() {
    int n, q, i, j, k, d, idx;
    char cmd[3];
    while(scanf("%d %d", &n, &q) == 2) {
        for(i = 0; i < SIZE; i++)
            p[(n-1)/SIZE][i] = oo;
        for(i = 0; i < n; i++)
            scanf("%d", A+i), p[i/SIZE][i%SIZE] = A[i];
        for(i = (n-1)/SIZE; i >= 0; i--)
            sort(p[i], p[i]+SIZE);
        while(q--) {
            scanf("%s", cmd);
            if(cmd[0] == 'C') {
                scanf("%d %d", &i, &k), i--;
                d = i/SIZE, idx = getIdx(d, A[i]);
                while(idx < SIZE)
                    p[d][idx] = p[d][idx+1], idx++;
                idx = SIZE-2;
                while(idx >= 0 && k < p[d][idx])
                    p[d][idx+1] = p[d][idx], idx--;
                p[d][idx+1] = k, A[i] = k;
            } else {
                scanf("%d %d %d", &i, &j, &k), i--, j--;
                int l = 0, r = 1000000000, m;
                while(l < r) {
                    m = (l+r+1)>>1;
                    if(getRank(i, j, m) >= k)
                        r = m-1;
                    else
                        l = m;
                }
                printf("%d\n", r+1);
            }
        }
    }
    return 0;
}

我要檢舉

#塊狀表#動態#區間K大

台長： Morris

您可能對以下文章有興趣

[ZJ][字串處理] d477. 古韵之同心锁

[ZJ] a450. 棒棒糖比身高

[ZJ][拓樸] a454: TOI2010 第二題：專案時程

a207. 精準覆蓋問題(Exact cover)

人氣(1,121) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][逆元] a545. Stressful
此分類上一篇:[ZJ][非遞迴合併排序] d542. 10810 - Ultra-QuickSort

回應(0)