117 lines
2.9 KiB
C++
117 lines
2.9 KiB
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
class Solution {
|
|
public:
|
|
struct tnode{
|
|
int l,r;
|
|
int sum;//segment sum
|
|
int val;//segment max
|
|
};
|
|
//vector<int> a;//input
|
|
vector<struct tnode> tree;
|
|
void buildtree(int no,int l,int r,vector<int> &a){
|
|
tree[no].l=l;
|
|
tree[no].r=r;
|
|
int mid=(l+r)/2;
|
|
if (l==r){
|
|
//segment max
|
|
tree[no].val=a[l];
|
|
//segment sum
|
|
//tree[no].sum=a[l];
|
|
}
|
|
else{
|
|
buildtree(no*2,l,mid,a);
|
|
buildtree(no*2+1,mid+1,r,a);
|
|
// segment max
|
|
tree[no].val=max(tree[no*2].val,tree[no*2+1].val);
|
|
// segment sum
|
|
//tree[no].sum=tree[no*2].sum+tree[no*2+1].sum;
|
|
}
|
|
return;
|
|
}
|
|
/*
|
|
//更新区间和
|
|
void update0(int no,int lr, int val) {
|
|
if (tree[no].l==lr && tree[no].r==lr){
|
|
tree[no].sum=val;
|
|
return;
|
|
}
|
|
|
|
int mid=(tree[no].l+tree[no].r)/2;
|
|
if (lr>mid){
|
|
update0(no*2+1,lr,val);
|
|
}
|
|
else{
|
|
update0(no*2,lr,val);
|
|
}
|
|
tree[no].sum=tree[no*2].sum+tree[no*2+1].sum;
|
|
}
|
|
|
|
void update(int index, int val) {
|
|
update0(1,index+1,val);
|
|
}
|
|
|
|
//查找区间和
|
|
int query(int no,int l, int r) {
|
|
if (tree[no].l==l && tree[no].r==r)
|
|
return tree[no].sum;
|
|
|
|
int mid=(tree[no].l+tree[no].r)/2;
|
|
if (l>mid)
|
|
return query(no*2+1,l,r);
|
|
else if (r<=mid)
|
|
return query(no*2,l,r);
|
|
else
|
|
return query(no*2,l,mid)+query(no*2+1,mid+1,r);
|
|
}
|
|
*/
|
|
//查找区间大于v的最左侧位置
|
|
int query(int no,int v, int pos,int l, int r) {
|
|
if (tree[no].val<=v)
|
|
return -1;
|
|
if (l==r)
|
|
return l;
|
|
|
|
int mid=(l+r)/2;
|
|
if (pos<=mid){
|
|
int res=query(no*2,v,pos,l,mid);
|
|
if (res>=0)
|
|
return res;
|
|
}
|
|
return query(no*2+1,v,pos,mid+1,r);
|
|
}
|
|
|
|
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
|
|
int n=heights.size();
|
|
tree.resize(4*n+1);
|
|
buildtree(1,0,n-1,heights);
|
|
int qn=queries.size();
|
|
vector<int> res(qn);
|
|
for (int i=0;i<qn;i++){
|
|
int a=queries[i][0];
|
|
int b=queries[i][1];
|
|
if (a>b) swap(a,b);
|
|
if (a==b){
|
|
res[i]=a;
|
|
}else if (heights[b]>heights[a]){
|
|
res[i]=b;
|
|
}else{
|
|
res[i]=query(1,heights[a],b+1,0,n-1);
|
|
}
|
|
}
|
|
return res;
|
|
}
|
|
};
|
|
int main()
|
|
{
|
|
Solution sol;
|
|
vector<int> heights={3,1,2,4,5};
|
|
vector<vector<int>> queries={{0,1},{1,0}};
|
|
vector<int> res=sol.leftmostBuildingQueries(heights,queries);
|
|
for (auto r:res){
|
|
cout << r << " ";
|
|
}
|
|
cout << endl;
|
|
return 0;
|
|
}
|