最近拿到了学校一个icpc区域赛的名额，新学点东西同时准备一下第一次icpc的竞赛w

Segment Tree Beats简介

有这样一类区间问题，需要维护

  • 区间 $[l,r]$ 的 $a_i$对$t$ 取min (max)
  • 区间加
  • 区间求max

其中有一个特点是有区间最值操作

我们虽然可以用分块在$O(n \sqrt n)$的复杂度内解决，但是我们可以用线段树在更快的$O(nlogn)$的复杂度内解决

这一算法叫做Segment Tree Beats，由吉老师在2016年国家集训队论文中最先提出，故也被称为吉司机线段树

Segment Tree Beats 思路

其他操作和普通线段树一样，现在主要介绍区间最值操作

假设我们要对$t$取min

我们需要维护区间最大值$mx$，区间次大值$sc$，区间最大值个数$mc$

  1. 当$mx\leq t$时，$t$显然没有意义，直接退出
  2. 当$sc<t<mx$时，用$t$更新当前区间最大值和区间和，同时打一个标记
  3. 当$t\leq sc$时，继续向下暴力递归

这样我们就完成了区间最值的操作，可以证明复杂度是$O(mlogn)$的，具体证明见论文。

例题

hdu5306 Gorgeous Sequence

sgtb裸题

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 1000005
#define ls(x) x<<1
#define rs(x) x<<1|1
#define getchar() (ss==tt&&(tt=(ss=In)+fread(In,1,Max,stdin),ss==tt)?EOF:*ss++)
#define dg puts("qwq")
using namespace std;
char In[Max],*ss=In,*tt=In;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[Max],n,T,m,tg[Max<<2],mx[Max<<2],mc[Max<<2],sc[Max<<2];
ll t[Max<<2];
il void pushup(int x)
{
    t[x]=t[ls(x)]+t[rs(x)];
    if(mx[ls(x)]>mx[rs(x)])
    {
        mx[x]=mx[ls(x)];
        mc[x]=mc[ls(x)];
        sc[x]=max(sc[ls(x)],mx[rs(x)]);
    }
    if(mx[rs(x)]>mx[ls(x)])
    {
        mx[x]=mx[rs(x)];
        mc[x]=mc[rs(x)];
        sc[x]=max(sc[rs(x)],mx[ls(x)]);
    }
    if(mx[ls(x)]==mx[rs(x)])
    {
        mx[x]=mx[ls(x)];
        mc[x]=mc[ls(x)]+mc[rs(x)];
        sc[x]=max(sc[rs(x)],sc[ls(x)]);
    }
}
il void pushtag(int x,int k)
{
    if(mx[x]<=k) return ;
    t[x]-=1ll*mc[x]*(mx[x]-k);
    mx[x]=k;
    tg[x]=k;
}
il void pushdown(int x)
{
    if(tg[x]==-1) return;
    pushtag(ls(x),tg[x]),pushtag(rs(x),tg[x]);
    tg[x]=-1;
}
il void build(int x,int l,int r)
{
    if(l==r)
    {
        t[x]=a[l];
        tg[x]=-1;
        mx[x]=a[l];
        mc[x]=1;
        sc[x]=-1;
        return ;
    }
    tg[x]=-1;
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    pushup(x);
}
il void mdf(int x,int l,int r,int ql,int qr,int k)
{
    if(mx[x]<=k) return ;
    if(ql<=l&&r<=qr&&sc[x]<k)
    {
        pushtag(x,k);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(x);
    if(ql<=mid) mdf(ls(x),l,mid,ql,qr,k);
    if(qr>mid) mdf(rs(x),mid+1,r,ql,qr,k);
    pushup(x);
}
il int qm(int x,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        return mx[x];
    }
    int mid=(l+r)>>1;
    pushdown(x);
    int res=-1;
    if(ql<=mid) res=qm(ls(x),l,mid,ql,qr);
    if(qr>mid) res=max(res,qm(rs(x),mid+1,r,ql,qr));
    return res;
}
il ll qs(int x,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        return t[x];
    }
    int mid=(l+r)>>1;
    pushdown(x);
    ll res=0;
    if(ql<=mid) res=qs(ls(x),l,mid,ql,qr);
    if(qr>mid) res+=qs(rs(x),mid+1,r,ql,qr);
    return res;
}
signed main()
{
    T=read();
    while(T--)
    {
        n=read(),m=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int opt=read();
            if(opt==0)
            {
                int u=read(),v=read(),t=read();
                mdf(1,1,n,u,v,t);
            }
            if(opt==1)
            {
                int u=read(),v=read();
                printf("%d\n",qm(1,1,n,u,v));
            }
            if(opt==2)
            {
                int u=read(),v=read();
                printf("%lld\n",qs(1,1,n,u,v));
            }
        }
    }
}