P2251 质量检测
线段树
#include <bits/stdc++.h>
#define ls ( rt<<1 )
#define rs ( rt<<1|1 )
#define Mid ( T[rt].l + T[rt].r >> 1 )
#define L ( T[rt].l )
#define R ( T[rt].r )
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
const int N = 1e6+10;
struct Node
{
int l,r;
int mi;
}T[N];
int a[N];
void push_up(int rt)
{
T[rt].mi = min( T[ls].mi , T[rs].mi );
}
void build(int rt,int l,int r)
{
T[rt] = {l,r,0};
if(l == r){
T[rt].mi = a[l];
return ;
}
build( ls,l,Mid),build(rs,Mid+1,r);
push_up(rt);
}
int query(int rt,int l,int r)
{
if( l <= L && r >= R ){
return T[rt].mi;
}
int al = inf,ar = inf;
if( l <= Mid ) al = query(ls,l,r);
if( r > Mid ) ar = query(rs,l,r);
return min(al,ar);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
build(1,1,n);
for(int i = 1 ; i + m - 1<= n ; i++){
printf("%d
",query(1,i,i+m-1) );
}
}
ST表
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e6+10;
int a[N][21];
inline void pre()
{
for(int j = 1; j <= 21; j ++)
for(int i = 1; i + (1<<j) - 1 <= n ; i++)
a[i][j] = min( a[i][j-1],a[ i + (1 << (j-1)) ][j-1] );
}
inline int query(int l,int r)
{
int k = log2(r-l+1);
return min( a[l][k], a[ r-(1<<k) + 1 ][k] );
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n ; i++) scanf("%d",&a[i]);
pre();
for(int i = 1 ; i + m - 1<= n ; i++){
printf("%d
",query(i,i+m-1) );
}
return 0;
}
分块
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int mi[N];
int a[N];
int id[N];
int n,m,block;
int query(int l,int r)
{
int sid = id[l],eid = id[r];
int ans = 0x3f3f3f3f;
if( sid == eid ){
for(int i = l; i <= r; i++) ans = min(ans, a[i] );
return ans;
}
for(int i = l ; id[i] == sid ; i++) ans = min(ans,a[i]);
for(int i = sid + 1; i < eid ; i++) ans = min(ans,mi[i]);
for(int i = (eid-1)*block + 1 ; i <=r ; i++ ) ans = min(ans,a[i]);
return ans ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m ;
block = sqrt(n);
int len = (n-1)/block +1 ;
for(int i = 1 ; i <= len; i ++){
mi[i] = 0x3f3f3f3f;
}
for(int i = 1; i <= n ; i++){
cin >> a[i];
id[i] = ( i - 1 ) / block + 1;
mi[ id[i] ] = min( mi[id[i]] , a[i] );
}
for(int i = 1; i + m - 1 <= n; i ++){
cout <<query(i,i+m-1) << endl;
}
return 0;
}