数据结构小板子

板子（大体按代码长度排序）

ST表

板子题传送门

预处理部分：

int n,nl[maxn],f[maxn][maxl],lg[maxn];
//nl：原数组
lg[0]=-1;
fru(i,1,n)f[i][0]=nl[i],lg[i]=lg[i>>1]+1;
fru(i,1,lg[n])fru(j,1,n-(1<<i)+1)
f[j][i]=max(f[j][i-1],f[j+(1<<i-1)][i-1]);

干活部分：

max(f[l][lg[r-l+1]],f[r-(1<<lg[r-l+1])+1][lg[r-l+1]])

左偏树

板子题传送门

struct tree
{
    int lc,rc,w,d;
}nl[maxn];
inline bool bgood(int a,int b)
{
    return nl[a].w==nl[b].w?a>b:nl[b].w<nl[a].w;
}
int heap_merge(int x,int y)
{
    if(!x||!y)return x|y;
    if(bgood(x,y))mswap(x,y);
    nl[x].lc=heap_merge(nl[x].lc,y);
    if(nl[nl[x].lc].d<nl[nl[x].rc].d)mswap(nl[x].lc,nl[x].rc);
    nl[x].d=nl[nl[x].rc].d+1;
    return x;
}

树状数组

单点加以及求前缀和。

int nl[maxn],k,a,b;
int n,m;
void upd(int a,int b)
{
    for(;a<=n;a+=a&(-a))
    {
        nl[a]+=b;
    }
    return ;
}
int getas(int x)
{
    int ans=0;
    for(;x>=1;x-=x&(-x))
    {
        ans+=nl[x];
    }
    return ans;
}

线段树

基本模板

乘和加。

