---

基本数据结构

最基本的数据结构有栈、队列、链表、堆等等，除了链表之外，C++的STL都有相应的实现。

• 栈：stack<type>，push() ，pop() ，top()等；
• 队列：queue<type>，push()，pop()，front() 等；
• 堆：priority_queue<type>（priority_queue<type,vector<type>,func>），push() ，pop() ，top()等；
• 集合：set<type>，insert()，count()，size() 等；

除此之外，STL中还有很多有用的数据结构，比如说：

• deque：双端队列，注意STL中的栈和队列其实都是基于deque实现的；
• vector：向量，类似数组，而且是可变长数组；
• map：内部实现的是红黑树，可以实现任意两种类型的一一映射；
• unordered_map：内部实现的是哈希表，其实和map功能差不多，但是这个查找更快，不过内部元素无序；
• bitset：一种支持各种位运算并且特别高效的结构；
• multiset：支持重复元素的集合；
• pair：二元对，比较方便；

并查集

一种树形结构，支持集合的合并和查询：

• 合并（union）：合并两个子集；
• 查询（find）：查询某个元素属于哪个集合；

并查集的名字也由此而来。

并查集的代码如下：

const int maxn=1e5+5;
int n,far[maxn];int find(int x) {return x==far[x]?x:far[x]=find(far[x]);}
bool isSame(int x,int y) {return find(x)==find(y);}
void unite(int x,int y) {far[find(x)]=find(y);}// 注意要初始化
// REP(i,1,n) far[i]=i;

上面的代码已经实现了路径压缩，大多数情况已经足够快了（平均单次复杂度是阿克曼函数级别的），如果要求比较严格，可以加上启发式合并，也就是合并的时候让集合小的合并到集合大的上面去。

st表

st表用于处理RMQ问题，可以在O(nlogn)的时间内建表，在O(1)时间内查询。

其实就是一个倍增+dp的思想，$st[i][j]$ 表示 $a[i]$ 至 $a[i+2^j-1]$ 这个区间的最值。

代码如下：

const int maxn=1e5+5;
int st[maxn][22],lg2[maxn],a[maxn];void get_st(int n)
{REP(i,2,maxn-1) lg2[i]=lg2[i-1]+(1<<(lg2[i-1]+1)==i);REP(i,1,n) st[i][0]=a[i];REP(j,1,lg2[n]) REP(i,1,n+1-(1<<j))st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}int RMQ(int l,int r)
{int k=lg2[r-l+1];return max(st[l][k],st[r-(1<<k)+1][k]);
}

扩展到二维，其实也是一样的，用 $st[r][c][i][j]$ 表示 $a[r][c]$ 至 $a[r+2^i-1][c+2^j-1]$ 这个区间内的最值。

代码如下：

const int maxn=500,N=11;
int lg2[maxn],a[maxn][maxn],st[maxn][maxn][N][N];void get_st(int n,int m)
{REP(i,2,maxn-1) lg2[i]=lg2[i-1]+(1<<(lg2[i-1]+1)==i);REP(i,1,n) REP(j,1,m) st[i][j][0][0]=a[i][j];int t=lg2[n];REP(i,0,t) REP(j,0,t){if(!i && !j) continue;REP(r,1,n+1-(1<<i)) REP(c,1,m+1-(1<<j))if(i) st[r][c][i][j]=max(st[r][c][i-1][j],st[r+(1<<(i-1))][c][i-1][j]);else st[r][c][i][j]=max(st[r][c][i][j-1],st[r][c+(1<<(j-1))][i][j-1]);}
}int RMQ2(int x,int y,int xx,int yy)
{int k=lg2[xx-x+1],kk=lg2[yy-y+1];int ans1=max(st[x][y][k][kk],st[xx-(1<<k)+1][y][k][kk]);int ans2=max(st[x][yy-(1<<kk)+1][k][kk],st[xx-(1<<k)+1][yy-(1<<kk)+1][k][kk]);return max(ans1,ans2);
}

做题的时候对于二维情况，比较多的是算一个正方形内部的最值，这个时候st数组只用三维就够了。

线段树

