【题解】Luogu P1816 【忠诚】

五分钟背板宣告失败,仍然打$RE$,原因:建树,建错树了,,,

这里也就是线段树维护区间最小值,也不用打修改操作。

#include<cstdio>

const int MAXN = 100000 + 6;
int a[MAXN];

class SegmentTree{
    public:int l,r;
    public:int min;
};
SegmentTree t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}
inline int min(int a,int b){return a < b ? a : b;}

void maintain(int p){
    t[p].min = min(t[LEFT(p)].min,t[RIGHT(p)].min);
}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].min = a[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    maintain(p);
}

void change(){}

int ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].min;
    }
    int ans = 0x7fffffff;
    if(l <= MID(t[p].l,t[p].r)){
        ans = min(ans,ask(LEFT(p),l,r));
    }
    if(r > MID(t[p].l,t[p].r)){
        ans = min(ans,ask(RIGHT(p),l,r));
    }
    return ans;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
    }
    
    build(1,1,n);
    
    int ll,rr;
    while(m--){
        scanf("%d %d",&ll,&rr);
        printf("%d ",ask(1,ll,rr));
    }
        
    return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注