程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> FZU2136--取糖果 (線段樹+RMQ)

FZU2136--取糖果 (線段樹+RMQ)

編輯：C++入門知識

FZU2136--取糖果 (線段樹+RMQ)

Problem Description

有N個袋子放成一排，每個袋子裡有一定數量的糖果，lzs會隨機選擇連續的幾個袋子，然後拿走這些袋子中包含最多糖果的袋子。現問你，在選擇x個袋子的情況下，lzs最壞情況下，也就是最少會拿到多少個糖果？對於x取值為1到n都分別輸出答案。
Input

第一行一個整數T，表示有T組數據。

每組數據先輸入一行一個整數N(1<=N<=100000)，表示袋子數，接下來一行輸入N個正整數，輸入的第i個數表示第i個袋子所裝的糖果數。
Output

每組數據輸出n行，第i行表示lzs隨機取連續的i個袋子時的最壞情況下能拿到的糖果數。
Sample Input
1
5
1 3 2 4 5
Sample Output
1
3
3
4
5

我是先用rmq預處理區間最大值
然後枚舉每個袋子,往左往右二分得到一個最大的區間,此區間的最大值就是枚舉的袋子上的值,然後說明長度為1 -> R-L+1的區間都可以得到這個值,用線段樹去維護最小值就行了

/*************************************************************************
    > File Name: FZU2136.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年04月23日 星期四 18時24分43秒
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair  PLL;

static const int N = 101010;
int dp[N][20];
int LOG[N];
int arr[N];

struct node {
    int l, r;
    int add;
    int val;
}tree[N << 2];

void initRMQ(int n) {
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = arr[i];
    }
    for (int j = 1; j <= LOG[n]; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int ST(int l, int r) {
    int k = LOG[r - l + 1];
    return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}

void build(int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    tree[p].add = -1;
    if (l == r) {
        tree[p].val = inf;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    tree[p].val = inf;
}

void pushdown(int p) {
    if (tree[p].add != -1) {
        if (tree[p << 1].add == -1) {
            tree[p << 1].add = tree[p].add;
        }
        else {
            tree[p << 1].add = min(tree[p].add, tree[p << 1].add);
        }
        if (tree[p << 1 | 1].add == -1) {
            tree[p << 1 | 1].add = tree[p].add;
        }
        else {
            tree[p << 1 | 1].add = min(tree[p].add, tree[p << 1 | 1].add);
        }
        tree[p << 1].val = min(tree[p].add, tree[p << 1].val);
        tree[p << 1 | 1].val = min(tree[p].add, tree[p << 1 | 1].val);
        tree[p].add = -1;
    }
}

void update(int p, int l, int r, int val) {
    if (l == tree[p].l && r == tree[p].r) {
        tree[p].val = min(val, tree[p].val);
        if (tree[p].add == -1) {
            tree[p].add = val;
        }
        else {
            tree[p].add = min(tree[p].add, val);
        }
        return;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (r <= mid) {
        update(p << 1, l, r, val);
    }
    else if (l > mid) {
        update(p << 1 | 1, l, r, val);
    }
    else {
        update(p << 1, l, mid, val);
        update(p << 1 | 1, mid + 1, r, val);
    }
    tree[p].val = min(tree[p << 1].val, tree[p << 1 | 1].val);
}

int query(int p, int pos) {
    if (tree[p].l == tree[p].r) {
        return tree[p].val;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (pos <= mid) {
        return query(p << 1, pos);
    }
    else {
        return query(p << 1 | 1, pos);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    LOG[0] = -1;
    for (int i = 1; i <= 100000; ++i) {
        LOG[i] = (i & (i - 1)) ? LOG[i - 1] : LOG[i - 1] + 1;
    }
    while (t--) {
        int n;
        scanf("%d", &n);
        build(1, 1, n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &arr[i]);
        }
        initRMQ(n);
        for (int i = 1; i <= n; ++i) {
            int l = 1, r = i, mid;
            int L, R;
            L = R = i;
            while (l <= r) {
                mid = (l + r) >> 1;
                int maxs = ST(mid, i);
                if (maxs <= arr[i]) {
                    L = mid;
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
            l = i, r = n, mid;
            while (l <= r) {
                mid = (l + r) >> 1;
                int maxs = ST(i, mid);
                if (maxs <= arr[i]) {
                    R = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            update(1, 1, R - L + 1, arr[i]);
        }

        for (int i = 1; i <= n; ++i) {
            printf("%d\n", query(1, i));
        }
    }
    return 0;
}