线段树变式+维护区间前8大的值

解题思路:线段树是很常见的数据结构，不会的同学可以自行百度学习。首先题意有两种操作，一个是修改值，一个是查询区间[a,b]的第8大的值。

我们使用线段树结构，每个节点存储这个区间的前八位的值，这里不用建树，大家都是0。关键就是怎么让孩子节点的值传递到父节点，这里其实就是归并排序，在左孩子和右孩子各自的8个值里，使用两个指针依次选更大的值。这里一般使用重载结构体的运算符实现。

注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long 
 
#define dou double 
const int N = 1e5 + 15;
const int D=998244353; 
int ans;
 
struct tr{
    int a[8];
    tr operator +(const tr& rt)const{//重载 + 
        tr res; int p=0,q=0;
        for(int i=0;i<8;i++){//归并排序 
            res.a[i]=a[p]>rt.a[q]?a[p++]:rt.a[q++];
        }
        return res;
    }
}t[4*N];
 
void push_up(int p){//更新父节点 
    t[p]=t[p * 2] + t[p * 2 + 1]; // 根据子节点更新当前节点的值
}
void update(int l,int r,int p,int d,int cl,int cr){
    if(cl>=l&&cr<=r){//当前区间全部被包含目标区间里面 
        t[p].a[0]=d;
    }else if(cl>r||cr<l){//区间不相交 
        return ;
    }else{
        int mid=(cl+cr)/2;
        update(l,r,2*p,d,cl,mid);update(l,r,2*p+1,d,mid+1,cr);
        push_up(p);
    }
}
 
tr query(int l,int r,int p,int cl,int cr){
    if(cl>=l&&cr<=r){
        return t[p];
    }else if(cl>r||cr<l){
        tr t1; 
        //for(int i=0;i<8;i++) t1.a[i]=0;
        return t1;
    }else{
        int mid=(cl+cr)/2;
        return query(l,r,2*p,cl,mid)+query(l,r,2*p+1,mid+1,cr);
    }  
}
 
signed main(){
    int L,T,a,b,p,x;
    char op;
    cin>>L>>T;
     
    while(T--){
        scanf(" %c",&op);
        if(op=='C'){
            scanf("%lld%lld",&p,&x); 
            update(p,p,1,x,1,L);
        }else{
            scanf("%lld%lld",&a,&b);
            cout<<query(a,b,1,1,L).a[7]<<endl;
        }
         
    }
    return 0;
}