前提知识

基本的线段树写法：
洛谷线段树1
洛谷线段树2

以下是正文

一、区间最值操作

例题一、

Gorgeous Sequence

本题要求我们实现三个操作

对于第二种和第三种操作我们是已经知道如何写了。

问题就在于第一种操作。

考虑第一种操作是取min
因此当我们这个区间内的最大值 
1.如果比给定的k来得小 那么我们不需要任何操作
2.如果这个k<最大值 但是k > 第二大的值(以下称为次大值)
那么我们只需要将最大值全部变成k,修改一下区间和即可.
3.如果这个k＜最大值 && k < 次大值 
那么我们当前这个结点是处理不了的,直接push_down交给儿子结点

以下放出完整代码

#include <iostream>
#include <cstring>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
typedef long long ll;
const int N = 1100000;
struct Node{
    int L,R,tag;//这个tag是维护区间最值操作的
    ll sum;
    int fir_big,sec_big;
    int fir_num;
}tree[N*4];
int a[N];
inline void push_up(int);
void build_tree(int l,int r,int p){
    //tag的取值是0~2^31-1 因此我们取-1
    tree[p].L=l,tree[p].R=r,tree[p].tag=-1;
    if(l==r){
        tree[p].sum=a[l];
        tree[p].fir_big=a[l];
        tree[p].sec_big=-1;
        tree[p].fir_num=1;
        return;
    }
    int mid = (l+r)>>1;
    build_tree(l,mid,lc);
    build_tree(mid+1,r,rc);
    push_up(p);
}
inline void push_up(int p){
    tree[p].sum=tree[lc].sum+tree[rc].sum;
    if(tree[lc].fir_big==tree[rc].fir_big){
        tree[p].fir_big=tree[lc].fir_big;
        tree[p].fir_num=tree[lc].fir_num+tree[rc].fir_num;
        tree[p].sec_big=max(tree[lc].sec_big,tree[rc].sec_big);
    }else if(tree[lc].fir_big>tree[rc].fir_big){
        tree[p].fir_big=tree[lc].fir_big;
        tree[p].fir_num=tree[lc].fir_num;
        tree[p].sec_big=max(tree[lc].sec_big,tree[rc].fir_big);
    }else{
        tree[p].fir_big=tree[rc].fir_big;
        tree[p].fir_num=tree[rc].fir_num;
        tree[p].sec_big=max(tree[rc].sec_big,tree[lc].fir_big);
    }
}
inline void update(int p,int cnt_val){
    if(cnt_val<tree[p].fir_big){
        //最大值全部变成cnt_val
        tree[p].sum+=(1ll*cnt_val-tree[p].fir_big)*tree[p].fir_num;
        tree[p].fir_big=tree[p].tag=cnt_val;
    }
}
inline void push_down(int p){
    if(~tree[p].tag){
        update(lc,tree[p].tag);
        update(rc,tree[p].tag);
        tree[p].tag=-1;
    }
}
void modify(int p,int l,int r,int cnt_val){
    if(tree[p].L>r||tree[p].R<l||tree[p].fir_big<=cnt_val) return;
    if(tree[p].L>=l&&tree[p].R<=r&&tree[p].sec_big<cnt_val){
        update(p,cnt_val);
        return;
    }
    push_down(p);
    modify(lc,l,r,cnt_val);
    modify(rc,l,r,cnt_val);
    push_up(p);
}
int queryMax(int p,int l,int r){
    if(tree[p].L>r||tree[p].R<l) return 0;
    if(tree[p].L>=l&&tree[p].R<=r){
        return tree[p].fir_big;
    }
    push_down(p);
    return max(queryMax(lc,l,r),queryMax(rc,l,r));
}
ll querySum(int p,int l,int r){
    if(tree[p].L>r||tree[p].R<l) return 0;
    if(tree[p].L>=l&&tree[p].R<=r){
        return tree[p].sum;
    }
    push_down(p);
    return querySum(lc,l,r)+querySum(rc,l,r);
}
#undef lc
#undef rc
int read(){
	int x=0; char ch=0;
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
	return x;
}
#if 0
这份代码完成三个功能
1.区间最小值操作
2.求区间最大值
3.求区间和
#endif // 0
int main()
{
    int t,n,m;
    t=read();
    while(t--){
        n=read();
        m=read();
        for(int i=1;i<=n;i++){
           a[i]=read();
        }
        build_tree(1,n,1);
        for(int i=1;i<=m;i++){
            int op,x,y,t;
            op=read();
            if(op==0){
                x=read();
                y=read();
                t=read();
                modify(1,x,y,t);
            }else if(op==1){
                x=read();
                y=read();
                printf("%d\n",queryMax(1,x,y));
            }else{
                x=read();
                y=read();
                printf("%lld\n",querySum(1,x,y));
            }
        }
    }
    return 0;
}

例题二、

等待完成ing…