线段树求调

_QyGyQ_ @ 2024-01-09 13:59:08

#include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
using ll=long long;
const int N=1e6+7;
int a[N];
struct node{
    int mi,ma;
}tree[N];
void push_up(int p){
    tree[p].mi=min(tree[lc(p)].mi,tree[rc(p)].mi);
    tree[p].ma=max(tree[lc(p)].ma,tree[rc(p)].ma);
}
void build(int p,int pl,int pr){
    if(pl==pr){
        tree[p].mi=tree[p].ma=a[pl];
        return ;
    }
    int mid=pl+pr>>1;
    build(lc(p),pl,mid);
    build(rc(p),mid+1,pr);
    push_up(p);
}
int query_mi(int L,int R,int p,int pl,int pr){
    if(L<=pl&&pr<=R){
        return tree[p].mi;
    }
    int res=1e9;
    int mid=pl+pr>>1;
    if(L<=mid) res=min(res,query_mi(L,R,lc(p),pl,mid));
    if(R>mid) res=min(res,query_mi(L,R,rc(p),mid+1,pr));
    return res;
}
int query_ma(int L,int R,int p,int pl,int pr){
    if(L<=pl&&pr<=R){
        return tree[p].ma;
    }
    int res=0;
    int mid=pl+pr>>1;
    if(L<=mid) res=max(res,query_ma(L,R,lc(p),pl,mid));
    if(R>mid) res=max(res,query_ma(L,R,rc(p),mid+1,pr));
    return res;
}
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1,j=k;j<=n;i++,j++){
        cout<<query_mi(i,j,1,1,n)<<" ";
    }
    puts("");
    for(int i=1,j=k;j<=n;i++,j++){
        cout<<query_ma(i,j,1,1,n)<<" ";
    }
    return 0;
}

by call_of_silence @ 2024-01-09 14:40:45

还有你的最大值输不出来负数

@meng_cen

hack

5 2
-1 -2 -3 -4 -5

by call_of_silence @ 2024-01-09 14:41:21

@meng_cen 线段树开四倍空间

by call_of_silence @ 2024-01-09 14:42:15

@meng_cen 查询最大值的时候res设为极小值

by liu13752 @ 2024-01-09 15:21:42

@meng_cen @meng_cen @meng_cen @meng_cen @meng_cen @meng_cen

by _QyGyQ_ @ 2024-01-12 19:57:44

谢谢大佬! @call_of_silence @liu13275375663

by call_of_silence @ 2024-01-12 20:00:19

@meng_cen

#include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
using ll=long long;
const int N=1e6+7;
int a[N];
struct node{
    int mi,ma;
}tree[N<<2];
void push_up(int p){
    tree[p].mi=min(tree[lc(p)].mi,tree[rc(p)].mi);
    tree[p].ma=max(tree[lc(p)].ma,tree[rc(p)].ma);
}
void build(int p,int pl,int pr){
    if(pl==pr){
        tree[p].mi=tree[p].ma=a[pl];
        return ;
    }
    int mid=pl+pr>>1;
    build(lc(p),pl,mid);
    build(rc(p),mid+1,pr);
    push_up(p);
}
int query_mi(int L,int R,int p,int pl,int pr){
    if(L<=pl&&pr<=R){
        return tree[p].mi;
    }
    int res=1e9;
    int mid=pl+pr>>1;
    if(L<=mid) res=min(res,query_mi(L,R,lc(p),pl,mid));
    if(R>mid) res=min(res,query_mi(L,R,rc(p),mid+1,pr));
    return res;
}
int query_ma(int L,int R,int p,int pl,int pr){
    if(L<=pl&&pr<=R){
        return tree[p].ma;
    }
    int res=-1e9;
    int mid=pl+pr>>1;
    if(L<=mid) res=max(res,query_ma(L,R,lc(p),pl,mid));
    if(R>mid) res=max(res,query_ma(L,R,rc(p),mid+1,pr));
    return res;
}
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1,j=k;j<=n;i++,j++){
        cout<<query_mi(i,j,1,1,n)<<" ";
    }
    puts("");
    for(int i=1,j=k;j<=n;i++,j++){
        cout<<query_ma(i,j,1,1,n)<<" ";
    }
    return 0;
}

我在你源代码上改的