C++的代码

以下是C++的完整代码：

竞赛树的代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int n,m;
int a[maxn];
int tree[maxn<<1];

void build_tree(){
    for(int i=n;i<2*n;i++){
        tree[i]=i-n;
    }
    for(int i=n-1;i;i--){
        tree[i]=a[tree[i<<1]]<a[tree[i<<1|1]]?tree[i<<1]:tree[i<<1|1];
    }
}

int query(int l,int r){
    int ans=0x7f7f7f7f;
    for(l=l-1+n,r=r+1+n;l^r^1;l>>=1,r>>=1){
        if(~l&1) ans=min(ans,a[tree[l^1]]);
        if(r&1) ans=min(ans,a[tree[r^1]]);
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    build_tree();
    scanf("%d",&m);
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }
    return 0;
}

赢者树的代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int n,m;
int a[maxn];
int tree[maxn];

void build_tree(){
    for(int i=n;i<2*n;i++){
        tree[i]=i-n;
    }
    for(int i=n-1;i;i--){
        tree[i]=a[tree[i<<1]]<a[tree[i<<1|1]]?tree[i<<1]:tree[i<<1|1];
    }
}

void update(int i){
    i+=n;
    while(i){
        int j=i^1;
        tree[i]=a[tree[i]]<a[tree[j]]?tree[i]:tree[j];
        i>>=1;
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    build_tree();
    scanf("%d",&m);
    while(m--){
        int op,x,y;
        scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d",&y);
            a[x]=y;
            update(x);
        }
        else printf("%d\n",tree[1]);
    }
    return 0;
}