解析

线段数，每个节点是一个vecotor，记录区间最大的8个数。
然后修改查询的操作和普通线段书一样，区间合并就是合并两个有序vector。
时间复杂度：$O(8*nlogn)$

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
const int N=100010;
vector<int> v[N<<2];
void push_up(vector<int> &vu,const  vector<int>& vl,const vector<int>& vr) {
    int i=0,j=0,k=0;
    while(k<8) {
        if(vl[i]>vr[j]) vu[k++]=vl[i++];
        else vu[k++]=vr[j++];
    }
}
void build(int u,int l,int r) {
    v[u].resize(8,0);
    if(l==r) return ;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    return ;
}
void modify(int u,int l,int r,int p,int w) {
    if(l==r) {
        v[u][0]=w;
    }
    else {
        int mid=l+r>>1;
        if(p<=mid) modify(u<<1,l,mid,p,w);
        if(mid<p) modify(u<<1|1,mid+1,r,p,w);
        push_up(v[u],v[u<<1],v[u<<1|1]);
    }
}
vector<int> query(int u,int l,int r,int ll,int rr) {
    if(ll<=l&&r<=rr) return v[u];
    else {
        int mid=l+r>>1;
        int i=0,j=0;
        if(rr<=mid) return query(u<<1,l,mid,ll,rr);
        if(mid<ll) return query(u<<1|1,mid+1,r,ll,rr);
        else {
            vector<int> tmp(8,0);
            push_up(tmp,query(u<<1,l,mid,ll,rr),query(u<<1|1,mid+1,r,ll,rr));
            return tmp;
        }
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    build(1,1,n);
    char opt[2];
    int a,b;
    while(m--) {
        scanf("%s%d%d",opt,&a,&b);
        if(*opt=='C') {
            modify(1,1,n,a,b);
        } 
        else {
            vector<int> re=query(1,1,n,a,b);
            printf("%d\n",re.back());
        }
    }
    return 0;
}