FZU2136--取糖果 (线段树+RMQ)
2015-04-24 10:26:39         来源：Alex

Problem Description

Input

Output

Sample Input
1
5
1 3 2 4 5
Sample Output
1
3
3
4
5

``````/*************************************************************************
> File Name: FZU2136.cpp
> Author: ALex
> Mail: zchao1995@gmail.com
> 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 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;
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 << 1].add == -1) {
}
else {
}
if (tree[p << 1 | 1].add == -1) {
}
else {
}
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);
}
}

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);
}
else {
}
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;
}``````