动态规划

基础DP

线性DP

动态规划分析步骤

模板题——破损的楼梯

"""
3367 破损的楼梯
https://www.lanqiao.cn/problems/3367/learning

这是一个典型的线性DP问题，dp[i]表示到达第i阶楼梯的方法数
状态转移方程：dp[i]=dp[i-1]+dp[i-2]
状态压缩：dp[i]只与dp[i-1]和dp[i-2]有关，所以可以压缩
时间复杂度：O(n)
空间复杂度：O(n)
"""
N = int(1e5 + 10)
mod = int(1e9 + 7)
n, m = map(int, input().split())
a = list(map(int, input().split()))
vis = [0] * N
for i in a: vis[i] = 1
dp = [0] * N
dp[0] = 1
dp[1] = 1 - vis[1]
for i in range(2, n + 1):
    if vis[i]:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[n])

n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+1)
tp=[0]*(n+1)
for i in a:
  tp[i]=1
dp[0]=1
dp[1]=1-tp[1]
for i in range(2,n+1):
  if tp[i]==1:
    continue
  dp[i]=dp[i-1]+dp[i-2]
mod=10**9+7
print(dp[i]%mod)

二维DP

分析步骤

模板题——数字三角形

import os
import sys

# 请在此输入您的代码
N = int(input())
dp = [list(map(int, input().split())) for _ in range(N)]
for i in range(1, N):
    for j in range(i + 1):
        if j == 0:
            dp[i][j] += dp[i - 1][j]
        elif j == i:
            dp[i][j] += dp[i - 1][j - 1]
        else:
            dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j])
print(max(dp[N - 1]))

模板题——摆花

'''
n种花凑 m盆 每种<a[i]
1.分解子问题
前i种花，一共j盆，答案是dp[n][m]
2.状态转移
前i种花有j盆方案数  如何由前i-1种有j盆得出.
以下每一种选择是一种方案
第i种花可以选0盆,前i-1种花有j盆：dp[i][j] = dp[i-1][j]
第i种花可以选1盆,前i-1种花有j-1盆：：dp[i][j] = dp[i-1][j-1]
...
第i种花可以选a[i]盆,前i-1种花有j-a[i]盆：：dp[i][j] = dp[i-1][j-a[i]]
3.边界条件，每种花都不选
前i种花 0盆 是 一种方案 dp[i][0] = 1
'''
MOD = 10 ** 6 + 7
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
dp = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n+1):
    dp[i][0] = 1
# 状态转移,当下做出的选择，利用之前dp,求dp[i][j]
for i in range(1,n+1):
    for j in range(1,m+1):
        for k in range(min(a[i],j)+1):
            dp[i][j]+=dp[i-1][j-k]
            dp[i][j]%=MOD
print(dp[n][m])

模板题——选数异或

n,x = map(int,input().split())
a = [0] + list(map(int,input().split()))
Mod = 998244353
'''
 dp[i][j]前i个正整数有j个子序列异或成 j 的方案；答案dp[n][x]
 dp[i][j] = 选第i个数字 + 不选第i个数字
          = dp[i - 1][j ^ a[i]] + dp[i - 1][j]   
          (因为如果选了第i个数字，那么a[i] ^ 前数 = j, 所以：前数 = j ^ a[i])
'''
dp = [[0] * (64) for _ in range(n + 1)]
# 初始化为 0
dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(64):
        dp[i][j] = (dp[i-1][j] + dp[i-1][j ^ a[i]]) % Mod
print(dp[n][x])

LIS

最长上升子序列

模板题——蓝桥勇士

n=int(input())
a=[0]+list(map(int,input().split()))
dp=[1]*(n+1)
for i in range(1,n):
  for j in range(i+1,n+1):
    if a[i]<a[j]:
      dp[j]=max(dp[j],dp[i]+1)
print(max(dp))

模板题——合唱队形

n = int(input())
a = [0] + list(map(int, input().split()))
dp1 = [0] * (n + 1)  # dp1[i]表示以i结尾的最长上升子序列长度
dp2 = [0] * (n + 1)  # dp2[i]表示以i出发的最长下降子序列长度

