难得自己想出最后一题，十分开心的来写题解。
题目给我们一段数组，然后让我们将其分为三段，使得第一段的最大值等于第二段的最小值等于第三段的最大值。
这种区间问题显而易见就得用一些对区间操作的数据结构比如st表树状数组啥的，我比较喜欢线段树那必然就用线段树了。
要寻找的话用n^2的枚举显然是不现实的，所以本蒟蒻便考虑二分答案，先枚举出第一段的位置，再二分出第二段的位置，时间复杂度大概是nlognlogn。
#include<iostream> #include<algorithm> using namespace std; int all[2000005]; struct node { int l, r, maxx, minn; }a[2000005]; void up_data(int i) { a[i].maxx = max(a[i << 1].maxx, a[i << 1 | 1].maxx); a[i].minn = min(a[i << 1].minn, a[i << 1 | 1].minn); return; } void build(int l, int r,int i) { a[i].l = l; a[i].r = r; if (l == r) { a[i].maxx = all[l]; a[i].minn = all[l]; return; } int mid = (l + r) >> 1; build(l, mid, i << 1); build(mid + 1, r, i << 1 | 1); up_data(i); } int find_max(int l, int r, int i) { if (a[i].l >= l && a[i].r <= r) { return a[i].maxx; } int now = 0; if (a[i << 1].r >= l)now = max(now, find_max(l, r, i << 1)); if (a[i << 1 | 1].l <= r)now = max(now, find_max(l, r, i << 1 | 1)); return now; } int find_min(int l, int r, int i) { if (a[i].l >= l && a[i].r <= r) { return a[i].minn; } int now = 0x7fffffff; if (a[i << 1].r >= l)now = min(now, find_min(l, r, i << 1)); if (a[i << 1 | 1].l <= r)now = min(now, find_min(l, r, i << 1 | 1)); return now; } int main() { int t; cin >> t; while (t--) { int n, flag = 0; cin >> n; for (int i = 1; i <= n; i++) cin >> all[i]; build(1, n, 1); for (int i = 1; i <= n; i++) { int here = find_max(1, i, 1); int l = i + 1, r = n - 1; while (l <= r) { int mid = (l + r) / 2; int s = find_min(i + 1 , mid, 1); int last = find_max(mid + 1, n, 1); if (s == here && last == here) { flag = 1; cout << "YES" << endl; cout << i << " " << mid - i << " " << n - mid << endl; break; } else if (s <= here && last <= here) { r = mid - 1; } else if (s >= here && last >= here)l = mid + 1; else break; } if (flag)break; } if(!flag) cout << "NO" << endl; } return 0; }
原文：https://www.cnblogs.com/redintoncforever/p/14504784.html