板子(大体按代码长度排序)

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)

贺自OIWIKI,源地址可点击查看

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

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