Google Kickstart Round-D D. Locked Doors（线段树+二分）

本文主要是介绍Google Kickstart Round-D D. Locked Doors（线段树+二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
$n$ 个点，相邻两点之间有一条边，每条边边权不同。
有 $q$ 次询问，每次询问给你一个起点 $s$ ，从这个点出发，每次往左右边权更小的点跑，求第 $k$ 个点是什么。
思路：
参考代码：https://doowzs.com/code/ks2020d-d/
想到了线段树，没想到二分。

假设是求第 $k$ 个点，那结果可以看作是能包含 $k$ 个点的窗口。
假设窗口左移，那么窗口左部分（起点 $s$ 左部分）的最大值一定会大于右部分最大值，否则移动的过程就会优先往左移。
同理窗口右移，那么左部分最大值一定会小于有部分最大值。
因此可以通过二分+线段树求区间最大值找到窗口的正确位置。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4e5 + 7;
int d[maxn];
int n,q;
struct Tree {int l,r;int mx;
}t[maxn << 2];
void build(int i,int l,int r) {t[i].l = l;t[i].r = r;if(l == r) {t[i].mx = d[l];return;}int m = (l + r) >> 1;build(i * 2,l,m);build(i * 2 + 1,m + 1,r);t[i].mx = max(t[i * 2].mx,t[i * 2 + 1].mx);
}
int query(int i,int x,int y) {if(x <= t[i].l && t[i].r <= y) {return t[i].mx;}int m = (t[i].l + t[i].r) >> 1;int ans = 0;if(x <= m) ans = max(ans,query(i * 2,x,y));if(y > m) ans = max(ans,query(i * 2 + 1,x,y));return ans;
}
bool check(int s,int k,int left) {int L = s - left,R = s + (k - left);int mxL = query(1,L,s - 1);int mxR = query(1,s,R);return mxL < mxR;
}
int solve(int s,int k) {int left = 0,l = max(1,k - (n - s)),r = min(s - 1,k);while(l <= r) {int mid = (l + r) >> 1;if(check(s,k,mid)) {left = mid;l = mid + 1;} else {r = mid - 1;}}int ansL = s - left - 1;int ansR = s + (k - left);return d[ansL] < d[ansR] ? ansL : ansR + 1;
}
int main() {int T;scanf("%d",&T);int kase = 0;while(T--) {scanf("%d%d",&n,&q);for(int i = 1;i < n;i++) {scanf("%d",&d[i]);}d[0] = d[n] = INF;build(1,0,n);printf("Case #%d: ",++kase);for(int i = 1;i <= q;i++) {int s = 0,k = 0;scanf("%d %d",&s,&k);printf("%d ",k == 1 ? s : solve(s,k - 2));}printf("\n");}return 0;
}