此题可以先排序再用rmq递归解决。
当然可以用treap。
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn = 5e4 + 10; 6 struct Point{ 7 char str[15]; 8 int pr; 9 bool operator < (const Point& rhs) const{10 return strcmp(str, rhs.str) < 0;11 }12 }a[maxn];13 14 struct Data{15 int p, v;16 }st[maxn][20];17 18 int n;19 20 int query(int l, int r){21 int len = r - l, d = 0;22 while((1 << d) <= len) d++;23 if(st[l][d - 1].v > st[r - (1 << (d - 1))][d - 1].v) return st[l][d - 1].p;24 else return st[r - (1 << (d - 1))][d - 1].p;25 }26 27 void print(int l, int r){28 if(l > r) return;29 putchar('(');30 int maxp = query(l, r + 1);31 print(l, maxp - 1);32 printf("%s", a[maxp].str);33 print(maxp + 1, r);34 putchar(')');35 }36 37 void RMQ(){38 for(int j = 0; j < n; j++) st[j][0].v = a[j].pr, st[j][0].p = j;39 for(int i = 1; (1 << i) <= n; i++) for(int j = 0; j < n; j++){40 if(j + (1 << i) <= n){41 if(st[j][i - 1].v > st[j + (1 << (i - 1))][i - 1].v){42 st[j][i].v = st[j][i - 1].v;43 st[j][i].p = st[j][i - 1].p;44 }else{45 st[j][i].v = st[j + (1 << (i - 1))][i - 1].v;46 st[j][i].p = st[j + (1 << (i - 1))][i - 1].p;47 }48 }49 }50 }51 52 int main(){53 //freopen("in.txt", "r", stdin);54 //freopen("out.txt", "w", stdout);55 while(~scanf("%d", &n) && n){56 for(int i = 0; i < n; i++){57 scanf("%s", a[i].str);58 int len = strlen(a[i].str);59 a[i].pr = 0;60 for(int j = len - 1, p = 1; a[i].str[j] != '/'; j--, p *= 10)61 a[i].pr += p * (a[i].str[j] - '0');62 }63 sort(a, a + n);64 RMQ();65 print(0, n - 1);66 putchar('\n');67 }68 return 0;69 }