Lumi
博客

板子整理汇总 Part 1 （Basic）

520 字约 1 分钟#XCPC#模板

图论与树论#

LCA#

最常见的倍增LCA，另外存在树链剖分LCA。以及O（1）查询的离线tarjan LCA

CSS54 行
//倍增LCA，树剖LCA一样跳
const int N = 500005;
const int LOG = 20;

vector<int> g[N];
int f[N][LOG], dep[N];
int n, m, s;

void init(int s) {
    queue<int> q;
    dep[s] = 1;
    for (int i = 0; i < LOG; i++) f[s][i] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : g[u]) {
            if (v == f[u][0]) continue;

            dep[v] = dep[u] + 1;
            f[v][0] = u;

            for (int i = 1; i < LOG; i++) {
                f[v][i] = f[f[v][i-1]][i-1];
            }
            q.push(v);
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);

    int d = dep[x] - dep[y];

    for (int i = LOG - 1; i >= 0; i--) {
        if ((d >> i) & 1) {
            x = f[x][i];
        }
    }

    if (x == y) return x;

    for (int i = LOG - 1; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }

    return f[x][0];
}
CSS44 行
//tarjan 离线 O(n+m) LCA, 顺便赠送了LCA代码
vector<int> g[N];
vector<pair<int,int>> q[N]; // {另一个端点, 询问编号}

int dsu[N], sz[N], ancestor[N], ans[N];
bool done[N];

