0x06 倍增

1.可以代替lowerbound

2.可以代替二分

3.效率更高

AcWing 109. 天才ACM 

二分答案，但可以用倍增替代

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500005;

int n, m;
int ans;
ll T;
ll w[N], t[N];
ll tmp[N];

ll sq(ll x)
{
    return x * x;
}

bool check(int l, int mid, int r){
    for (int i = mid; i < r; i ++ )
        t[i] = w[i];
    sort(t + mid, t + r);
    int i = l, j = mid, k = 0;
    while (i != mid && j != r)
        if (t[i] < t[j])
            tmp[k ++ ] = t[i ++ ];
        else
            tmp[k ++ ] = t[j ++ ];
    while (i != mid) tmp[k ++ ] = t[i ++ ];
    while (j != r) tmp[k ++ ] = t[j ++ ];
    ll sum = 0;
    for (i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(tmp[i] - tmp[k - 1]);
    return sum <= T;
}

int main()
{
    int K;
    scanf("%d", &K);
    while (K -- )
    {
        scanf("%d %d %lld\n", &n, &m, &T);
        for (int i = 0; i < n; i ++ )
            scanf("%lld", &w[i]);
        ans = 0;
        int len;
        int start = 0, end = 0;
        while (end < n)
        {
            len = 1;
            while (len)
            {
                if (end + len <= n && check(start, end, end + len))
                {
                    end += len, len <<= 1;
                    if (end >= n) break ;
                    for (int i = start; i < end; i ++ )
                        t[i] = tmp[i - start];
                }
                else    len >>= 1;
            }
            start = end;
            ans ++ ;
        }
        printf("%d\n", ans);
    }
    return 0;
}

区间最值问题

ST表

#include<bits/stdc++.h>
using namespace std;
int n,m,v[50001],dp1[50001][101],dp2[50001][101],logg[1000001];
void init(){
    logg[0]=-1;
    for(int i=1;i<=n;i++){
        dp1[i][0]=dp2[i][0]=v[i];
        logg[i]=logg[i>>1]+1;
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
            dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    init();
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        int c=logg[b-a+1];
        printf("%d\n",max(dp1[a][c],dp1[b-(1<<(c))+1][c])-min(dp2[a][c],dp2[b-(1<<(c))+1][c]));
    }
    return 0;
}