int n,m,nl[maxn];
ll mod;
ll tre[maxn<<2],add[maxn<<2],pro[maxn<<2];
void build(int k,int l,int r)
{
    pro[k]=1;
    if(l==r)
    {
        tre[k]=nl[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tre[k]=(tre[k<<1]+tre[k<<1|1])%mod;
}
inline void up(int dc,int k,ll lin,ll x)
{
    if(dc==1)
    {
        (tre[k]+=x*lin)%=mod;
        (add[k]+=x)%=mod;
    }
    else
    {
        (tre[k]*=x)%=mod;
        (add[k]*=x)%=mod;
        (pro[k]*=x)%=mod;
    }
}
inline void pushdown(int k,int l,int r,int mid)
{
    if(pro[k]^1)
    {
        up(2,k<<1,mid-l+1,pro[k]);
        up(2,k<<1|1,r-mid,pro[k]);
        pro[k]=1;
    }
    if(add[k]^0)
    {
        up(1,k<<1,mid-l+1,add[k]);
        up(1,k<<1|1,r-mid,add[k]);
        add[k]=0;
    }
}
int dcl,dcr;
ll num;
void update(int dc,int k,int l,int r)
{
    if(dcr<l||r<dcl)return ;
    if(dcl<=l&&r<=dcr)
    {
        up(dc,k,r-l+1,num);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r,mid);
    update(dc,k<<1,l,mid);
    update(dc,k<<1|1,mid+1,r);
    tre[k]=tre[k<<1]+tre[k<<1|1];
}
ll getans(int k,int l,int r)
{
    if(dcr<l||r<dcl)return 0;
    if(dcl<=l&&r<=dcr)
    {
        return tre[k];
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r,mid);
    return (getans(k<<1,l,mid)+getans(k<<1|1,mid+1,r))%mod;
}

终极模板

P6242 【模板】线段树 3的 AC 代码（可能是我写过最长的 AC 代码）

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define pc(x) putchar(x)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = long long;
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
const int maxn=500012;const int inf=(int)1e9;
int n,m,nl[maxn];
int Tp,Wl,Wr,W;
struct node
{
    int l,r;ll sum;int mxn,mxh,sm,cnt,tm,tmh,te,teh;
}tl[maxn<<2];//sum:sum mxn:maxn mxh:history_mxn sm:second_maxn 
inline void pushup(int k)
{
    tl[k].sum=tl[k<<1].sum+tl[k<<1|1].sum;
    tl[k].mxn=max(tl[k<<1].mxn,tl[k<<1|1].mxn);tl[k].mxh=max(tl[k<<1].mxh,tl[k<<1|1].mxh);
    if(tl[k<<1].sm>=tl[k<<1|1].mxn)
    {
        tl[k].mxn=tl[k<<1].mxn;tl[k].cnt=tl[k<<1].cnt;
        tl[k].sm=tl[k<<1].sm;
    }
    else if(tl[k<<1|1].sm>=tl[k<<1].mxn)
    {
        tl[k].mxn=tl[k<<1|1].mxn;tl[k].cnt=tl[k<<1|1].cnt;
        tl[k].sm=tl[k<<1|1].sm;
    }
    else
    {
        tl[k].mxn=max(tl[k<<1].mxn,tl[k<<1|1].mxn);
        if(tl[k<<1].mxn==tl[k<<1|1].mxn)
        {
            tl[k].sm=max(tl[k<<1].sm,tl[k<<1|1].sm);tl[k].cnt=tl[k<<1].cnt+tl[k<<1|1].cnt;
        }
        else
        {
            if(tl[k<<1].mxn<tl[k<<1|1].mxn)
            {
                tl[k].sm=tl[k<<1].mxn;
                tl[k].cnt=tl[k<<1|1].cnt;
            }
            else 
            {
                tl[k].sm=tl[k<<1|1].mxn;
                tl[k].cnt=tl[k<<1].cnt;
            }
        }
    }
}
inline void upmx(int k,int w,int wm)
{
    tl[k].tmh=max(tl[k].tmh,tl[k].tm+wm);
    tl[k].tm+=w;
    tl[k].sum+=(ll)w*(ll)tl[k].cnt;
    tl[k].mxh=max(tl[k].mxh,tl[k].mxn+wm);
    tl[k].mxn+=w;
}
inline void upe(int k,int w,int wm)
{
    tl[k].teh=max(tl[k].teh,tl[k].te+wm);
    tl[k].te+=w;
    tl[k].sum+=(ll)(tl[k].r-tl[k].l+1-tl[k].cnt)*(ll)w;
    tl[k].sm+=w;
}
inline void pushdown(int k)
{
    int lmx=tl[k<<1].mxn,rmx=tl[k<<1|1].mxn;
    if(tl[k].tm||tl[k].tm!=-inf)
    {
        if(lmx>rmx)upmx(k<<1,tl[k].tm,tl[k].tmh);
        else if(lmx<rmx)upmx(k<<1|1,tl[k].tm,tl[k].tmh);
        else {upmx(k<<1,tl[k].tm,tl[k].tmh);upmx(k<<1|1,tl[k].tm,tl[k].tmh);}
        tl[k].tm=0;tl[k].tmh=-inf;
    }
    if(tl[k].te||tl[k].teh!=-inf)
    {
        upe(k<<1,tl[k].te,tl[k].teh);upe(k<<1|1,tl[k].te,tl[k].teh);
        if(lmx>rmx)
        {
            upmx(k<<1|1,tl[k].te,tl[k].teh);
        }
        else if(lmx<rmx)
        {
            upmx(k<<1,tl[k].te,tl[k].teh);
        }
        tl[k].te=0;tl[k].teh=-inf;
    }
}
void upmin(int k)
{
    if(W>=tl[k].mxn)return ;
    if(W>tl[k].sm)
    {
        upmx(k,W-tl[k].mxn,W-tl[k].mxn);
        return ;
    }
    pushdown(k);
    upmin(k<<1);upmin(k<<1|1);
    pushup(k);
}
void build(int k,int l,int r)
{
    if(l>r)return ;
    if(l==r)
    {
        tl[k]=(node){l,r,nl[l]  ,nl[l],nl[l]  ,-inf,1  ,0,-inf,0,-inf};
        return ;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    tl[k].l=l;tl[k].r=r;
    pushup(k);
}
void upd(int k)
{
    if(tl[k].r<Wl||Wr<tl[k].l)return ;
    if(Wl<=tl[k].l&&tl[k].r<=Wr)
    {
        if(Tp==1)upe(k,W,W),upmx(k,W,W);
        else upmin(k);
        return ;
    }
    pushdown(k);
    upd(k<<1);upd(k<<1|1);
    pushup(k);
}
ll qry(int k)
{
    // cout<<tl[k].l<<' '<<tl[k].r<<' '<<tl[k].sum<<' '<<tl[k].mxn<<' '<<tl[k].mxh<<' '<<tl[k].sm<<' '<<tl[k].cnt<<' '<<tl[k].tm<<' '<<tl[k].tmh<<' '<<tl[k].te<<' '<<tl[k].teh<<endl;
    if(tl[k].r<Wl||Wr<tl[k].l)
    {
        if(Tp==3)return 0;
        else if(Tp==4)return -inf;
        else return -inf;
    }
    if(Wl<=tl[k].l&&tl[k].r<=Wr)
    {
        if(Tp==3)return tl[k].sum;
        else if(Tp==4)return tl[k].mxn;
        else return tl[k].mxh;
    }
    pushdown(k);
    if(Tp==3)return qry(k<<1)+qry(k<<1|1);
    else if(Tp==4)return max(qry(k<<1),qry(k<<1|1));
    else return max(qry(k<<1),qry(k<<1|1));
}
int main()
{
    // fio();
    n=in();m=in();
    fru(i,1,n)
    {
        nl[i]=in();
    }
    build(1,1,n);
    // int tot=0;
    while(m--)
    {
        Tp=in();
        if(Tp<3)
        {
            Wl=in();Wr=in();W=in();
            upd(1);
        }
        else
        {
            Wl=in();Wr=in();
            // if((++tot)==1340)
            // {
            // 	cerr<<Tp<<' '<<Wl<<' '<<Wr;
            // }
            printf("%lld\n",qry(1));
        }
    }
    return 0;
}

李超线段树

因为作者比较懒，就先放了板子题的代码。

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = double;using pii = pair<int,double>;
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
const int maxn=100012,m=39989;const double eps=1e-9;
int n,tre[maxn<<2],td;ll t1,t2,t3,t4;
struct ln
{
    double k,b;
    double gp(int x)
    {
        // cout<<endl<<"gp"<<x<<' '<<x*k+b<<endl;
        return x*k+b;
    }
}nl[maxn];
inline short int cmp(double x,double y){if(x>y+eps)return -1;else if(y>x+eps)return 1;return 0;}
void upd(int k,int l,int r,int tn)
{
    int mid=(l+r)>>1;
    short int b1=cmp(nl[tre[k]].gp(mid),nl[tn].gp(mid)),b2;
    if(b1==1||(!b1&&tn<tre[k]))swap(tre[k],tn);
    b1=cmp(nl[tre[k]].gp(l),nl[tn].gp(l));b2=cmp(nl[tre[k]].gp(r),nl[tn].gp(r));
    if(b1==1||(!b1&&tn<tre[k]))upd(k<<1,l,mid,tn);
    if(b2==1||(!b2&&tn<tre[k]))upd(k<<1|1,mid+1,r,tn);
    // cout<<k<<' '<<l<<' '<<r<<' '<<tre[k]<<endl;
}
void fd(int k,int l,int r)
{
    if(r<t1||t3<l)return ;
    if(t1<=l&&r<=t3)
    {
        upd(k,l,r,td);
        return ;
    }
    int mid=(l+r)>>1;
    fd(k<<1,l,mid);fd(k<<1|1,mid+1,r);
}
inline pii pmax(pii la,pii ra)
{
    if(fabs(la.second-ra.second)<=eps)return la.first<ra.first?la:ra;
    else return la.second>ra.second?la:ra;
}
pii qry(int k,int l,int r)
{
    if(t1<l||r<t1)return make_pair(0,0); 
    if(l==t1&&l==r)return make_pair(tre[k],nl[tre[k]].gp(l));
    int mid=(l+r)>>1;
    pii la=qry(k<<1,l,mid),ra=qry(k<<1|1,mid+1,r);
    return pmax(pmax(la,ra),make_pair(tre[k],nl[tre[k]].gp(t1)));
}
int main()
{
    n=in();
    int op,la=0;
    while(n--)
    {
        op=in();
        if(!op)
        {
            t1=(la+in()-1)%m+1;
            printf("%d\n",la=qry(1,1,m).first);
        }
        else
        {
            t1=(in()+la-1)%m+1;t2=(in()+la-1)%1000000000+1;t3=(in()+la-1)%m+1;t4=(in()+la-1)%1000000000+1;
            if(t1>t3)
            {
                swap(t1,t3);swap(t2,t4);
            }
            if(t1==t3)nl[++td]=(ln){0,max(t2,t4)*1.0};
            else nl[++td]=(ln){(t2-t4)/(1.0*(t1-t3)),(t4*t1-t2*t3)/(1.0*(t1-t3))};
            // cout<<t1<<' '<<t2<<' '<<t3<<' '<<t4<<' '<<td<<' '<<nl[td].k<<' '<<nl[td].b<<endl;
            fd(1,1,m);
        }
    }
    return 0;
}

吉司机线段树（segment tree beats）

论文复杂度看不懂，网络上又没有浅显易懂的证明，只好咕咕咕

这里用到了吉司机线段树的思想