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;
}
