头像

总分没有751不换名字


访客:514

离线:3天前


新鲜事 原文

老师叫写题解三部曲 1.写 2.给老师看 3.交到ACWING


新鲜事 原文

新鲜事是今天上了新鲜事功能,然后我发了个新鲜事
图片


分享 浅谈trie




传送门

#include<bits/stdc++.h>
#define N 1000100
#define logN 20
#define INF 0x3f3f3f
using namespace std;
int st_min[N][logN],st_max[N][logN];
int n,m;
inline void pre( ){
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>st_min[i][0];
        st_max[i][0]=st_min[i][0];
    }
}
inline void ST( ){
    int i,j;
    for(i=1;i<=n;i++)
    for(j=1;i+(1<<j)-1<=n;j++){
        st_min[i][j]=min(st_min[i][j-1],st_min[i+(1<<j-1)][j-1]);
        st_max[i][j]=max(st_max[i][j-1],st_max[i+(1<<j-1)][j-1]);
    }
}
inline int que_min(int l,int r){
    int k=log2(r-l+1);
    return min(st_min[l][k],st_min[r-(1<<k)+1][k]);
}
inline int que_max(int l,int r){
    int k=log2(r-l+1);
    return max(st_max[l][k],st_max[r-(1<<k)+1][k]);
}
inline void work( ){
    int i;
    for(i=1;i+m-1<=n;i++)cout<<que_min(i,i+m-1)<<" ";
    puts("");
    for(i=1;i+m-1<=n;i++)cout<<que_max(i,i+m-1)<<" ";
}
int main( ){
    pre( );
    ST( );
    work( );
}