FJUT 1115优化题（2）（线段树+二分）

线段树+二分）"/>

FJUT 1115优化题（2）（线段树+二分）

题意：

给定n个点（xi,yi）。然后q个查询，每个查询是一个a，输出x坐标小于a的最大的y，不存在则输出-1

解析：

现将所有的坐标点按照x从小到大进行排序，然后每次搜索二分求出第一x坐标个小于a的数字的位置，然后用线段树求从0~该位置的最大值。

AC代码

#include <stdio.h>
#include <algorithm>
#define ls o*2
#define rs o*2+1
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100005;struct Point {int x, y;Point(int _x, int _y) {x = _x, y = _y;}Point() {}bool operator < (const Point& rhs) const {return x < rhs.x;}
}poi[N];int maxv[N<<2];
inline void maintain(int o) {maxv[o] = max(maxv[ls], maxv[rs]);
}void build(int o, int L, int R) {if(L == R) {maxv[o] = poi[L].y;return ;}int M = (L+R)/2;build(ls, L, M);build(rs, M+1, R);maintain(o);
}int ql, qr;
int query(int o, int L, int R) {if(ql <= L && R <= qr)return maxv[o];int M = (L+R)/2, ret = -INF;if(ql <= M) ret = max(ret, query(ls, L, M));if(qr > M) ret = max(ret, query(rs, M+1, R));return ret;
}int main() {int n, q, x;while(scanf("%d",&n)!=EOF) {for(int i = 0; i < n; i++)scanf("%d%d",&poi[i].x, &poi[i].y);sort(poi, poi+n);build(1, 0, n-1);scanf("%d",&q);int ans = 0;while(q--) {scanf("%d", &x);ql = 0;qr = lower_bound(poi, poi+n, Point(x, 0)) - poi - 1;if(qr < 0) ans = -1;else ans = query(1, 0, n-1);printf("%d\n",ans);}}return 0;
}