for i in range(1, n + 1):
    dp1[i] = 1
    for j in range(1, i):
        if a[i] > a[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

for i in range(n, 0, -1):
    dp2[i] = 1
    for j in range(i + 1, n + 1):
        if a[i] > a[j]:
            dp2[i] = max(dp2[i], dp2[j] + 1)

ans = max((dp1[i] + dp2[i] - 1) for i in range(1, n + 1))
print(n-ans)

LCS

最长公共子序列

模板题——最长公共子序列

import os
import sys
# 这段代码实现的是计算两个序列（a 和 b）的最长公共子序列（Longest Common Subsequence, LCS）的长度。LCS 是一种在计算两个序列相似度时常用的度量方法。这个问题通常通过动态规划来解决。现在，我将逐步解释这段代码的各个部分：

# 输入处理
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
# 首先，通过 input().split() 获取两个整数 n 和 m，分别表示序列 a 和 b 的长度。
# 接着，读取这两个序列，并在序列前面各自加上一个 0 作为哨兵值。这样做是为了让序列的索引从 1 开始，方便后续操作。
# 初始化动态规划数组
dp = [[0] * (m + 1) for _ in range(2)]  # 注意这里是 m，不是 n
now = 0; old = 1
# 初始化一个二维动态规划数组 dp，但这里只用到了两行（range(2)），目的是节省空间。因为在计算当前状态时，只需要用到前一行（即上一状态）的数据。m + 1 是因为考虑到从 0 开始到 m 的所有可能位置。
# now 和 old 变量用来在这两行之间切换，表示当前行和上一行。
# 动态规划过程
for i in range(1, n + 1):
    now, old = old, now
    for j in range(1, m + 1):
        dp[now][j] = max(dp[now][j - 1], dp[old][j])
        if a[i] == b[j]: 
            dp[now][j] = max(dp[now][j], dp[old][j - 1] + 1)
# 这部分是动态规划的核心。
# 外层循环遍历序列 a，内层循环遍历序列 b。
# dp[now][j] = max(dp[now][j - 1], dp[old][j])：当前状态是基于之前状态的最大值，这表示如果当前字符不匹配，LCS 长度不变。
# 如果当前位置的字符相等（a[i] == b[j]），则检查上一个状态的值并加一，即 dp[now][j] = max(dp[now][j], dp[old][j - 1] + 1)。这反映了找到了一个公共元素，因此当前的最长公共子序列长度增加了 1。
# 输出结果
print(dp[now][m])
# 最后，打印出最长公共子序列的长度，即在遍历完两个序列后，dp 数组最后一个元素（dp[now][m]）的值。
# 通过这种方式，代码高效地计算了两个序列的最长公共子序列的长度，同时通过只使用两行的动态规划数组大大减少了空间复杂度。

背包DP

01背包

模板题——小明的背包1

#dp[i][j]    前i件物品，总体积不超过j 的最大价值

n,v=map(int,input().split())
dp=[[0]*(v+1) for i in range(n+1)]

for i in range(1,n+1):
    wi,vi=map(int,input().split())
    for j in range(0,v+1):
        if j>=wi:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+vi)
        else:
            dp[i][j]=dp[i-1][j]
            
print(dp[n][v])

滚动数组优化

n,V=map(int,input().split())
dp=[0]*(V+1)
for i in range(1,n+1):
  w,v=map(int,input().split())
  for j in range(V,w-1,-1):
    dp[j]=max(dp[j],dp[j-w]+v)
print(dp[V])

完全背包

模板题——小明的背包2

# dp[i][j]=max(dp[i-1][j],dp[i][j-wi]+vi)  不取或在先前基础上取第i种（所以可以取多次）

n,v=map(int,input().split())
dp=[[0]*(v+1) for i in range(n+1)]
for  i in range(1,n+1):
    wi,vi=map(int,input().split())
    for j in range(0,v+1):
        if (j>=wi):
            dp[i][j]=max(dp[i-1][j],dp[i][j-wi]+vi)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][v])

滚动数组优化

import os
import sys
N, V = map(int, input().split())
items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append((w, v))
dp = [0] * (V + 1)
for i in range(1, V + 1):
    for w, v in items:
        if i >= w:
            dp[i] = max(dp[i], dp[i - w] + v)
print(dp[V])
'''
读取输入的商场物品数量N和小明的背包容量V，以及每种物品的体积和价值。
初始化一个长度为V+1的动态规划数组dp，dp[i]表示背包容量为i时所能获得的最大价值。
使用动态规划求解，外层循环遍历背包容量从1到V，内层循环遍历每种物品，更新dp[i]的值为dp[i-w]+v和当前dp[i]的较大值。
输出dp[V]即为小明所能获得的最大价值。
'''

多重背包

模板题——小明的背包3

#dp[i][j] =max(dp[i][j],dp[i-1][j-k*wi]+k*vi)  k属于(0，si)

