GorgeousSequence（吉老师线段树）xiaodangao

题目链接：Gorgeous Sequence
思路：本题用普通线段树完成不了将区间内的大于k的数都等于k的操作，但吉老师线段树可以。我们需要维护的东西有：最大值，次大值，最大值的数量，区间和。对于每一次$modify$操作，我们分类讨论（为了讨论方便，我们将当前修改的值设为k，当前区间最大值设为ma，当前次大值设为se，当前最大值数量设为cnt）：
1.$ma \leq k$这时候我们不需要修改当前最大值。
2.$se < k < ma$这时候我们需要将当前最大值修改为k并且更新区间和。
3.$k \leq se$这时候该区间我们无法进行处理，须向下更新子节点。
然后再说细节，在碰到第2类情况时，修改当前最大值就相当于修改懒标记，因为我们下传懒标记的过程就是判断儿子节点的最大值是否大于父亲节点最大值，如果大于，那么修改一下儿子节点最大值。（父亲节点都懒标记了，那么儿子节点就一定不会出现情况3）
（如果第一次写，发现代码会很啰嗦
$Code:$

/* -*- encoding: utf-8 -*-
'''
@File    :   HDU5306.cpp
@Time    :   2021/06/16 16:36:35
@Author  :   puddle_jumper 
@Version :   1.0
@Contact :   1194446133@qq.com
'''

# here put the import lib*/
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#define ch() getchar()
#define pc(x) putchar(x)
#include<stack>
#include<unordered_map>
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define PI acos(-1)
using namespace std;
template<typename T>void read(T&x){
    static char c;
    static int f;
    for(c=ch(),f=1; c<'0'||c>'9'; c=ch())if(c=='-')f=-f;
    for(x=0; c>='0'&&c<='9'; c=ch())x=x*10+(c&15);
    x*=f;
}
template<typename T>void write(T x){
    static char q[65];
    int cnt=0;
    if(x<0)pc('-'),x=-x;
    q[++cnt]=x%10,x/=10;
    while(x)
    q[++cnt]=x%10,x/=10;
    while(cnt)pc(q[cnt--]+'0');
}
const int N = 1e6+10;
 
int a[N],n,m,_;
struct node{
    int l,r,ma,se,cnt;
    ll sum;
}tr[N<<2];
inline void up(int x){
    tr[x].sum = tr[x<<1].sum + tr[x<<1|1].sum;
    tr[x].ma = max(tr[x<<1].ma,tr[x<<1|1].ma);
    if(tr[x<<1].ma == tr[x<<1|1].ma){
        tr[x].cnt = tr[x<<1].cnt + tr[x<<1|1].cnt;
        tr[x].se = max(tr[x<<1].se,tr[x<<1|1].se);
    } else if (tr[x<<1].ma > tr[x<<1|1].ma) tr[x].cnt = tr[x<<1].cnt,tr[x].se = max(tr[x<<1].se,tr[x<<1|1].ma);
    else tr[x].cnt = tr[x<<1|1].cnt,tr[x].se = max(tr[x<<1|1].se,tr[x<<1].ma);
}
inline void down(int p){
    if(tr[p].l == tr[p].r) return ;
    if(tr[p<<1].ma > tr[p].ma){
        tr[p<<1].sum -= 1ll*(tr[p<<1].ma - tr[p].ma)*tr[p<<1].cnt;
        tr[p<<1].ma = tr[p].ma;
    }
    if(tr[p<<1|1].ma > tr[p].ma){
        tr[p<<1|1].sum -= 1ll*(tr[p<<1|1].ma - tr[p].ma)*tr[p<<1|1].cnt;
        tr[p<<1|1].ma = tr[p].ma;
    }
}
void modify(int l,int r,int p,int k){
    if(tr[p].ma <= k)return;
    int mid = tr[p].l + tr[p].r >> 1;
    down(p);
    if(l<=tr[p].l and tr[p].r<=r){
        if(tr[p].ma> k and tr[p].se < k){
            tr[p].sum -= 1ll*(tr[p].ma-k)*tr[p].cnt;
            tr[p].ma = k;
            return ;
        }else {
            modify(l,r,p<<1,k);
            modify(l,r,p<<1|1,k);
            //up(p);
        }
    } else {
        if(l<=mid)modify(l,r,p<<1,k);
        if(r>mid)modify(l,r,p<<1|1,k);
    }
    up(p);
}
int query1(int l,int r,int p){
    int mid = tr[p].l + tr[p].r >> 1;
    if(tr[p].l >= l and tr[p].r <= r)return tr[p].ma;
    int ans = -1;down(p);
    if(mid >= l)ans = max(ans,query1(l,r,p<<1));
    if(r > mid)ans = max(ans,query1(l,r,p<<1|1));
    //up(p);
    return ans ;
}
ll query2(int l,int r,int p){
    int mid = tr[p].l + tr[p].r >> 1;
    if(l<=tr[p].l and tr[p].r <= r)return tr[p].sum;
    ll ans = 0;down(p);
    if(mid >= l)ans = query2(l,r,p<<1);
    if(r > mid) ans += query2(l,r,p<<1|1);
    //up(p);
    return ans;
}
void build(int l,int r,int p){
    int mid = l + r>>1;
    if(l == r){
        tr[p] = {l,l,a[l],-1,1,a[l]*1ll};
        return ;
    } 
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    tr[p] = {l,r};
    up(p);
}
inline void solve(){
    
    read(_);
    while(_--){
        read(n);read(m);
        rep(i,1,n){
            read(a[i]);
        }
        build(1,n,1);
        while(m--){
            int x,y,t,op;
            read(op);
            if(op == 0){
                read(x);read(y);read(t);
                modify(x,y,1,t);
                continue;
            }else if(op == 1){
                read(x);read(y);
                write(query1(x,y,1));
            }else {
                read(x);read(y);
                write(query2(x,y,1));
            }
            pc('\n');
        }
    }
}



signed main(){solve();return 0; }

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章