POJ_3264 Balanced Lineup
問題
http://poj.org/problem?id=3264
解法
SegmentTree で RMQ みたいなことをする。
自力でせぐつりーを実装できるようになった。
#include <cstdio> #include <algorithm> using namespace std; const int INF = 1 << 29; int n, a[100001 * 2], b[100001 * 2], q; // a:最大値 b:最小値 void init(int _n){ n = 1; while(n < _n){ n*=2; } for(int i = 0; i < 2 * n; i++){ a[i] = -INF; b[i] = INF; } } void make(){ for(int i = n - 2; i >= 0; i--){ a[i] = max(a[i * 2 + 1], a[i * 2 + 2]); b[i] = min(b[i * 2 + 1], b[i * 2 + 2]); } } int rmq_a(int i, int j, int k, int l, int r){ if(l <= i && j <= r) return a[k]; if(r <= i || j <= l) return -INF; int ld = rmq_a(i, (i + j) / 2, k * 2 + 1, l, r); int rd = rmq_a((i + j) / 2, j, k * 2 + 2, l, r); return max(ld, rd); } int rmq_b(int i, int j, int k, int l, int r){ if(l <= i && j <= r) return b[k]; if(r <= i || j <= l) return INF; int ld = rmq_b(i, (i + j) / 2, k * 2 + 1, l, r); int rd = rmq_b((i + j) / 2, j, k * 2 + 2, l, r); return min(ld, rd); } int main(){ int _n; scanf("%d %d", &_n, &q); init(_n); for(int i = 0; i < _n; i++){ scanf("%d", &a[n - 1 + i]); b[n - 1 + i] = a[n - 1 + i]; } make(); for(int i = 0; i < q; i++){ int s, g; scanf("%d %d", &s, &g); s--; printf("%d\n", rmq_a(0, n, 0, s, g) - rmq_b(0, n, 0, s, g)); } return 0; }