poj 3264 RMQ線分ツリー
2006 ワード
zkw式セグメントツリーはRMQ問題を解決して、クエリーだけで、更新しなくて、とても簡単で、ps:どうしてC++はgccよりそんなに速いですか?gcc提出3047 ms、C++
の場合、1329 msしかかかりません.
の場合、1329 msしかかかりません.
#include <stdio.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a): (b)
#define inf 20000000
#define N 50001
struct tree_node
{
int min, max;
};
struct tree_node tree[131072];
int cow[N];
int n, M;
int min_h, max_h;
void build_tree()
{
int i;
for (M = 1; M < (n+2); M <<= 1);
//
for (i = 1; i <= n; i++) {
tree[i+M].min = tree[i+M].max = cow[i];
}
//
for (i = n+1; i%M != 1; i++) {
tree[(i%M)+M].min = inf;
tree[(i%M)+M].max = -1;
}
//
for (i = M-1; i > 0 ; i--) {
tree[i].min = MIN(tree[i<<1].min, tree[(i<<1)+1].min);
tree[i].max = MAX(tree[i<<1].max, tree[(i<<1)+1].max);
}
}
void query(int s, int t)
{
max_h = -1;
min_h = inf;
for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
if (~s&1) {
max_h = MAX(max_h, tree[s^1].max);
min_h = MIN(min_h, tree[s^1].min);
}
if (t&1) {
max_h = MAX(max_h, tree[t^1].max);
min_h = MIN(min_h, tree[t^1].min);
}
}
}
int main()
{
int i, q, s, t;
scanf("%d %d", &n, &q);
for (i = 1; i <= n; i++) {
scanf("%d", cow+i);
}
build_tree();
while (q--) {
scanf("%d %d", &s, &t);
query(s, t);
printf("%d
", max_h-min_h);
}
return 0;
}