int find(int x) {
    if (dsu[x] == x) return x;
    return dsu[x] = find(dsu[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (sz[x] < sz[y]) swap(x, y);
    dsu[y] = x;
    sz[x] += sz[y];
}

void tarjan(int u, int fa) {
    dsu[u] = u;
    sz[u] = 1;
    ancestor[u] = u;

    for (int v : g[u]) {
        if (v == fa) continue;

        tarjan(v, u);

        merge(u, v);
        ancestor[find(u)] = u;
    }

    done[u] = true;

    for (auto [v, id] : q[u]) {
        if (done[v]) {
            ans[id] = ancestor[find(v)];
        }
    }
}

有向图求强联通分量 SCC#

CSS27 行
int dfn[N],low[N],st[N],be[N],in[N],vis[N];
vector <int> g[N];
vector <int> scc[N];
void tarjan(int u){
	int v;
	dfn[u]=low[u]=++num;
	st[++top]=u,vis[u]=1;
	for (int i=0;i<g[u].size();i++){
		v=g[u][i];
		if (!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else{
			if (vis[v]){
				low[u]=min(low[u],dfn[v]);
			}
		}
	}
	if (dfn[u]==low[u]){
		cnt++;
		do{
			v=st[top--];
			vis[v]=0;
			be[v]=cnt,scc[cnt].push_back(v);
		}while(u!=v);
	}
}

无向图求割边，割点，边双，点双#

（！！！ 首先，注意重边，vector存图用size当第二位当edge id）

割点，low[v]>=dfn[u]，记得特别判断 root 节点

割边，low[v]>dfn[u]

点双连通分量 V-BCC

CSS26 行
ll n,m,tot,cnt,dfn[N],low[N],d[N];
vector<ll>e[N],ans[N];
stack<ll>st;
void tarjan(ll u,ll fa){
	dfn[u]=low[u]=++tot;st.push(u);//将顶点扔到栈里
	if(!d[u]){//孤立点特殊处理
		ans[++cnt].push_back(u);
	}
	ll ct=0;
	for(int i=0;i<e[u].size();i++){
		ll v=e[u][i];//cout<<v<<" "<<fa<<endl;
		if(dfn[v])low[u]=min(low[u],dfn[v]);
		else{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				++cnt;ll t;
				do{//出栈操作
					t=st.top();ans[cnt].push_back(t);st.pop();//cout<<st.top()<<endl;
				}
				while(t!=v);
				ans[cnt].push_back(u);
			}
		}
	}
}

边双连通分量 E-BCC :

删掉所有桥边，留下的就各自是边双。具体的，Ban 掉桥边，每个连通块就是一个E-BCC

字符串#

KMP#

C11 行
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

马拉车#

CSS25 行
cin>>st;
	s+='?';
	for (i=0;i<st.size();i++){
		s+='#';
		s+=st[i];
	}
	s+='#';
	s+='@';
	int r=0,c=0;
	for (i=1;i<s.size()-1;i++){
		if (r>i){
			p[i]=min(r-i,p[2*c-i]);
		}else{
		    p[i]=1;
		}
		while (s[i+p[i]]==s[i-p[i]]){
			p[i]++;
		}
		if (i+p[i]>r){
			r=i+p[i];
			c=i;
		}
		maxn=max(maxn,p[i]);
	}
	cout<<maxn-1;

AC自动机（待整理）#

数据结构#

RMQ#

CSS29 行
constexpr int N = 100000 + 5;
constexpr int logN = 16;  // ⌊ log_2 N ⌋
int f[logN + 1][N], Logn[N];

// 初始化对数值
void pre() {
  Logn[2] = 1;
  for (int i = 3; i < N; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  pre();
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> f[0][i];
  for (int j = 1; j <= logN; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);  // ST表具体实现
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    int s = Logn[y - x + 1];
    cout << max(f[s][x], f[s][y - (1 << s) + 1]) << '\n';
  }
  return 0;
}

线段树#

首先是1个基础的区间修改，区间查询的线段树

CSS67 行
#define ls(x) x<<1
#define rs(x) x<<1|1
struct tree {
	int l,r;
	ll sum,add;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define add(x) t[x].add
};
tree t[M*4];

void build(int p,int l,int r) {
	l(p)=l,r(p)=r;
	if (l==r) {
		sum(p)=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(le(p),l,mid);
	build(ri(p),mid+1,r);
	sum(p)=(sum(le(p))+sum(ri(p)))%mod;
}

void spread(int p) {
	
	if (add(p)!=0) {
		add(le(p))=(add(le(p))+add(p))%mod;
		add(ri(p))=(add(ri(p))+add(p))%mod;
		sum(le(p))=(sum(le(p))+(ll)(r(le(p))-l(le(p))+1)*add(p))%mod;
		sum(ri(p))=(sum(ri(p))+(ll)(r(ri(p))-l(ri(p))+1)*add(p))%mod;
		add(p)=0;
	}
}

void change(int p,int l,int r,int d) {
	if (l<=l(p)&&r(p)<=r) {
		add(p)=(add(p)+d)%mod;
		sum(p)=(sum(p)+(ll)(r(p)-l(p)+1)*d)%mod;//int*int
		return;
	}
	spread(p);
	int mid=(l(p)+r(p))/2;
	if (l<=mid) {
		change(le(p),l,r,d);
	}
	if (r>mid) {
		change(ri(p),l,r,d);
	}
	sum(p)=(sum(le(p))+sum(ri(p)))%mod;
}

ll query(int p,int l,int r) {
	if (l<=l(p)&&r(p)<=r) {
		return sum(p)%mod;
	}
	spread(p);
	ll ans=0;
	int mid=(l(p)+r(p))/2;
	if (l<=mid) {
		ans=(ans+query(le(p),l,r))%mod;
	}
	if (mid<r) {
		ans=(ans+query(ri(p),l,r))%mod;
	}
	return ans;
}

学习到了一个神秘科技，线段树Beats，复杂度 (n+q)logn(n+q) log n

CSS84 行
struct Node {
    long long sum, mn1, mn2, tag;
    int cnt, len;
};

const long long INF = LLONG_MAX;

vector<Node> t;

// 使用两个子节点更新父节点
void pushup(int u) {
    auto &x = t[u];
    auto &a = t[u * 2];
    auto &b = t[u * 2 + 1];

    x.sum = a.sum + b.sum;
    x.len = a.len + b.len;

    x.mn1 = min(a.mn1, b.mn1);

    x.cnt = 0;
    if (a.mn1 == x.mn1) x.cnt += a.cnt;
    if (b.mn1 == x.mn1) x.cnt += b.cnt;

    x.mn2 = min(
        a.mn1 == x.mn1 ? a.mn2 : a.mn1,
        b.mn1 == x.mn1 ? b.mn2 : b.mn1
    );

    x.tag = 0; // 调用前父节点的标记已下传
}

// 对整个节点执行饱和减法
// 前提：d < mn2
void apply(int u, long long d) {
    auto &x = t[u];

    if (d == 0 || x.sum == 0) return;

    x.sum -= min(d, x.mn1) * x.cnt
           + d * (x.len - x.cnt);

    x.mn1 = max(0LL, x.mn1 - d);

    if (x.mn2 != INF) x.mn2 -= d;

    x.tag += d;
}

void pushdown(int u) {
    long long d = t[u].tag;

    if (d == 0) return;

    apply(u * 2, d);
    apply(u * 2 + 1, d);

    t[u].tag = 0;
}

void modify(int u, int l, int r,
            int ql, int qr, long long d) {

    if (qr < l || r < ql || t[u].sum == 0)
        return;

    // Beats 的关键判断
    if (ql <= l && r <= qr && d < t[u].mn2) {
        apply(u, d);
        return;
    }

    pushdown(u);

    int mid = (l + r) / 2;

    if (ql <= mid)
        modify(u * 2, l, mid, ql, qr, d);

    if (qr > mid)
        modify(u * 2 + 1, mid + 1, r, ql, qr, d);

    pushup(u);
}

可持久化线段树#

CSS42 行
int build(int l,int r){  // 也可以不用build，可以直接rt[0]=0,反正都是0
	int p=++cnt,mid;
	sum(p)=0;
	if (l==r){
		return p;
	}
	mid=(l+r)>>1;
	l(p)=build(l,mid);
	r(p)=build(mid+1,r);
	sum(p)=sum(l(p))+sum(r(p));
	return p;
}

int insert(int now,int l,int r,int pos,int delta){
	int p=++cnt,mid;
	tree[p]=tree[now];
	if (l==r){
		sum(p)+=delta;
		return p;
	}
	mid=(l+r)>>1;
	if (pos<=mid){
		l(p)=insert(l(now),l,mid,pos,delta);
	}else{
		r(p)=insert(r(now),mid+1,r,pos,delta);
	}
	sum(p)=sum(l(p))+sum(r(p));
	return p;
}

int ask(int p,int q,int l,int r,int k){// 有点二分的味道
	if (l==r){
		return l;
	}
	int lcnt=sum(l(p))-sum(l(q));
	int mid=(l+r)>>1;
	if (k<=lcnt){
		return ask(l(p),l(q),l,mid,k);
	}else{
		return ask(r(p),r(q),mid+1,r,k-lcnt);
	}
}
C++18 行
// 一个正常点的query
int query(int p,int l,int r,int x){
    if (p==0){
        return 0;
    }

    if (l==r){
        return sum(p);
    }

    int mid=(l+r)>>1;

    if (x<=mid){
        return query(ls(p),l,mid,x);
    }else{
        return query(rs(p),mid+1,r,x);
    }
}

树状数组#

CSS15 行
void upd(int x,int y) {
	while (x<=n) {
		c[x]=c[x]+y;
		x=x+find(x);
	}
}

long long cou(int x) {
	long long ans=0;
	while (x>0) {
		ans+=c[x];
		x-=find(x);
	}
	return ans;
}

分块#

CSS55 行
#include <cmath>
#include <iostream>
using namespace std;
int id[50005], len;
// id 表示块的编号, len=sqrt(n) , 即上述题解中的s, sqrt的时候时间复杂度最优
long long a[50005], b[50005], s[50005];

// a 数组表示数据数组, b 数组记录每个块的整体赋值情况, 类似于 lazy_tag, s
// 表示块内元素总和
void add(int l, int r, long long x) {  // 区间加法
  int sid = id[l], eid = id[r];
  if (sid == eid) {  // 在一个块中
    for (int i = l; i <= r; i++) a[i] += x, s[sid] += x;
    return;
  }
  for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x;
  for (int i = sid + 1; i < eid; i++)
    b[i] += x, s[i] += len * x;  // 更新区间和数组(完整的块)
  for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x;
  // 以上两行不完整的块直接简单求和,就OK
}

long long query(int l, int r, long long p) {  // 区间查询
  int sid = id[l], eid = id[r];
  long long ans = 0;
  if (sid == eid) {  // 在一个块里直接暴力求和
    for (int i = l; i <= r; i++) ans = (ans + a[i] + b[sid]) % p;
    return ans;
  }
  for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + b[sid]) % p;
  for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]) % p;
  for (int i = r; id[i] == eid; i--) ans = (ans + a[i] + b[eid]) % p;
  // 和上面的区间修改是一个道理
  return ans;
}

