Posted in ACM-ICPC, Segment Tree

POJ 3264 Balanced Lineup

8/11/2017
Problem: http://poj.org/problem?id=3264
Solution: Record the max and min value for each segment.


#include<iostream>
#include<climits>
#include<cmath>
#include<cstdio>
using namespace std;
int mi = INT_MAX;
int ma = INT_MIN;

struct node{
	int l, r;
	int max;
	int min;
};

node t[800005] = {0};

void build (int root, int l, int r) {
	t[root].l = l;
	t[root].r = r;
	t[root].max = INT_MIN;
	t[root].min = INT_MAX;
	if (l != r) {
		build(root * 2 + 1, l, (l + r) / 2);
		build(root * 2 + 2, (l + r) / 2 + 1, r);
	}
}

void insert (int root, int i, int v) {
	if (t[root].l == t[root].r) {
		t[root].min = v;
		t[root].max = v;
		return;
	}
	t[root].min = min(t[root].min, v);
	t[root].max = max(t[root].max, v);
	if (i <= (t[root].l + t[root].r) / 2) {
		insert (root * 2 + 1, i, v);
	} else {
		insert (root * 2 + 2, i, v);
	}
}

void search (int root, int l, int r) {
	int mid = (t[root].l + t[root].r) / 2;
	if (mi <= t[root].min && ma >= t[root].max) {
		return;
	}
	if (t[root].l == l && t[root].r == r) {
		mi = min(mi, t[root].min);
		ma = max(ma, t[root].max);
		return;
	}
	if (r <= mid) {
		search (root * 2 + 1, l, r);
	} else if (l >= mid + 1) {
		search (root * 2 + 2, l, r);
	} else {
		search (root * 2 + 1, l, mid);
		search (root * 2 + 2, mid + 1, r);
	}
	return;
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	build(0, 1, n);
	int tmp;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &tmp);
		insert(0, i, tmp);
	}
	for (int i = 1; i <= q; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		mi = INT_MAX;
		ma = INT_MIN;
		search(0, a, b);
		printf("%d\n", ma - mi);
	}
	return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s