非原创，来自多校题解
不是自己写的，惭愧ing……
留着以后自己参考……
lower_bound {1,2,4,5} 询问 2，返回的是 2 ,询问3 返回的是 4 是大于等于元素的值
upper_bound {1,2,4,5} 询问2，返回4，询问3，返回4，是 大于 元素的值
题意：图论的知识
1 2 3 4 5 6 （1）
1 4 5 6 3 2 （2）
（1）中 数字 1 的 位置没变 所以（1） 2 的为位置 编程了 4 ，4 的位置变成了 6，6的位置变为 2 即 2 -> 4 -> 6 -> 2 所以(2，4，6)在一个群中而 相应的 4 -> 6 -> 2 -> 4 是等价的 所以也可以表达为 (4，6，2) 最后是 （3，5）
所以 操作为 (1) (2,4,6)(3,5)
问题是：给 你 操作 ，把 括号 去掉，让你安排括号的位置 使 重排 后 的 字典序最大
官方题解：http://bestcoder.hdu.edu.cn/blog/2015-multi-university-training-contest-4-solutions-by-%E5%AD%A6%E5%86%9B%E4%B8%AD%E5%AD%A6/ 第四场 最后一道题
不用线段树会超时……
#include <iostream> #include <cstdio> #include <cstring> #include <set> using namespace std; const int MAXN = 100000+10; const int inf = 0x7fffffff; int a[MAXN],ord[MAXN]; /*cut 该位置后是否加括号 *con 该元素 是否 已经 被 确定在某个括号里面 */ bool cut[MAXN],con[MAXN]; set<int>cuts;//存放的是左括号和右括号 int n; int seg[MAXN*4]; void cutit(int x){ //加括号 if(!cut[x]){ cut[x] = 1; cuts.insert(x); } } void build(int l,int r,int x){ //建树 if(l == r){ seg[x] = a[r]; return; } int mid = (l+r)>>1; build(l,mid,x<<1); build(mid+1,r,x<<1|1); seg[x] = max(seg[x<<1],seg[x<<1|1]); } int v,l1,r1,I; void que(int l,int r,int x){ //查询区间最值 if(l >= l1 && r <= r1){ v = max(v,seg[x]); return; } int mid = (l+r)>>1; if(mid >= l1){ que(l,mid,x<<1); } if(mid < r1){ que(mid+1,r,x<<1|1); } } void upd(int l,int r,int x){ //把用掉的值消除掉 if(l == r){ seg[x] = -inf; return; } int mid = (l+r)>>1; if(I <= mid){ upd(l,mid,x<<1); }else{ upd(mid+1,r,x<<1|1); } seg[x] = max(seg[x<<1],seg[x<<1|1]); } void conit(int x){ //用掉的值 if(!con[x]){ con[x] = 1; I = x; upd(1,n,1); } } int ans[MAXN]; int main(){ // freopen("input.txt","r",stdin); int T; scanf("%d",&T); while(T--){ cuts.clear(); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); ord[a[i]] = i; con[i] = cut[i] = 0; } con[n+1] = cut[n+1] = 0; build(1,n,1); cutit(1); //加 cutit(n+1);//加括号 for(int k = 1;k<=n;k++){ int i = ord[k]; int r = -inf; if(!cut[i+1]){ //下一个元素的值 r = a[i+1]; } int l = -inf; if(!con[i+1]){ //左边最靠近i位置的括号的坐标 /*cuts 中存放的是左括号和右括号的坐标 *cuts中寻找已知括号 */ set<int>::iterator it = cuts.lower_bound(i+1); it--; l1 = *it; //线段树的左边界应该是从距离i位置最近的括号开始 r1 = i;//线段树的有边界是 i v = -inf; que(1,n,1);//寻找最大值 l = v; } if(r > l){ //如果不能插入括号 ans[k] = r; conit(i+1); //把i+1的值消除掉影响 }else{ // 如果能插入括号 ans[k] = l;//则结果为最邻近括号的最大值 int pos = ord[l]; cutit(pos); cutit(i+1); for(int j = pos+1;j <= i;j++){//消除掉影响，后面的则指向下一个 conit(j); } } } for(int i = 1;i<= n;i++){ if(i > 1){ printf(" "); } printf("%d",ans[i]); } printf(" "); } return 0; }