int main() {
  int n;
  cin >> n;
  len = sqrt(n);  // 均值不等式可知复杂度最优为根号n
  for (int i = 1; i <= n; i++) {  // 题面要求
    cin >> a[i];
    id[i] = (i - 1) / len + 1;
    s[id[i]] += a[i];
  }
  for (int i = 1; i <= n; i++) {
    int op, l, r, c;
    cin >> op >> l >> r >> c;
    if (op == 0)
      add(l, r, c);
    else
      cout << query(l, r, c + 1) << endl;
  }
  return 0;
}

树链剖分#

CSS76 行
void dfs1(int u,int father,int depth) {
	fa[u]=father;
	dep[u]=depth;
	size[u]=1;
	int ms=-1;
	for (int i=0; i<g[u].size(); i++) {
		int v=g[u][i];
		if (v==father) {
			continue;
		}
		dfs1(v,u,depth+1);
		size[u]+=size[v];
		if (size[v]>ms){
			ms=size[v];
			son[u]=v;
		}
	}
}

void dfs2(int u,int f){
	//cout<<u<<"***"<<f<<endl;
	top[u]=f;
	id[u]=++cnt;
	a[id[u]]=w[u];
	if (son[u]==0){
		return;
	}
	dfs2(son[u],f);
	for (int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if (v==fa[u]||v==son[u]){
			continue;
		}
		dfs2(v,v);
	}
}

