算法竞赛进阶指南——基本算法（倍增）

ST表

可以求区间最大、最小、gcd、lcm，符合 f(a, a) = a都可以
求区间最值，一个区间划分成两段
f[i][j]: 从i开始，长度为2^j的区间最值

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6 + 10;
int n, k, a[N];
int f[N][50];

//预处理 
void pre(){
	for(int i = 1; i <= n; i++) f[i][0] = a[i];
	//以2为底，n的对数 
	int t = log(n) / log(2);
	for(int j = 1; j <= t; j++)
		for(int i = 1; i <= n - (1 << j) + 1; i++)
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r){
	int k = log(r - l + 1) / log(2);
	return min(f[l][k], f[r - (1 << k) + 1][k]);
}

int main(){
  scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d", &k);
	pre();
	for(int i = 1; i <= n; i++){
		int l = max(1, i - k), r = min(n, i + k);
		printf("%d ", query(l, r));
	}
	return 0;
}

天才ACM

#pragma GCC optimize(3, "Ofast", "inline")
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;
int k, n, m;
int a[N], b[N];
long long t;

long long f(int l, int r){
    int z = 0;
    for(int i = l; i < r; i++) b[z++] = a[i];
    sort(b, b + z);
    long long res = 0;
    for(int i = 0, j = z - 1; i < m && i < j; i++, j--)
        res += (long long)(b[j] - b[i]) * (b[j] - b[i]);
    return res;
}

int main(){
    scanf("%d", &k);
    while(k--){
        scanf("%d %d %lld", &n, &m, &t);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        int st = 0, ed = 0, ans = 0;
        while(ed < n){
            int len = 1;
            while(len){
                //[st, ed)
                if(ed + len <= n && f(st, ed + len) <= t){
                    ed += len;
                    len *= 2;
                }else len /= 2;
            }
            st = ed;
            ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}