n,v=map(int,input().split())
dp=[[0]*(v+1) for i in range(n+1)]
for i in range(1,n+1):
    wi,vi,si=map(int,input().split())
    for j in range(0,v+1):
        for k in range(0,min(si,j//wi)+1):

            dp[i][j]=max(dp[i][j],dp[i-1][j-k*wi]+k*vi)

print(dp[n][v])

滚动数组优化

N,V=map(int,input().split())
w,v,s=[[0]*(N+1) for _ in range(3)]
dp=[0 for _ in range(V+1)]
for i in range(1,N+1):
  w[i],v[i],s[i]=map(int,input().split())
for i in range(1,N+1):
  for j in range(s[i]):
    for k in range(V,0,-1):
      if w[i]<=k:
        dp[k]=max(dp[k-w[i]]+v[i],dp[k])
print(dp[-1])

二维费用背包&分组背包

模板题——小蓝的神秘行囊

import sys

n, v, m = map(int, sys.stdin.readline().split())
dp = [[0]*(v + 1) for _ in range(m + 1)]
for _ in range(n):
    volume, mass, value = map(int, sys.stdin.readline().split())
    for i in range(m, 0, -1):
        for j in range(v, 0, -1):
            if i >= mass and j >= volume:
                dp[i][j] = max(dp[i][j], dp[i-mass][j-volume] + value)
print(dp[m][v])

n,v,m=map(int,input().split())
dp=[[0]*(m+1) for i in range(v+1)]

for i in range(1,n+1):
    vi,mi,wi=map(int,input().split())
    for j in range(v,vi-1,-1):
        for k in range(m,mi-1,-1):
            dp[j][k] =max(dp[j][k],dp[j-vi][k-mi]+wi)
           
print(dp[v][m])

树形DP

状压DP

数位DP

字符串

KMP

模式匹配

KMP算法

模板题——斤斤计较的小Z

Next = [0] * 1000010
def get_next(T):
    for i in range(1,len(T)):
        j = Next[i]
        while j > 0 and T[i] != T[j]:
            j = Next[j]
        if T[i] == T[j]:
            Next[i + 1] = j + 1
        else:
            Next[i + 1] = 0
def KMP(s,t):
    get_next(t)
    ans = 0
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != t[j]:
            j =  Next[j]
        if s[i] == t[j]:
            j += 1
        if j == len(t):
            ans += 1
            j =  Next[j]
    return ans
t = input()
s = input()
print(KMP(s,t))

print((lambda s: input().count(s))(input()))

Hash

字符串哈希

模板题——斤斤计较的小Z

t = input()
s = input()
m,n = len(t), len(s)
B = 26
mod = 1000000007
hash = [0] * (n + 1)
for i in range(1,n + 1):
    hash[i] = hash[i - 1] * B + ord(s[i - 1]) - ord('A')
    hash[i] %= mod

numT = 0
for c in t:
    numT = numT * B + ord(c) - ord('A')
    numT %= mod
    
p = (B ** m) % mod
ans = 0
for l in range(1,n +1):
    r = l + m - 1
    if r > n:
        break
    if (hash[r] - hash[l - 1] * p % mod + mod) % mod == numT:
        ans += 1
print(ans)

排序

归并排序

快速排序

数学

二项式定理

容斥原理

排列组合

模意义下的逆元

矩阵运算

数据结构

ST表

RMQ问题

平衡树

平衡树-Splay

平衡树-FHQ_Treap

无旋Treap

无旋Treap的结构

基本操作

案例

struct NODE {
    int val;
    int cnt;
    int rev;
    int prio;
    int size;
    int ch[2];
}

struct FHQTREAP {
    int root;
    int size;
    NODE node[MAXN];
}

pair<int, int> split_by_val(int t, int val) {
    if (!t) {
        return {0, 0};
    }
    check_rev(t);
    if (node[t].val <= val) {
        auto tmp = split_by_val(node[t].ch[1], val);
        node[t].ch[1] = tmp.first;
        update_size(t);
        return {t, tmp.second};
    } else {
        auto tmp = split_by_val(node[t].ch[0], val);
        node[t].ch[0] = tmp.second;
        update_size(t);
        return {tmp.first, t};
    }
}

tuple<int, int, int> split_by_rank(int t, int k) {
    if (!t) {
        return {0, 0, 0};
    }
    check_rev(t);
    int lt, mt, rt;
    if (k <= node[node[t].ch[0]].size()) {
        tie(lt, mt, rt) = split_by_rank(node[t].ch[0], k);
        node[t].ch[0] = rt;
        update_size(t);
        return {lt, mt, t};
    } else if (k > node[node[t]].ch[0].size() + node[t].cnt) {
        tie(lt, mt, rt) = split_by_rank(node[t].ch[1], k - node[node[t].ch[0]].size() - node[t].cnt);
        node[t].ch[1] = lt;
        update_size(t);
        return {t, mt, rt};
    } else {
        lt = node[t].ch[0];
        rt = node[t].ch[1];
        check_rev(lt);
        check_rev(rt);
        node[t].ch[0] = 0;
        upda[t].ch[1] = 0;
        update_size(t);
        return {lt, t, rt};
    }
}

int merge(int lt, int rt) {
    if (!lt) {
        return rt;
    } else if (!rt) {
        return lt;
    }
    check_rev(lt);
    check_rev(rt);
    if (node[lt].prio < node[rt].prio) {
        node[lt].ch[1] = merge(node[lt].ch[1], rt);
        update_size(lt);
        return lt;
    } else {
        node[rt].ch[0] = merge(lt, node[rt].ch[0]);
        update_size(rt);
        return rt;
    }
}

void insert(int val) {
    int lt, mt, rt;
    tie(lt, rt) = split_by_val(root, val);
    tie(lt, mt) = split_by_val(lt, val - 1);
    if (!mt) {
        mt = new_node(val);
    } else {
        node[mt].cnt ++;
        update_size(mt);
    }
    root = merge(merge(lt, mt), rt);
}

void del(int val) {
    int lt, mt, rt;
    tie(lt, rt) = split_by_val(root, val);
    tie(lt, mt) = split_by_val(lt, val - 1);
    unode[mt].cnt --;
    update_size(mt);
    if (node[mt].cnt == 0) {
        clear(mt);
    } else {
        lt = merge(lt, mt);
    }
    root = merge(lt, rt);
}

void reverse(int l, int r) {
    int t1, t2, t3, t4, t5;
    tie(t1, t2, t3) = split_by_rank(root, l - 1);
    tie(t3, t4, t5) = split_by_ranl(t3, r - l + 2);
    node[t3].rev = 1;
    root = merge(merge(merge(merge(t1, t2), t3), t4), t5);
}

void check_rev(int t) {
    if (node[t].rev) {
        swap(node[t].ch[0], node[t].ch[1]);
        node[node[t].ch[0]].rev ^= 1;
        node[node[t].ch[1]].rev ^= 1;
        node[t].rev = 0;
    }
}

int rank(int val) {
    auto tmp = split_by_val(root, val - 1);
    int k = node[tmp.first].size + 1;
    root = merge(tmp.first, tmp.second);
    return k;
}

int kth(int &t, int k) {
    int lt, mt, rt;
    tie(lt, mt, rt) = split_by_rank(t, k);
    int val = node[mt].val;
    t = merge(merge(lt, mt), rt);
    return val;
}

int pre(int val) {
    auto tmp = split_by_cal(root, val - 1);
    int k = kth(tmp.first, node[tmp.first].size);
    root = merge(tmp.first, tmp.second);
    return k;
}

int nxt(int val) {
    auto tmp = split_by_val(root, val);
    int k = kth(tmp.second, 1);
    root = merge(tmp.first, tmp.second);
    return k;
}

并查集

基础并查集

基础

模板题——蓝桥幼儿园

# def Findroot(x):
#     while x!=p[x]:
#         x=p[x]
#     return x
'''使用路径压缩'''
def Findroot(x):
    if x==p[x]:return x
    #路径压缩
    p[x]=Findroot(p[x])
    return p[x]
def Merge(x,y):
    rootx,rooty=Findroot(x),Findroot(y)
    p[rootx]=rooty
def Query(x,y):
    rootx,rooty=Findroot(x),Findroot(y)
    return rootx==rooty
n,m=map(int,input().split())
p=list(range(n+1))
for _ in range(m):
    op,x,y=map(int,input().split())
    if op ==1:
        Merge(x,y)
    else:
        if Query(x,y):
            print("YES")
        else:
            print("NO")

路径压缩

模板题——星球大战

import os
import sys
M = 200010; N = 2 * M
n, m = map(int, input().split())
father = [0] * (n + 10)                 #并查集板块
def init():
    for i in range(n + 10):
        father[i] = i
def find_father(x):
    if x != father[x]: father[x] = find_father(father[x])
    return father[x]
def unite(x, y):
    father[find_father(x)] = find_father(y)
come = [0] * N; to = [0] * N;   #存储每个边
g = [[] for _ in range(N)]      #邻接表
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b); g[b].append(a)
    come[i] = a; to[i] = b 
broken = [0] * (n + 10)                     #记录每个点是否被修坏
destroy = []
k = int(input())
for i in range(k):
    b = int(input())
    broken[b] = 1
    destroy.append(b)
init()
res = n - k             #先计算所有剩下星球的连通块数，(最后一轮的结果)
for i in range(m):
    l = come[i]; r = to[i]
    fl, fr = find_father(l), find_father(r)
    if not broken[l] and not broken[r] and fl != fr:
        res -= 1
        #unite(l, r)
        father[fl] = fr
ans = [res]
for i in range(len(destroy) - 1, -1, -1):       #顺序破坏，相当于倒序修建
    c = destroy[i]
    broken[c] = 0
    res += 1                                    #修好一个星球，连通块会多一个
    for j in g[c]:
        fc, fp = find_father(c), find_father(j)
        if not broken[j] and fc != fp:
            res -= 1
            father[fc] = fp
    ans.append(res)
for i in range(len(ans) - 1, -1, -1):           #倒序输出结果
    print(ans[i])

可撤销并查集

可撤销并查集定义

算法原理

带权并查集

树状数组

lowbit操作

树状数组

模板题——单点修改，区间查询

N = 100100
#初始化树状数组 为0
f = [0] * N

#求下标为x的最小区间长度
def lowbit(x):
    return x & (-x)

#树状数组更新函数
def upd(pos,v):#pos：下标 v：值
    #在下标为pos的区间加上v 并且在每个有包含pos的大区间加上v
    #包含当前区间的大区间：在pos的位置上加lowbit(pos)便能得到大区间
    while pos <= n:
        f[pos] += v
        pos += lowbit(pos)

#得到1-pos位置的前缀和
def get(pos):
    res = 0
    while pos > 0:#加上组成pos每一个区间的和
        res += f[pos]
        pos -= lowbit(pos)
    return res

n = int(input())
data = input().split()

for i in range(0,n):
    x = int(data[i])
    #树状数组初始化都为0，需要将原数组每个值通过upd方法将每个值加入树状数组
    upd(i+1,x)

m = int(input())
for _ in range(m):
    opt,a,b = map(int,input().split())
    if opt == 1:
        upd(a,b)#更新
    else:
        #区间[a,b] = [1,b] - [1,a-1]
        print(get(b) - get(a-1))

import os
import sys
N = int(input())
n = list(map(int,input().split()))
m = int(input())
for i in range(m):
  s,a,b = map(int,input().split())
  if s == 1:
    n[a-1] += b
  if s == 2:
    print(sum(n[a-1:b]))

树状数组

模板题——殷老师排队

import os
import sys

def lowbit(x):
  return x & (-x)
def query(x):
  ans = 0
  while x:
    ans += tree[x]
    x -= lowbit(x)
  return ans 
def add(x,y):
  while x <= n:
    tree[x] += y
    x += lowbit(x)

n, m = map(int,input().split())
a =[0] + list(map(int,input().split()))
tree = [0] * (n + 1)
for i in range(1,n+1):
  add(i,a[i])
for i in range(m):
  lt = list(map(int,input().split()))
  if lt[0] == 1:
    x, y = lt[1], lt[2]
    add(x,y - a[x])
    a[x] = y
  else:
    x = lt[1]
    ans = (2 * x - n - 2) * a[x] + query(n) - 2*query(x-1)
    print(ans)

二维树状数组

模板题——

树状数组上二分

模板题——

maxn = 110000
ans = [0] * maxn
tree = [0] * maxn
a = [0] * maxn

def lowbit(x):
    return x & -x

def add(pos, x):
    while pos < maxn:
        tree[pos] += x
        pos += lowbit(pos)

def query(pos):
    res = 0
    while pos > 0:
        res += tree[pos]
        pos -= lowbit(pos)
    return res

n = int(input())
nums = list(map(int, input().strip().split()))
for i in range(1, n + 1):
    a[i] = nums[i - 1]
    add(i, 1)

for i in range(n, 0, -1):
    l, r = 1, n
    while l <= r:
        mid = (l + r) // 2
        if query(mid) < a[i] + 1:
            l = mid + 1
        else:
            r = mid - 1
    ans[i] = r
    add(r, -1)

for i in range(1, n + 1):
    print(ans[i], end=' ')

线段树

线段树-动态开点

例题

struct Tree {
    int l, r, n, ls, rs;
}

void update(int &t, int l, int r, int pos, int n) {
    if (!t) {
        t = ++ cnt;
        tree[t].l = l;
        tree[t].r = r;
    }
    if (l == r) {
        tree[t].n = n;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        update(tree[t].ls, l, mid, pos, n);
    } else {
        update(tree[t].rs, mid + 1, r, pos, n);
    }
}

int getnum(int t, int l, int r) {
    if (!t) {
        return 0;
    }
    if (tree[t].l == l && tree[t].r == r) {
        return tree[t].n;
    }
    int mid = (tree[t].l + tree[t].r) >> 1;
    if (r <= mid) {
        return getnum(tree[t].ls, l, r);
    } else if (l > mid) {
        return getnum(tree[t].rs, l, r);
    } else {
        return getnum(tree[t].ls, l, mid) + getnum(tree[t].rs, mid + 1, r);
    }
}

线段树-标记永久化

案例

void build(int t, int l, int r, int *v) {
    _l[t] = l;
    _r[t] = r;
    if (l == r) {
        _v[t] = v[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(t << 1, l, mid, v);
    build(t << 1 | 1, mid + 1, r, v);
    _v[t] = _v[t << 1] + _v[t << 1 | 1];
}

void update(int t, int l, int r, int k) {
    _v[t] += k * (r - l + 1);
    if (_l[t] == l && _r[t] == r) {
        _laz[t] += k;
        return ;
    }
    int mid = (_l[t] + _r[t]) >> 1;
    if (r <= mid) {
        update(t << 1, l, r, k);
    } else if (l > mid) {
        update(t << 1 | 1, l, r, k);
    } else {
        update(t << 1, l, mid, k);
        update(t << 1 | 1, mid + 1, r, k);
    }
}

int getv(int t, int l, int r, int sum) {
    if (_l[t] == l && _r[t] == r) {
        return _v[t] + sum * (_r[t] - _l[t] + 1);;
    }
    int mid = (_l[t] + _r[t]) >> 1;
    if (r <= mid) {
        return getv(t << 1, l, r, sum + _laz[t]);
    } else if (l > mid) {
        return getv(t << 1 | 1, l, r, sum + _laz[t]);
    } else {
        return getv(t << 1, l, mid, sum + _laz[t])
            + getv(t << 1 | 1, mid + 1, r, sum + _laz[t]);
    }
}

线段树维护矩阵

void build(int t, int l, int r) {
    _l[t] = l;
    _r[t] = r;
    _v[t] = _E;
    if (l == r) {
        return ;
    }
    int mid = (l + r) >> 1;
    build(t << 1, l, mid);
    build(t << 1 | 1, mid + 1, r);
}

void update(int t, int pos, MATRIX &v) {
    if (_l[t] = _r[t]) {
        _v[t] = v;
        return ;
    }
    int mid = (_l[t] + _r[t]) >> 1;
    if (pos <= mid) {
        update(t << 1, pos, v);
    } else {
        update(t << 1 | 1, pos, v);
    }
    _v[t] = _v[t << 1] * _v[t << 1 | 1];
}

MATRIX getv(int t, int l, int r) {
    if (_l[t] == l && _r[t] == r) {
        return _v[t];
    }
    int mid = (_l[t] + _r[t]) >> 1;
    if (r <= mid) {
        return getv(t << 1, l, r);
    } else if (l > mid) {
        return getv(t << 1 | 1, l, r);
    } else {
        return getv(t << 1, l, mid) * getv(t << 1 | 1, mid + 1, r);
    }
}

线段树维护哈希

bs1= []
bs2= []
mod1 = 998244353
mod2 = 19260817
bas = 233
s = []

class asdf:
    def __init__(self, h1, h2, length):
        self.h1 = h1
        self.h2 = h2
        self.length = length
    
    def __add__(self, c):
        return asdf((self.h1 * bs1[c.length] + c.h1) % mod1, (self.h2 * bs2[c.length] + c.h2) % mod2, self.length + c.length)
    
    def __eq__(self, c):
        return self.h1 == c.h1 and self.h2 == c.h2 and self.length == c.length

def build(l, r, rt):
    if l == r:
        s[rt] = asdf(ord(a[l]), ord(a[l]), 1)
        return s[rt]
    s[rt] = build(l, (l + r) // 2, rt * 2) + build((l + r) // 2 + 1, r, rt * 2 + 1)
    return s[rt]

def query(l, r, rt, x, y):
    if x <= l and r <= y:
        return s[rt]
    if y <= (l + r) // 2:
        return query(l, (l + r) // 2, rt * 2, x, y)
    if x > (l + r) // 2:
        return query((l + r) // 2 + 1, r, rt * 2 + 1, x, y)
    return query(l, (l + r) // 2, rt * 2, x, y) + query((l + r) // 2 + 1, r, rt * 2 + 1, x, y)

def modify(l, r, rt, ad, ch):
    if l == r:
        s[rt] = asdf(ord(ch), ord(ch), 1)
        return s[rt]
    if ad <= (l + r) // 2:
        s[rt] = modify(l, (l + r) // 2, rt * 2, ad, ch) + s[rt * 2 + 1]
    else:
        s[rt] = s[rt * 2] + modify((l + r) // 2 + 1, r, rt * 2 + 1, ad, ch)
    return s[rt]

n = int(input())
a = input()
a = "!" + a
bs1.append(1)
bs2.append(1)
for i in range(n):
    bs1.append(bs1[i]*bas%mod1)
    bs2.append(bs2[i]*bas%mod2)
s = [None] * (4 * (n+5))
build(1, n, 1)

q = int(input())
for _ in range(q):
    ls=input().split()
    opt = ls[0]
    if opt == '1':
        ad = int(ls[1])
        ch = ls[2]
        modify(1, n, 1, int(ad), ch)
    else:
        l1 = int(ls[1])
        r1 = int(ls[2])
        l2 = int(ls[3])
        r2 = int(ls[4])
        x = query(1, n, 1, l1, r1)
        y = query(1, n, 1, l2, r2)
        if x == y:
            print("YES")
        else:
            print("NO")

可持久化线段树

可持久化线段树

struct NODE {
    int v, ls, rs;
}

struct SEGTREE {
    int cnt = 0;
    int root[MAXN << 5];
    NODE node[MAXN << 5];
}

void SEGTREE::update(int _t, int &t, int l, int r, int pos, int k) {
    if (!t) {
        t = ++cnt;
        node[t].v = node[_t].v;
    }
    if (l == r) {
        node[t].v += k;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        node[t].rs = node[_t].rs;
        update(node[_t].ls, node[t].ls, l, mid, pos, k);
    } else {
        node[t].ls = node[_t].ls;
        update(node[_t]).rs, node[t].rs, mid + 1, r, pos, k);
    }
    node[t].v = node[node[t].ls].v + node[node[t].rs].v;
}

int SEGTREE::getV(int t, int _l, int _r, int l, int r) {
    if (!t) {
        return 0;
    }
    if (l == _l && r == _r) {
        return node[t].v;
    }
    int mid = (_l + _r) >> 1;
    if (r <= mid) {
        return getV(node[t].ls, _l, mid, l, r);
    } else if (l > mid) {
        return getV(node[t].rs, mid + 1, _r, l, r);
    } else {
        return getV(node[t].ls, _l, mid, l, mid)
            + getV(node[t].rs, mid + 1, _r, mid + 1, r);
    }
}

模板题——区间第k小

#include<bits/stdc++.h>
using namespace std;
#define lc(x) tr[x].l
#define rc(x) tr[x].r
const int N=2e5+6;
int n,m,a[N],b[N];
struct Node {
 int l,r,s;//左右儿子，该节点在值域中的个数
}tr[N*20];
int idx,root[N];
void build(int &x,int l,int r)
{
    x=++idx;
    if(l==r)return ;
    int mid=(l+r)>>1;
    build(lc(x),l,mid);
    build(rc(x),mid+1,r);
}
void update(int x,int &y,int l,int r,int v)
{
    y=++idx;
    tr[y]=tr[x];
    tr[y].s++;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(v<=mid)
        update(lc(x),lc(y),l,mid,v);
    else
        update(rc(x),rc(y),mid+1,r,v);
}
int query(int x,int y,int l,int r,int k)
{
    if(l==r)return l;
    int mid=(l+r)>>1;
    int s=tr[lc(y)].s-tr[lc(x)].s;
    if(k<=s)
        return query(lc(x),lc(y),l,mid,k);
    else 
        return query(rc(x),rc(y),mid+1,r,k-s);
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int bn=unique(b+1,b+1+n)-b-1;
    build(root[0],1,bn);
    for(int i=1;i<=n;i++)
    {
        int id=lower_bound(b+1,b+1+bn,a[i])-b;
        update(root[i-1],root[i],1,bn,id);
    }
    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        int id=query(root[l-1],root[r],1,bn,k);
        cout<<b[id]<<'\n';
    }
    return 0;
}

图论

单源最短路

Floyd

模板题—— 蓝桥公园

import sys
input=sys.stdin.readline
n,m,q=map(int,input().split())
inf=int(1e18)
dp=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  dp[i][i]=0
for i in range(1,m+1):
  u,v,w=map(int,input().split())
  dp[u][v]=dp[v][u]=min(dp[u][v],w)
#Floyd 模板
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

for i in range(1,n+1):
    for j in range(1,n+1):
      if dp[i][j]==inf:
        dp[i][j]=-1

for _ in range(q):
  s,e=map(int,input().split())
  print(dp[s][e])

# Floyd 算法  多个起点--多个终点  多源最短路算法（多对多）
# 最简单的最短路径算法
# 存图:最简单的矩阵存图
# 效率不高，不能用于大图

# 动态规划：求图上两点i,j之间的最短距离，按‘从小图到全图’的步骤，在逐步扩大图的过程中计算和更新最短路
# 定义状态：dp[k][i][j]: i,j,k是点的编号，范围1--n
# 状态dp[k][i][j]表示在包含1--k点的子图上，点对i,j之间的最短路
# 状态转移方程 从子图1-k-1 扩展到子图 1-k
# dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])
# 初始值：i,j直连 就是他们的边长； 若不直连，赋值为无穷大 / 0x3f3f3f3f3f3f3f3f
# 滚动数组优化：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
#                           不经过k     经过k
# for k in range(1,n+1):
# for i in range(1,n+1):
# for j in range(1,n+1):
# dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
# 只能用于n<300 的小规模图


def floyd():
    global dp
    for k in range(1,n+1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
# 蓝桥公园
# n个点 m条边 q次查询
n,m,q=map(int,input().split())
INF = 0x3f3f3f3f3f3f3f3f
dp=[[INF for _ in range(n+50)] for _ in range(n+50)]
# 记录路径
for i in range(1,m+1):
    u,v,w=map(int,input().split())
    dp[u][v]=dp[v][u]=min(dp[u][v],w)
floyd()
for _ in range(q):
    start,end=map(int,input().split())
    # 无法到达
    if dp[start][end]==INF:
        print(-1)
    # 起点终点相同
    elif start==end:
        print(0)
    else:
        print(dp[start][end])

# 1-12

import os
import sys

# 请在此输入您的代码
N, M, Q = map(int, input().split())
weight = [[0 if i == j else sys.maxsize for i in range(N + 1) ] for j in range(N + 1)]  # 领接矩阵
for i in range(M):
    u, v, w = map(int, input().split())
    weight[u][v] = min(weight[u][v], w)
    weight[v][u] = weight[u][v]
for k in range(1, N + 1):  # N次递推
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):  # 更新最小值
                weight[i][j] = min(weight[i][j], weight[i][k] + weight[k][j])
                weight[j][i] = weight[i][j]

for i in range(Q):
    st, ed = map(int, input().split())
    t = weight[st][ed]
    if t == sys.maxsize:
        print(-1)
    else:
        print(t)

模板题——城市间的交易

import os
import sys

# 请在此输入您的代码
# 8336 城市间的交易
INF =1e18
n, m = map(int, input().split())
# 产量、成本和售价
a, p, s = [0] * (n+1), [0] * (n+1), [0] * (n+1)
f = [[INF] * (n+1) for i in range(n+1)]
g = [[0] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    a[i], p[i], s[i] = map(int, input().split())
# 邻接矩阵初始化
for i in range(1, m+1):
    u, v, w = map(int, input().split())
    f[u][v] = f[v][u] = min(f[u][v], w)
for i in range(1, n+1):
    f[i][i] = 0

# Floyd
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            f[i][j] = min(f[i][j], f[i][k]+f[k][j])
# g[i][j]表示城市i的物品运输到城市j可得到的利润 = 城市j的售价 - 城市i的成本 - 从i到j的运输成本
ans = 0
for i in range(1, n+1):
    # 求每个城市的利润
    cnt = 0
    for j in range(1, n+1):
        g[i][j] = s[j] - p[i] - f[i][j]
        cnt = max(cnt, g[i][j])
    ans += a[i] * cnt
print(ans)

import os
import sys
n,m=map(int,input().split())
res=[]
for _ in range(n):
  a,p,s=map(int,input().split())
  res.append((a,p,s))
inf=int(1e10)
path=[[inf]*(n+1) for _ in range(n+1)]
for _ in range(m):
  u,v,w=map(int,input().split())
  path[u][v]=path[v][u]=min(w,path[u][v])
for i in range(1,1+n):
  path[i][i]=0

for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      path[i][j]=min(path[i][j],path[i][k]+path[k][j])
re=0
for i in range(1,n+1):
  result=0
  for j in range(1,n+1):
    if path[i][j]!=inf:
       result=max(result,res[j-1][2]*res[i-1][0]-res[i-1][0]*res[i-1][1]-path[i][j]*res[i-1][0])
  re+=result
print(re)

Dijkstra

模板题——蓝桥王国

import os
import sys

# 请在此输入您的代码
# 1122_蓝桥王国_Dijkstra算法
from queue import PriorityQueue  # 导入优先队列
from collections import deque

INF = 1e18


def dijkstra(s):
    # 返回从s出发到所有点的最短路
    # d[i]表示从s到i的最短路
    d = [INF] * (n + 1)
    # vis[i]表示是否出队列（注：与传统BFS不同）
    vis = [0] * (n + 1)
    q = PriorityQueue()

    # 1.将起点入队列，更新距离
    d[s] = 0
    # 将距离放在前面，才能对距离使用优先队列
    q.put((d[s], s))  # 入队用put()
    # 当队列非空
    while not q.empty():  # 或者写为： while len(q.queue) != 0:
        dis, u = q.get()
        # 每个点只有第一次出队列是有用的
        if vis[u]: continue
        vis[u] = 1  # 出队列打标记
        # 对于从u出发，到达v，权重为w的边
        for v, w in G[u]:
            if d[v] > d[u] + w:
                d[v] = d[u] + w
                q.put((d[v], v))
    for i in range(1, n + 1):
        if d[i] == INF:
            d[i] = -1
    # d.pop(0)
    return d[1::] # 从1到最后


# 皇宫编号为1
# 输入
n, m = map(int, input().split())
G = [[] for i in range(n + 1)]  # 图的存储：邻接表。此题N为10^5，不能用邻接矩阵存图

for i in range(m):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
print(*dijkstra(1)) # 列表前面加星号作用是将列表解开（unpacke）成多个独立的参数，传入函数。

模板题——混境之地3

import os
import sys
# 3818 混境之地  Dijkstra
from queue import PriorityQueue
# 数据较大时可以进行如下优化
import sys
input = sys.stdin.readline
INF = 1e18
def get(c):
    if c == '.':
        return 0
    else:
        s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
        for i in range(len(s)):
            if c == s[i]:
                return i + 1
        # return ord(c) - ord('A') + 1
def dijkstra():
    d = [[INF] * m for _ in range(n)]
    vis = [[0] * m for _ in range(n)]
    q = PriorityQueue()  # 创建优先队列
    # 1.将起点塞入队列
    d[x1][y1] = 0
    q.put((d[x1][y1], x1, y1))
    # 2.当队列非空
    while not q.empty():
        dis, x, y = q.get()
        if x == x2 and y == y2:
            return dis
        # 每个点只有第一次出队列是有用的
        if vis[x][y]:
            continue
        vis[x][y] = 1  # 出队列打标记
        for d elta_x, delta_y in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            xx, yy = x + delta_x, y + delta_y
            # 判断未越界、未标记、非障碍物
            if 0 <= xx < n and 0 <= yy < m and vis[xx][yy] == 0 and Map[xx][yy] != "#":
                if d[xx][yy] > d[x][y] + get(Map[xx][yy]):  # 写一个get函数获取权重
                    d[xx][yy] = d[x][y] + get(Map[xx][yy])
                    q.put((d[xx][yy], xx, yy))
    return INF
# 输入
n, m = map(int, input().split())  # 地图大小
x1, y1, x2, y2 = map(int, input().split())  # 起始点坐标
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
# 地图
Map = [input() for i in range(n)]
e = int(input())  # 剩余能量
# 如果能量支撑到达终点，返回Yes，否则，返回No.
if e >= dijkstra():  # 不传参，使用全局变量
    print('Yes')
else:
    print('No')

最小生成树

Kruskal

模板题——繁忙的都市

def kruskal():
    # 初始化
    n, m = map(int, input().split())
    Map = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        Map.append([w, u, v])  # 注意第一个参数是边权
    Map.sort()

    # 并查集
    p = list(range(n+1))
    def root(x):
        if x != p[x]:
            p[x] = root(p[x])
        return p[x]

    # 非连环时更新
    _sum, _max = 0, 0
    for w, u, v in Map:
        root_u = root(u)
        root_v = root(v)
        if root_u != root_v:
            p[root_u] = root_v
            _sum += 1
            _max = max(_max, w)
    return _sum, _max
print(*kruskal())

Prim

模板题——繁忙的都市

import os
import sys
n,m=map(int,input().split())
e=[]
for  _ in range(m):
  u,v,w=map(int,input().split())
  e.append((w,u,v))
#边按照权重进行排序
e.sort()
#需要一个并查集
p=list(range(n+1))

def findroot(x):
  if x==p[x]:return x
  else:
    p[x]=findroot(p[x])
    return p[x]
ans=0
#进行遍历所有的边，进行合并：
for w,u,v in e:
  #只要u和v不在同一集合内就可以进行合并：
  rootu=findroot(u)
  rootv=findroot(v)
  if rootu!=rootv:
    p[rootu]=rootv
    ans=max(ans,w)
print(n-1,ans)

最近共同祖先

最近公共祖先

模板题——最近公共祖先LCA查询

import os
import sys

#设置deep数组表示深度。
#front数组，表示节点u,前2**i层的爹是谁？？？
n=int(input())
tree=[[] for _ in range(n+1)]
fornt=[[0]*(21) for _ in range(n+1)]#如果你是0你就是孤儿。
deep=[0]*(n+1)#0节点没有层数。
for i in range(n-1):
  u,v=map(int,input().split())
  tree[u].append(v)

def dfs(er,die):
  if die==0:
    deep[er]=1#这是第一层,同时，第一层也没有爹啊，也不需要更新如何层数相关节点。

  else:
    deep[er]=deep[die]+1#更新层数。
    fornt[er][0]=die#上一层的点，就是die。
    for cc in range(1,21):
      if fornt[fornt[er][cc-1]][cc-1]!=0:

        fornt[er][cc]=fornt[fornt[er][cc-1]][cc-1]
        #倍增法。2**i层之上的点=
        #2**(cc-1)上面的点的上面2**(cc-1)的点。就，无限套娃。
  
  for i in tree[er]:
    dfs(i,er)#儿子变成新的爹。
dfs(1,0)#儿子是根，爹不存在。

def find(x,y):
  #第一步，拉升。将x拉到和y一个水平。一开始走2**20步，太大，就走2**19步，然后走一半，再走一半
  #就像那个乌龟与跑步哥一样。二进制原理使得这个步数遍历后一定是一个高度。
  for i in range(20,-1,-1):
    if deep[fornt[x][i]]>=deep[y] and fornt[x][i]!=0:
      x=fornt[x][i]#自动判断能走不能走，能走则走一大步。x提升到别的节点。

  #此时提升必定一样了。
  if x==y:
    return x#原来你就是我爹！
  
  else:#不是？我们再度提升吧！神明！
    for i in range(20,-1,-1):
      if fornt[x][i]!=fornt[y][i] and fornt[x][i]!=0 and fornt[y][i]!=0:#相等反而不能决定什么，因为可能不是最近的公共祖先
        x=fornt[x][i]
        y=fornt[y][i]
    return fornt[y][0]#最后，y上面的就是自己的公共祖先。
q=int(input())
for i in range(q):
  x,y=map(int,input().split())
  if deep[x]<deep[y]:#我们设x是深节点。
    x,y=y,x
  print(find(x,y))