void add_path(int x,int y,int k){
	k=k%mod;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]){
			swap(x,y);
		}
		change(1,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if (dep[x]>dep[y]){
		swap(x,y);
	}
	change(1,id[x],id[y],k);
}

int query_path(int x,int y){
	int ans=0;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]){
			swap(x,y);
		}
		ans=(ans+query(1,id[top[x]],id[x]))%mod;
		x=fa[top[x]];
	}
	if (dep[x]>dep[y]){
		swap(x,y);
	}
	ans=(ans+query(1,id[x],id[y]))%mod;
	return ans;
}

void add_tree(int x,int k){
	k=k%mod;
	change(1,id[x],id[x]+size[x]-1,k);
}

int query_tree(int x){
    return query(1,id[x],id[x]+size[x]-1)%mod;
}

数学#

整除符号#

a|b意味着 b 是 a 的倍数，例如 2|6

费马小定理#

若p为素数，a为正整数，且a、p互质。则有ap−1≡1(modp)a^{p−1} ≡ 1 ( mod p )。

exgcd#

由裴蜀定理知道，方程 ax+by=max + by = m 有整数解 (x, y) 的充分必要条件是 m 是 gcd(a,b)gcd(a,b) 的倍数，然后可以使用 exgcdexgcd 求解

CSS4 行
void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}

乘法逆元#

显然，只有a,p互质情况下存在a关于p的乘法逆元

  • p不是质数，exgcd
  • p是质数，a(p−2)a^{(p-2)} 即可
  • 线性递推
CSS3 行
inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;
  • 阶乘求法

中国剩余定理#

注意，CRT保证了 a1a_1 ~ ana_n 互质

CSS11 行
for(register int i = 1;i <= n;i ++) {
		a[i] = read();
		b[i] = read();
		ans *= a[i];
	}
	for(register int i = 1;i <= n;i ++) {
		int k = ans / a[i];
		int x , y;
		exgcd(k , a[i] , x , y);
		s = s +  k * b[i] * x % ans;
	}

杂七杂八#

去重+离散化#

CSS10 行
// 1. 排序
    sort(b + 1, b + n + 1);

    // 2. 去重
    m = unique(b + 1, b + n + 1) - (b + 1);

    // 3. 离散化
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    }

不要求顺序的离散化也可以直接用unordered_map

三分#

C++11 行
//代码中为求最小值
double l=0,r=1000;
while(r-l>eps){
	double mid1=(2*l+r)/3;
	double mid2=(l+2*r)/3;
	if(f(mid1)<f(mid2)){
		r=mid2;
	}else{
		l=mid1;
	}
}

Std 有关用法 map,set,multiset#

C++13 行
set <int> s;
multiset <int> ms;
s.insert();
s.erase();//by 值 or 迭代器
int mn = *s.begin();     // 最小
int mx = *s.rbegin();    // 最大

大于等于 xxx 的最小   s.lower_bound(x)         it != s.end()
严格大于 xxx 的最小   s.upper_bound(x)         it != s.end()
严格小于 xxx 的最大   prev(s.lower_bound(x))   s.lower_bound(x) != s.begin()
小于等于 xxx 的最大   prev(s.upper_bound(x))   s.upper_bound(x) != s.begin()

注意条件，包括set.empty(),能否找到？，prev(it),it是不是在s.begin()?

Auto 用法#

C++42 行

```cpp
// 1. 普通图
for (auto v : g[u]) {
    // ...
}

// 2. 带权图 pair
for (auto [v, w] : g[u]) {
    // ...
}

// 3. 带权图 struct
for (const auto &e : g[u]) {
    // ...
}

// 4. 修改 vector 元素
for (auto &x : a) {
    x++;
}

// 5. 遍历 set
for (auto x : s) {
    // ...
}

// 6. 遍历 map
for (auto &[k, v] : mp) {
    // ...
}

// 7. 二分返回迭代器
auto it = lower_bound(a.begin(), a.end(), x);

// 8. 查找 map/set
auto it = mp.find(x);

// 9. 遍历迭代器
for (auto it = s.begin(); it != s.end(); ++it) {
    // ...
}
纯文本1 行

搜索文章

按标题、标签或摘要查找文章