POJ 3776 - Passing the Message

http://poj.org/problem?id=3776

概要

\(N\) 人の子供が一列に並んでいる。 各子供の left messenger と right messenger はそれぞれ何番目の子供か答える。

• A の left messenger とは、A の left follower のうち最も背が高い子供である
• A の left follower とは、A より左側にいて、A より背が低く、A から見える子供である (もちろん、複数存在しうる)
• A の左側にいる子供のうち、A より背が高い最も近い子供までのすべての子供を、A は見ることができる
• right messenger の定義も同様

制約

• \(0 < N \le 50000\)
• 子供の高さ \(h < 2 ^ {31} - 1\)
• 子供の高さはユニーク

解法

半区間 \([0, N-1)\) からスタートし、 半区間内で最も背の高い子供を \(I\) とすると、 \(I\) の left follower は半区間 \([0, I)\) で最も背が高い子供であり、 再帰的にその半区間内でも同様の処理を行う。 \(I\) の right follower は半区間 \([I+1, N)\) で最も背が高い子供であり、 再帰的にその半区間内でも同様の処理を行う。

半区間内で最も背の高い子供を見つけるのには SegmentTree を使った。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <functional>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 template <class T, class Compare>
  8 struct SegmentTree/*{{{*/
  9 {
 10   vector<T>& mem;
 11   vector<int> indexes;
 12   Compare cmp;
 13   SegmentTree(vector<T>& cs)
 14     : mem(cs), indexes(4*cs.size(), -1)
 15   {
 16     build(0, 0, cs.size());
 17   }
 18 
 19   void build(int idx, int left, int right)
 20   {
 21     if (left+1 == right) {
 22       indexes[idx] = left;
 23     } else {
 24       const int mid = (left + right)/2;
 25       build(2*idx+1, left, mid);
 26       build(2*idx+2, mid, right);
 27       // minimum in [left, right)
 28       if (cmp(mem[indexes[2*idx+1]], mem[indexes[2*idx+2]])) {
 29         indexes[idx] = indexes[2*idx+1];
 30       } else {
 31         indexes[idx] = indexes[2*idx+2];
 32       }
 33     }
 34   }
 35 
 36   inline int query_index(int left, int right) const { return query_index(left, right, 0, 0, mem.size()); }
 37 
 38   int query_index(int left, int right, int i, int a, int b) const
 39   {
 40     // [a, b) is the range of indexes[i]
 41     if (b <= left || right <= a) {
 42       // does not intersect
 43       return -1;
 44     } else if (left <= a && b <= right) {
 45       // contains
 46       return indexes[i];
 47     } else {
 48       const int m = (a+b)/2;
 49       const int l = query_index(left, right, 2*i+1, a, m);
 50       const int r = query_index(left, right, 2*i+2, m, b);
 51       if (l == -1) {
 52         return r;
 53       } else if (r == -1) {
 54         return l;
 55       } else {
 56         if (cmp(mem[l], mem[r])) {
 57           return l;
 58         } else {
 59           return r;
 60         }
 61       }
 62     }
 63   }
 64 
 65 };/*}}}*/
 66 
 67 static const int MAXN = 50000;
 68 int ansl[MAXN], ansr[MAXN];
 69 
 70   template <class T, class Compare>
 71 void solve(const SegmentTree<T, Compare>& seg, int self, int left, int right)
 72 {
 73   if (left == right) {
 74     return;
 75   }
 76   if (left == self) {
 77     ansl[self] = 0;
 78   } else {
 79     const int l = seg.query_index(left, self);
 80     ansl[self] = l+1;
 81     solve(seg, l, left, self);
 82   }
 83   if (right == self+1) {
 84     ansr[self] = 0;
 85   } else {
 86     const int r = seg.query_index(self+1, right);
 87     ansr[self] = r+1;
 88     solve(seg, r, self+1, right);
 89   }
 90 }
 91 
 92 int main()
 93 {
 94   int T;
 95   scanf("%d", &T);
 96   for (int Ti = 1; Ti <= T; Ti++) {
 97     int N;
 98     scanf("%d", &N);
 99     vector<int> v(N);
100     int tallest = 0, height = 0;
101     for (int i = 0; i < N; i++) {
102       scanf("%d", &v[i]);
103       if (v[i] > height) {
104         height = v[i];
105         tallest = i;
106       }
107     }
108 
109     const SegmentTree<int, greater<int> > seg(v);
110     printf("Case %d:\n", Ti);
111     solve(seg, tallest, 0, N);
112     for (int i = 0; i < N; i++) {
113       printf("%d %d\n", ansl[i], ansr[i]);
114     }
115   }
116   return 0;
117 }