rt，数据结构模板，主要是用来保存，需要的也可以拿去用αωα
ST表（区间最大值模板）：
#include
using namespace std;
const int N=1e5*2+10,M=18;
int w[N],f[N][M],n,m;
void init()
{
for(int j=0;
j 单调队列模板：
#include
using namespace std;
const int N=1000010;
int a[N],q[N];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;
iq[hh]) hh++;
while(hh<=tt and a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) printf("%d ",a[q[hh]]);
}
printf("\n");
hh=0,tt=-1;
for(int i=0;
iq[hh]) hh++;
while(hh<=tt and a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) printf("%d ",a[q[hh]]);
}
return 0;
}
//题目链接：https://www.acwing.com/problem/content/description/156//************************************************/
#include
using namespace std;
const int N=300010,INF=1e9;
int n,m;
int s[N],q[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;
i<=n;
i++) scanf("%d",&s[i]),s[i]+=s[i-1];
int res=-INF;
int hh=0,tt=0;
for(int i=1;
i<=n;
i++)
{
if(q[hh]=s[i]) tt--;
q[++tt]=i;
}
printf("%d",res);
return 0;
}
//题目链接：https://www.acwing.com/problem/content/description/137/
树状数组模板：1 ，2
线段树模板：
（线段树2模板，洛谷P3373 ）
#include
using namespace std;
typedef long long LL;
？
const int N=100010;
int n,p,m;
int w[N];
struct Node？
{
int l,r;
int sum,add,mul;
}tr[N*4];
？
void pushup(int u)
{
tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
？
}
void eval(Node &t,int add,int mul)
{
t.sum=((LL)t.sum*mul+(LL)(t.r-t.l+1)*add)%p;
？
t.mul=(LL)t.mul*mul%p;
t.add=((LL)t.add*mul+add)%p;
}
void pushdown(int u)？
{
eval(tr[u<<1],tr[u].add,tr[u].mul);
eval(tr[u<<1|1],tr[u].add,tr[u].mul);
tr[u].add=0,tr[u].mul=1;
？
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,w[r],0,1};
？
else
{
tr[u]={l,r,0,0,1};
？
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}？
void modify(int u,int l,int r,int add,int mul)
{
if(tr[u].l>=l and tr[u].r<=r) eval(tr[u],add,mul);
？
else
{？
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
？
if(l<=mid) modify(u<<1,l,r,add,mul);
if(r>mid) modify(u<<1|1,l,r,add,mul);
pushup(u);
}？
}？
int query(int u,int l,int r)
{
if(tr[u].l>=l and tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
？？
int sum=0;
if(l<=mid) sum=qu？ery(u<<1,l,r);
if(r>mid) sum=(sum+query(u<<1|1,l,r))%p;
return sum;
？
}
int main()
{
scanf("%d%d%d",&n,&p);
？
for(int i=1;
i<=n;
i++) scanf("%d",&w[i]);
？
build(1,1,n);
？
scanf("%d",&m);
？
while(m--)？
{？
int t,l,r,d;
scanf("%d%d%d", &t,&l,&r);
？
if(t==1)？
{？
scanf("%d",&d);
？？
modify(1,l,r,0,d)；？
}？？
else if(t==2)？
{？
scanf("%d",&d);
？
modify(1,l,r,d,1);
？
}？
else printf("%d\n",query(1,l,r));
？
}？
return 0;
？
}
【基础数据结构】没了.平衡树模板（Treap,splay）到时候放
推荐阅读
- 模板|类欧几里得算法
- 模板|LOJ #2340. 「WC2018」州区划分(FMT子集卷积)
- 模板|FWT 模板
- C++|高精度加法 洛谷 P1601 A+B Problem（高精）
- C++题解|【模板】迷宫#1
- C++题解|【模板 / 约数】轻拍牛头