【玄关】线段树玄学问题求调

mysterys @ 2024-02-17 18:44:27

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2*1E6;
int n,m;
int a[MAXN];
struct node{
    int minn,l,r;
}tree[MAXN*4];
void build(int u,int l,int r){
    tree[u].l=l;
    tree[u].r=r;
    if(l==r){
        tree[u].minn=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(u*2,l,m);
    build(u*2+1,m+1,r);
    tree[u].minn=min(tree[u*2].minn,tree[u*2+1].minn);
}
int query(int u,int l,int r){
    if(tree[u].l>=l&&tree[u].r<=r){
        return tree[u].minn;
    }
    int m=(tree[u].l+tree[u].r)>>1;
    int ans=0x7fffffff;
    if(l<=m){
        ans=min(query(u*2,l,r),ans);
    }
    if(r>m){
        ans=min(query(u*2+1,l,r),ans);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=n;i++){
        int x_x=i-m,y_y=i-1;
        if(x_x<=0) x_x=1;
        if(x_x>y_y){
            cout<<0<<'\n';
            continue;
        }
        cout<<query(1,x_x,y_y)<<'\n';
    }
    return 0;
}

by NO_OI_NO_LIFE @ 2024-02-17 19:00:11

@mysterys O2可过

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000006
using namespace std;

int n,m;
int a[MAXN];
struct node{
    int minn,l,r;
}tree[MAXN<<2];
void build(int u,int l,int r){
    tree[u].l=l;
    tree[u].r=r;
    if(l==r){
        tree[u].minn=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(u<<1,l,m);
    build(u<<1|1,m+1,r);
    tree[u].minn=min(tree[u<<1].minn,tree[u<<1|1].minn);
}
int query(int u,int l,int r){
    if(tree[u].l>=l&&tree[u].r<=r){
        return tree[u].minn;
    }
    int m=(tree[u].l+tree[u].r)>>1;
    int ans=1e9;
    if(l<=m){
        ans=min(query(u<<1,l,r),ans);
    }
    if(r>m){
        ans=min(query(u<<1|1,l,r),ans);
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=n;i++){
        int x_x=i-m,y_y=i-1;
        if(x_x<=0) x_x=1;
        if(x_x>y_y){
            printf("0\n");
            continue;
        }
        printf("%lld\n",query(1,x_x,y_y));
    }
    return 0;
}

by NO_OI_NO_LIFE @ 2024-02-17 19:01:19

@mysterys 线段树固然重要，但在考场上，能用单调队列，就用单调队列，因为线段树相比慢