[ZJ][zkw線段樹] d801. SCOI2006 2.动态最值(minmax)＠Morris' Blog

2012-12-08 12:35:24| 人氣1,210| 回應1 | 上一篇 | 下一篇

[ZJ][zkw線段樹] d801. SCOI2006 2.动态最值(minmax)

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

內容：

有一个包含n个元素的数组，要求实现以下操作：DELETE k：删除位置k上的数。右边的数往左移一个位置。QUERY i j：查询位置i~j上所有数的最小值和最大值。例如有10个元素：

位置	1	2	3	4	5	6	7	8	9	10
元素	1	5	2	6	7	4	9	3	1	5

QUERY 2 8的结果为2 9。依次执行DELETE 3和DELETE 6（注意这时删除的是原始数组的元素7）后数组变为：

位置	1	2	3	4	5	6	7	8
元素	1	5	6	7	4	3	1	5

QUERY 2 8的结果为1 7。

輸入說明：

第一行包含两个数n, m，表示原始数组的元素个数和操作的个数。第二行包括n个数，表示原始数组。以下m行，每行格式为1 k或者2 i j，其中第一个数为1表示删除操作，为2表示询问操作。

輸出說明：

对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。

範例輸入： help

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

10 4
1 5 2 6 7 4 9 3 1 5
2 2 8
1 3
1 6
2 2 8

範例輸出：

2 9
1 7

提示：

50%的数据满足1<=n, m<=10⁴，删除操作不超过100个100%的数据满足1<=n, m<=10⁶, 1<=m<=10⁶对于所有的数据，数组中的元素绝对值均不超过10⁹

//这题是SCOI(四川)2006的第二题，时间限制是每组测试数据5s，还是遵循原来的限制吧，不过时间有点紧。
//由于原测试数据一共有10组，这里只取最大的那一组。

出處：

SCOI2006 第二题 (管理：liouzhou_101)

總共需要兩棵線段樹去維護。
一個線段樹是要維護最大最小值的查詢，令一個維護的是紀錄實際應該查找的區間。

一開始很傻的用 BIT 去維護，但是後來想是想錯了，那個複雜度是 O(logN*logN)。
O(logN) 的查找會是錯誤的。

#include <stdio.h>
#include <algorithm>
#define INF 200000000
using namespace std;
struct ND {
    int mx, mn;
} ST[1<<21|1];
int M, ST2[1<<21|1];

void setST(int n) {
    int i;
    for(i = 2*M-1; i > 0; i--) {
        ST[i].mx = -INF;
        ST[i].mn = INF;
        if(i >= M)
            ST2[i] = 1;
        else
            ST2[i] = ST2[i<<1]+ST2[i<<1|1];
    }
}
void modify(int x, int nv, int xv) {
    ST[x+M].mx = xv;
    ST[x+M].mn = nv;
    x = x+M;
    for(x >>= 1; x > 0; x >>= 1) {
        ST[x].mn = min(ST[x<<1].mn, ST[x<<1|1].mn);
        ST[x].mx = max(ST[x<<1].mx, ST[x<<1|1].mx);
    }
}
void query(int& s, int& t) {
    static int i;
    static ND ans;
    ans.mn = INF, ans.mx = -INF;
    for(s = s+M-1, t = t+M+1; (s^t) != 1;) {
        if(~s&1) {
            ans.mn = min(ans.mn, ST[s^1].mn);
            ans.mx = max(ans.mx, ST[s^1].mx);
        }
        if(t&1) {
            ans.mn = min(ans.mn, ST[t^1].mn);
            ans.mx = max(ans.mx, ST[t^1].mx);
        }
        s >>= 1, t >>= 1;
    }
    printf("%d %d\n", ans.mn, ans.mx);
}
int getIdx(int idx) {
    static int s;
    for(s = 1; s < M;) {
        if(ST2[s<<1] < idx)
            idx -= ST2[s<<1], s = s<<1|1;
        else
            s = s<<1;
    }
    return s-M+1;
}
void delIdx(int idx) {
    idx = idx+M-1;
    while(idx)
        ST2[idx]--, idx >>= 1;
}
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, m, i, j, sum;
    int I, J, c, A;
    while(scanf("%d %d", &n, &m) == 2) {
        for(M = 1; M < n+2; M <<= 1);
        setST(n);
        for(i = 1; i <= n; i++) {
            ReadInt(&A);
            modify(i, A, A);
        }
        while(m--) {
            ReadInt(&c);
            ReadInt(&I);
            if(c == 1) {
                I = getIdx(I);
                modify(I, INF, -INF);
                delIdx(I);
            } else {
                ReadInt(&J);
                I = getIdx(I);
                J = getIdx(J);
                query(I, J);
            }
        }
    }
    return 0;
}

我要檢舉

#d801#SCOI2006#2.动态最值(minmax)#zkw

台長： Morris

您可能對以下文章有興趣

[ZJ][模擬、旋轉] b125. 積木的拼疊問題（Bricks）

a081. NOI2000 Day2.2.青蛙过河

[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

[ZJ] d372. 4. 合法執行路徑問題

人氣(1,210) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類上一篇:[ZJ][一年後修正版][樹型DP] b174. 旅游规划

回應(1)