看了下报错,输出全是 1。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, h[N], id[N];
int maxn[N][20];
void rmq()
{
for(int i = 1; i <= n; i++)
{
maxn[i][0] = h[i];
for(int j = 1; 1 << j <= i; j++)
maxn[i][j] = max(maxn[i][j - 1], maxn[i - (1 << j - 1)][j - 1]);
}
}
int getmax(int l, int r)
{
int k = __lg(r - l + 1);
return max(maxn[l + (1 << k) - 1][k], maxn[r][k]);
}
int l[N], r[N], q[N], tt, to[N][20], rr[N][20];
void init(int n, vector<int> H)
{
for(int i = 1; i <= n; i++) id[h[i] = H[i - 1]] = i;
for(int i = 1; i <= n; i++)
{
while(tt && h[q[tt]] < h[i]) r[q[tt--]] = i;
q[++tt] = i;
}
tt = 0;
for(int i = n; i; i--)
{
while(tt && h[q[tt]] < h[i]) l[q[tt--]] = i;
q[++tt] = i;
}
rmq();
for(int i = n; i; i--)
{
int pos = id[i];
if(l[pos] && r[pos]) to[pos][0] = h[l[pos]] > h[r[pos]] ? l[pos] : r[pos];
else if(l[pos]) to[pos][0] = l[pos];
else if(r[pos]) to[pos][0] = r[pos];
for(int j = 1; j <= 18; j++)
to[pos][j] = to[to[pos][j - 1]][j - 1];
}
for(int i = n; i; i--)
{
rr[i][0] = r[i];
for(int j = 1; j <= 18; j++)
rr[i][j] = rr[rr[i][j - 1]][j - 1];
}
}
int minimum_jumps(int a, int b, int c, int d)
{
a++, b++, c++, d++;
int maxn = getmax(c, d);
if(getmax(b, c - 1) > maxn) return -1;
int l1 = a, r1 = b;
while(l1 < r1)
{
int mid = l1 + r1 >> 1;
if(getmax(mid, c - 1) < maxn) r1 = mid;
else l1 = mid + 1;
}
int now = id[getmax(l1, b)];
l1 = c, r1 = d;
while(l1 < r1)
{
int mid = l1 + r1 >> 1;
if(getmax(c, mid) > getmax(now, c - 1)) r1 = mid;
else l1 = mid + 1;
}
int minn = h[l1];
int ans = 0;
for(int i = 18; ~i; i--)
if(to[now][i] && h[to[now][i]] < minn)
ans += 1 << i, now = to[now][i];
if(c <= r[now]) return ans + 1;
if(l[now] && h[l[now]] < maxn) return ans + 2;
for(int i = 18; ~i; i--)
if(rr[now][i] && rr[now][i] < c)
ans += 1 << i, now = rr[now][i];
return ans + 1;
}