一种支持可合并的区间操作的数据结构，比如区间极值，区间和等等。

线段树有很多技巧，懒惰标记，永久标记（其实就是某个点管了整个子树）等等。

由于线段树是一种非常基本的竞赛必备知识，已经写了很多了，这里就放一个支持区间加法更新的 洛谷P3372 的模板：

const int maxn=1e5+5;
LL a[maxn],tree[maxn<<2],tag[maxn<<2];#define chl k<<1
#define chr k<<1|1
#define mid ((l+r)>>1)void push_up(int k) {tree[k]=tree[chl]+tree[chr];}void build(int k,int l,int r)
{if(l>r) return;if(l==r) {tree[k]=a[l]; return;}build(chl,l,mid); build(chr,mid+1,r);push_up(k);
}void push_down(int k,int l,int r)
{if(!tag[k]) return;tag[chl]+=tag[k]; tag[chr]+=tag[k];tree[chl]+=tag[k]*(mid-l+1); tree[chr]+=tag[k]*(r-mid);tag[k]=0;
}void add(int k,int l,int r,int ll,int rr,LL x)
{if(l>rr || ll>r) return;if(l>=ll && r<=rr){tree[k]+=(r-l+1)*x;tag[k]+=x;return;}push_down(k,l,r);add(chl,l,mid,ll,rr,x); add(chr,mid+1,r,ll,rr,x);push_up(k);
}LL query(int k,int l,int r,int ll,int rr)
{if(l>rr || ll>r) return 0;if(l>=ll && r<=rr) return tree[k];push_down(k,l,r);return query(chl,l,mid,ll,rr)+query(chr,mid+1,r,ll,rr);
}int main()
{int n=read(),m=read();REP(i,1,n) a[i]=read();build(1,1,n);while(m--){int op=read(),l=read(),r=read();if(op==1) {int x=read(); add(1,1,n,l,r,x);}else printf("%lld\n",query(1,1,n,l,r));}return 0;
}

单调队列

其实有单调栈和单调队列，但是其实单调栈就是一种特殊的单调队列，所以可以混为一谈。

单调队列就是维护一个序列，这个序列是单调的，而且只能从队首和队尾进行操作（单调栈就是只能栈顶），往往用于优化某一类问题，这一类问题有很多潜在答案，我们每次把更优的答案放在更前面，并且保证每个值只会出入队列一次，这样就可以在 O(n) 的时间内解决这类问题。

经典的应用是 滑动窗口(sliding window) ，该题的代码如下：

const int maxn=1e6+5;
typedef pair<int,int> P;
P Q[maxn];
int head,tail,n,k,a[maxn];void solve(int cmp(int,int))
{head=tail=0;REP(i,1,n){if(i<k){while(head<tail && cmp(Q[tail-1].first,a[i])) tail--;Q[tail++]=P(a[i],i);}else{while(head<tail && Q[head].second<=i-k) head++;while(head<tail && cmp(Q[tail-1].first,a[i])) tail--;Q[tail++]=P(a[i],i);printf("%d ",Q[head].first);}}puts("");
}int cmp1(int x,int y) {return x<=y;}
int cmp2(int x,int y) {return x>=y;}int main()
{//freopen("input.txt","r",stdin);scanf("%d%d",&n,&k);REP(i,1,n) scanf("%d",&a[i]);solve(cmp2); solve(cmp1);return 0;
}

单调队列还可以解决很多问题，比如说对于一个序列，可以求出每个数左侧第一个大于（或等于）这个数的位置，比如这题 bad hair day（这题是右侧）。这题代码如下：

const int maxn=8e4+5;
typedef pair<int,int> P;
P Q[maxn];
int head,tail,n,h[maxn],l[maxn];int main()
{//freopen("input.txt","r",stdin);n=read();REP_(i,n,1) h[i]=read();LL ans=0;REP(i,1,n){while(head<tail && Q[tail-1].first<h[i]) tail--;l[i]=head<tail?Q[tail-1].second:0;Q[tail++]=P(h[i],i);}REP(i,1,n) ans+=i-l[i]-1;cout<<ans;return 0;
}

另外，单调队列还可以用来优化dp。