P2251 质量检测
正解应该是ST表和单调队列，不过对于这道题来说只有查询没有修改，这里我还是想用线段树和分块来写，不得不说分块是真好，优雅的暴力
线段树版本：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e6 + 10;
struct SegmentTree{
int l, r;
int minn;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define minn(x) tree[x].minn
}tree[4 * N];
int n, m, a[N];
void build(int p, int l, int r)
{
l(p) = l, r(p) = r;
if(l == r) {minn(p) = a[l]; return;}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
minn(p) = min(minn(p << 1), minn(p << 1 | 1));
}
int ask(int p, int l, int r)
{
if(l <= l(p) && r >= r(p)) return minn(p);
int mid = (l(p) + r(p)) >> 1;
int val = 1e9;
if(l <= mid) val = min(ask(p << 1, l , r), val);
if(r > mid) val = min(ask(p << 1 | 1, l, r), val);
return val;
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
build(1, 1, n);
for(int i = 1; i + m - 1 <= n; ++ i) cout << ask(1, i, i + m - 1) << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
solve();
return 0;
}
分块版本
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e6 + 10;
int a[N], n, m, block[N], ans[N], bl;
int ask(int l, int r)
{
int p = block[l], q = block[r], res = 1e9;
if(p == q) for(int i = p; i <= q; ++ i) res = min(res, a[i]);
else
{
for(int i = p + 1; i <= q - 1; ++ i) res = min(res, ans[i]);
for(int i = l; i <= p * bl; ++ i) res = min(res, a[i]);
for(int i = (q - 1) * bl + 1; i <= r; ++ i) res = min(res, a[i]);
}
return res;
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
bl = sqrt(n);
memset(ans, 0x3f, sizeof ans);
for(int i = 1; i <= n; ++ i)
{
block[i] = (i - 1) / bl + 1;
ans[block[i]] = min(ans[block[i]], a[i]);
}
for(int i = 1; i + m - 1 <= n; ++ i) cout << ask(i, i + m - 1) << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
solve();
return 0;
}