线段树
维护复杂信息时重载 + 号，不同的修改直接在 upd() 中改。
struct SegTree{
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)ll tr[N<<2],tag[N<<2];void pushup(int u){tr[u]=tr[ls]+tr[rs];}void upd(int u,ll k,int len){tr[u]+=k*len;tag[u]+=k;}void pushdown(int u,int l,int r){upd(ls,tag[u],mid-l+1);upd(rs,tag[u],r-mid);tag[u]=0;}void build(int u=1,int l=1,int r=n){if(l==r){tr[u]=a[l];return;}build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void modify(int x,int y,ll k,int u=1,int l=1,int r=n){if(l>=x && r<=y){upd(u,k,r-l+1);return;}pushdown(u,l,r);if(x<=mid) modify(x,y,k,ls,l,mid);if(mid<y) modify(x,y,k,rs,mid+1,r);pushup(u);}ll query(int x,int y,int u=1,int l=1,int r=n){if(l>=x && r<=y) return tr[u];pushdown(u,l,r);ll res=0;if(x<=mid) res+=query(x,y,ls,l,mid);if(mid<y) res+=query(x,y,rs,mid+1,r);return res;}
}Tr;
树状数组
感觉好久没写了。
struct BIT{
#define lowbit(i) i&-ill tr[N];void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)){tr[i]+=k;}}ll query(int x){ll res=0;for(int i=x;i;i-=lowbit(i)){res+=tr[i];}return res;}
}T;
AC 自动机
字符集默认小写字符。
struct ACauto{struct node{int son[26];int fail,cnt;}tr[M];int tot=0;void insert(const string &s){int u=0;for(char ch:s){int &son=tr[u].son[ch-'a'];if(!son) son=++tot;u=son;}tr[u].cnt++;}void build_fail(){queue<int> que;for(int i=0;i<26;i++){if(tr[0].son[i]) que.push(tr[0].son[i]);}while(!que.empty()){int u=que.front();que.pop();for(int i=0;i<26;i++){if(tr[u].son[i]){tr[tr[u].son[i]].fail=tr[tr[u].fail].son[i];que.push(tr[u].son[i]);}else tr[u].son[i]=tr[tr[u].fail].son[i];}}}
}AC;
哈希表
其实不会用……
#include<bits/extc++.h>
using namespace __gnu_pbds;
constexpr int P=131,p1=998244353,p2=1e9+7;
int qpow(int a,int b,const int &p){int res=1;while(b){if(b&1) res=(ll)res*a%p;b>>=1,a=(ll)a*a%p;}return res;
}
int hash1(const string &s){ll a=0,b=1;for(char ch:s){b=b*P%p1;a=(a*P+ch)%p1;}return a*b;
}
int hash2(const string &s){ll a=0,b=1;for(char ch:s){b=b*P%p2;a=(a*P+ch)%p2;}return a*b;
}
struct pair_hash{size_t operator()(const pair<int,int> &x)const{size_t seed=0;seed^=hash<int>{}(x.first)+0x9e3779b9+(seed<<6)+(seed>>2);seed^=hash<int>{}(x.second)+0x9e3779b9+(seed<<6)+(seed>>2);return seed;}
};
gp_hash_table<pair<int,int>,int,pair_hash> mp;
//调用hash1和hash2扔键里，值是有多少个相同的。
矩阵
struct Matrix{
#define M 4int a[M][M];Matrix(){memset(a,0,sizeof(a));}void init(){for(int i=0;i<M;i++) a[i][i]=1;}Matrix operator + (const Matrix &b)const{Matrix res=Matrix();for(int i=1;i<M;i++){for(int j=1;j<M;j++){res.a[i][j]=a[i][j]+b.a[i][j];}}return res;}Matrix operator * (const Matrix &b)const{Matrix res=Matrix();for(int k=1;k<M;k++){for(int i=1;i<M;i++){for(int j=1;j<M;j++){res.a[i][j]=res.a[i][j]+1ll*a[i][k]*b.a[k][j];}}}return res;}
};
Tarjan
//tarjan缩点后有天然的逆序拓扑序
vector<int> G1[N],G2[N];
int dfn[N],dfx,low[N],scc,bel[N],siz[N];
bool vis[N];
stack<int> sta;
void tarjan(int u){dfn[u]=low[u]=++dfx;vis[u]=1;sta.push(u);for(int v:G1[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){scc++;while(sta.top()!=u){int t=sta.top();sta.pop();vis[t]=0;bel[t]=scc;siz[scc]++;}vis[u]=0;bel[u]=scc;siz[scc]++;sta.pop();}
}
SA
struct SufArr{int x[N],y[N],s[N],cnt[N],sa[N],rk[N],len;//x,y,cnt,sa,rk不用管。//s是原串，len是原串的长度。//sa是后缀第 i 小的编号//rk是第 i 个后缀的排名void build(){for(int i=1;i<=len;i++){x[i]=s[i];cnt[x[i]]++;}for(int i=2;i<=10000;i++){cnt[i]+=cnt[i-1];}for(int i=len;i>=1;i--){sa[cnt[x[i]]--]=i;}for(int k=1;k<=len;k<<=1){int num=0;for(int i=len-k+1;i<=len;i++){y[++num]=i;}for(int i=1;i<=len;i++){if(sa[i]>k){y[++num]=sa[i]-k;}}for(int i=1;i<=m;i++) cnt[i]=0;for(int i=1;i<=len;i++) cnt[x[i]]++;for(int i=2;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=len;i>=1;i--){sa[cnt[x[y[i]]]--]=y[i];y[i]=0;}swap(x,y);x[sa[1]]=1,num=1;for(int i=2;i<=len;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;if(num==len) break;m=num;}for(int i=1;i<=len;i++){rk[sa[i]]=i;}}
}SA;
李超线段树
struct Line{int k,b;int f(int x){return x*k+b;}
}li[N<<1];int cnt;
struct Tree{
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1) int tr[N<<3];int insert(int k,int b){li[++cnt]={k,b};return cnt;}void update(int u,int l,int r,int x,int y,int k){if(l>=x && r<=y){if(li[k].f(mid)>li[tr[u]].f(mid)) swap(k,tr[u]);if(l==r) return;if(li[k].f(l)>li[tr[u]].f(l)) update(ls,l,mid,x,y,k);if(li[k].f(r)>li[tr[u]].f(r)) update(rs,mid+1,r,x,y,k);}if(x<=mid) update(ls,l,mid,x,y,k);if(mid<y) update(rs,mid+1,r,x,y,k);}int query(int u,int l,int r,int x){if(l==r) return li[tr[u]].f(x);int res=li[tr[u]].f(x);if(x<=mid) res=max(res,query(ls,l,mid,x));else res=max(res,query(rs,mid+1,r,x));return res;}
#undef ls
#undef rs
#undef mid
}Tr;