勇者sky遇上的命中注定的恋人白羽竟然是妹妹2

代码

#include<cstdio>
#include<iostream>
using namespace std;

const int N = 1e6;
int n , y[N + 5] , m , k , Min[N + 5][23] , Max[N + 5][23] , ans;

inline void prepare()
{
    for(register int j = 1; (1 << j) <= n; j++)
        for(register int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            Min[i][j] = min(Min[i][j - 1] , Min[i + (1 << j - 1)][j - 1]);
            Max[i][j] = max(Max[i][j - 1] , Max[i + (1 << j - 1)][j - 1]);
        }
}

inline bool check(int mid , int m)
{
    int l = 1;
    for(register int i = 1; i <= m && l <= n; i++)
    {
        int r = l , smin = y[l] , smax = y[l];
        for(register int j = 22;j >= 0; j--) 
        if (r + (1 << j) <= n)
        {
            int tmin = Min[r + 1][j] , tmax = Max[r + 1][j];
            if (max(smax , tmax) - min(smin , tmin) <= mid)
            {
                r += (1 << j);
                smax = max(smax , tmax);
                smin = min(smin , tmin);
            }
        }
        l = r + 1;
    }
    return l > n;
}

inline int work(int m)
{
    int res , l = 0 , r = 1e9 , mid;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid , m)) res = mid , r = mid - 1;
        else l = mid + 1;
    }
    return res;
}

int main()
{
//  freopen("a.in" , "r" , stdin);
    scanf("%d" , &n);
    for(register int i = 1; i <= n; i++) 
    {
        scanf("%*d%d" , &y[i]); 
        Min[i][0] = Max[i][0] = y[i];
    }
    prepare();
    scanf("%d" , &k);
    while (k--)
    {
        scanf("%d" , &m);
        ans = work(m);
        if (ans & 1) printf("%.1lf\n" , ans * 1.0 / 2);
        else printf("%d\n" , ans / 2);
    }
}

勇者sky遇上的命中注定的恋人白羽竟然是妹妹2

原文：https://www.cnblogs.com/leiyuanze/p/12346523.html