O(n) returns root of the tree has max heap property
| 34 | //returns root of the tree |
| 35 | //has max heap property |
| 36 | int cartesian_tree() { |
| 37 | tot = 0; |
| 38 | for (int i = 1; i <= n; i++) l[i] = r[i] = vis[i] = 0; |
| 39 | for (int i = 1; i <= n; i++) { |
| 40 | int k = tot; |
| 41 | while (k > 0 && a[st[k - 1]] < a[i]) k--; //use > for min heap |
| 42 | if (k) r[st[k - 1]] = i; |
| 43 | if (k < tot) l[i] = st[k]; |
| 44 | st[k++] = i; |
| 45 | tot = k; |
| 46 | } |
| 47 | for (int i = 1; i <= n; i++) vis[l[i]] = vis[r[i]] = 1; |
| 48 | int rt = 0; |
| 49 | for (int i = 1; i <= n; i++) { |
| 50 | if (vis[i] == 0) rt = i; |
| 51 | } |
| 52 | return rt; |
| 53 | } |
| 54 | |
| 55 | |
| 56 | //given an array find the probability of any array having each element in [0,1](real numbers) |