本文主要是介绍POJ 1785 treap 或 RMQ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题大意就是。
建立一颗树，每个结点有两个关键字，要求第一个关键字满足二叉搜索树的性质，第二个结点满足堆的性质
首先，要把所有结点按照第一个关键字按非递减排序，这样之后，每个结点左边的结点都比该结点的第一个关键字小，右边的则第一个关键字都比他大。
这样的话按顺序每次插入右子树，因为要满足二叉搜索树的性质， 插入之后不能满足堆的性质时就左旋。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 55555
#define MAXM 5555
#define INF 100000007
using namespace std;
struct node
{int w, fa, lch, rch;char s[111];bool operator <(const node& a)const{return strcmp(s, a.s) <= 0;}
}p[MAXN];
int n;
void insert(int i)
{int j = i - 1;while(p[j].w < p[i].w) j = p[j].fa;p[i].lch = p[j].rch;p[j].rch = i;p[i].fa = j;
}
void solve(int rt)
{if(rt == 0) return;printf("(");solve(p[rt].lch);printf("%s/%d", p[rt].s, p[rt].w);solve(p[rt].rch);printf(")");
}
int main()
{char s[111], tmp[111];while(scanf("%d", &n) != EOF && n){for(int i = 1; i <= n; i++){scanf("%s", s);int j;for(j = 0; s[j]; j++)if(s[j] == '/') break;else tmp[j] = s[j];tmp[j++] = '\0';int num = 0;while(s[j]) {num = num * 10 + s[j] - '0'; j++;}strcpy(p[i].s, tmp);p[i].w = num;p[i].lch = p[i].rch = 0;p[i].fa = 0;}sort(p + 1, p + n + 1);p[0].w = INF;p[0].lch = p[0].rch = p[0].fa = 0;for(int i = 1; i <= n; i++) insert(i);solve(p[0].rch);printf("\n");}return 0;
}
然后还可以使用RMQ来搞
还是首先要排序
每次递归处理一个区间，找出有最大第二关键字的那个做根。他左边的就是他的左子树，右边的是右子树
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 55555
#define MAXM 5555
#define INF 100000007
using namespace std;
struct node
{int w;char s[111];bool operator <(const node& a)const{return strcmp(s, a.s) <= 0;}
}p[MAXN];
int mi[MAXN][17], mx[MAXN][17];
int n;
void rmqinit()
{for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = i;int m = (int)(log(n * 1.0) / log(2.0));for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){mx[j][i] = mx[j][i - 1];mi[j][i] = mi[j][i - 1];int k = j + (1 << (i - 1));if(k <= n){if(p[mx[j][i]].w < p[mx[k][i - 1]].w) mx[j][i] = mx[k][i - 1];if(p[mi[j][i]].w > p[mi[k][i - 1]].w) mi[j][i] = mi[k][i - 1];}}
}
int rmqmax(int l, int r)
{int m = (int)(log((r - l + 1) * 1.0) / log(2.0));if(p[mx[l][m]].w < p[mx[r - (1 << m) + 1][m]].w) return mx[r - (1 << m) + 1][m];else return mx[l][m];
}
void solve(int s, int t)
{if(s > t) return;int pos = rmqmax(s, t);printf("(");solve(s, pos - 1);printf("%s/%d", p[pos].s, p[pos].w);solve(pos + 1, t);printf(")");
}
int main()
{char s[111], tmp[111];while(scanf("%d", &n) != EOF && n){for(int i = 1; i <= n; i++){scanf("%s", s);int j;for(j = 0; s[j]; j++)if(s[j] == '/') break;else tmp[j] = s[j];tmp[j++] = '\0';int num = 0;while(s[j]) {num = num * 10 + s[j] - '0'; j++;}strcpy(p[i].s, tmp);p[i].w = num;}sort(p + 1, p + n + 1);rmqinit();solve(1, n);printf("\n");}return 0;
}这篇关于POJ 1785 treap 或 RMQ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
