数据结构
vector
template<typename Tp>
struct Vector{Tp *arr=new Tp[1+5]; int siz_,cap_=1;void allocate(){Tp *new_arr=new Tp[(cap_<<1)+5];for(int i=0;i<cap_;i++)new_arr[i]=arr[i];arr=new_arr,cap_<<=1;}int size(){ return siz_; }void push_back(Tp x){if(siz_==cap_)allocate();arr[siz_++]=x;}Tp& operator[](const Tp &x)const{return arr[x];}Tp *begin(){ return arr; }Tp *end(){ return (arr+siz_); }void insert(int x,Tp val){if(siz_==cap_)allocate();for(int i=siz_-1;i>=x;i--)arr[i+1]=arr[i];siz_++,arr[x]=val;}
};
实现了 \(vector\) 最基础的功能，比 \(STL\) 稍快。
deque
template<typename Tp,int SIZ>
struct Deque{Tp q[SIZ+5]; int f=1,b=0;void push_back(Tp x){ q[++b]=x; }void pop_back(Tp x){ b--; }void pop_front(){ f++; }Tp front(){ return q[f]; }Tp back(){ return q[b]; }bool empty(){ return (f>b); }int size(){ return b-f+1; }
};
可用于单调队列。
stack
template<typename Tp,int SIZ>
struct Stack{Tp s[SIZ+5]; int t;void push(Tp x){ s[++t]=x; }void pop(Tp x){ t--; }Tp top(){ return s[t]; }bool empty(){ return (!t); }int size(){ return t; }
};
queue
template<typename Tp,int SIZ>
struct Queue{Tp q[SIZ+5]; int f=1,b;void push(Tp x){ q[b=b%(SIZ+1)+1]=x; }void pop(){ f=f%(SIZ+1)+1; }Tp front(){ return q[f]; }Tp back(){ return q[b]; }bool empty(){ return (b+1==f); }int size(){ return (b-f+2+SIZ)%(SIZ+1); }
};
循环队列，可用于 \(SPFA\)。
并查集
template<int SIZ>
struct DisJoint_Set{int f[SIZ+5];void clear(){ for(int i=1;i<=SIZ;i++)f[i]=i; }int find(int x){ return (f[x]==x)?x:f[x]=find(f[x]); }void merge(int x,int y){ f[find(x)]=find(y); }
};
路径压缩并查集。
template<int SIZ>
struct DisJoint_Set{int f[SIZ+5]; bool val[SIZ+5];void clear(){for(int i=1;i<=SIZ;i++)f[i]=i,val[i]=0;}int find(int x){if(f[x]==x)return x;int fa=f[x]; f[x]=find(f[x]);val[x]^=val[fa]^val[f[x]];return f[x];}void Union(int x,int y,bool b){int fx=find(x),fy=find(y);if(fx==fy)return; f[fx]=fy;if(!(b^val[x]^val[y]))val[fx]=1;}
};
带权并查集，可用于维护两个对立的集合。
BIT
template<int SIZ>
struct BIT{int tr[SIZ+5];inline int lowbit(int x){ return x&(-x); }void add(int x,int val){for(int i=x;i<=SIZ;i+=lowbit(i))tr[i]+=val;}int query(int x){int ans=0;for(int i=x;i;i-=lowbit(i))ans+=tr[i];return ans;}
};
单修区查树状数组。
ST表
template<int SIZ>
struct Sparse_Table{int ST[20][SIZ+5],log[SIZ+5]={-1};void build(){for(int i=1;i<=SIZ;i++)log[i]=log[i>>1]+1;for(int i=1;i<=log[SIZ];i++)for(int j=1;j+(1<<i)<=SIZ+1;j++)ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]); }int query(int L,int R){int k=log[R-L+1];return min(ST[k][L],ST[k][R-(1<<k)+1]);}
};
哈希表
namespace Hash_table{
constexpr int M=1e6+3,A=535365,B=956756756,p=1e9+7;
struct Hash_Table{struct E{ int last; long long x,val; }e[M];int head[M],cnt;int get_hash(long long x){ return (x*A+B)%p%M; }long long &operator[](const long long &x){int y=get_hash(x);for(int i=head[y];i;i=e[i].last)if(e[i].x==x)return e[i].val;e[++cnt].x=x,e[cnt].val=0;e[cnt].last=head[y],head[y]=cnt;return e[cnt].val;}
};
}using Hash_table::Hash_Table;
可以像数组一样使用。
算法
离散化
template<typename Tp>
void Discreteization(Tp arr_a[],int L,int R){Tp* arr_new=new Tp[R-L+5];for(int i=1,j=L;j<=R;i++,j++)arr_new[i]=arr_a[j];sort(arr_new+L,arr_new+R+1);int max_arr=unique(arr_new+L,arr_new+R+1)-arr_new-1;for(int i=L;i<=R;i++)arr_a[i]=lower_bound(arr_new+1,arr_new+max_arr+1,arr_a[i])-arr_new;delete[] arr_new;
}