1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #include <cstdio> using namespace std; const int N = 1e7 + 10; struct Node { int l, r, v; } tr[N]; int n; int top, stk[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &tr[i].v); for (int i = 1, pos; i <= n; i++) { pos = top; while (pos && tr[stk[pos]].v > tr[i].v) pos--; if (pos) tr[stk[pos]].r = i; if (pos < top) tr[i].l = stk[pos + 1]; stk[top = ++pos] = i; } return 0; }
|