Java
函数
// inc=true -> 断言满足条件时l向mid收拢
static long bisect(long l, long r, Predicate<Long> predicate, boolean inc) {
long res = -1;
while (l <= r) {
long mid = (l + r) >>> 1;
if (predicate.test(mid)) {
res = mid;
long ignore = inc ? (l = mid + 1) : (r = mid - 1);
} else {
long ignore = inc ? (r = mid - 1) : (l = mid + 1);
}
}
return res;
}
static double bisect_double(double l, double r, Predicate<Double> predicate, boolean inc) {
double res = -1;
while (l + 1e-8 < r) {
double mid = (l + r) / 2.0;
if (predicate.test(mid)) {
res = mid;
double ignore = inc ? (l = mid + 1) : (r = mid - 1);
} else {
double ignore = inc ? (r = mid - 1) : (l = mid + 1);
}
}
return res;
}
// min
static<T extends Comparable<T>> T min(T... args) {
return min(Comparable::compareTo, args);
}
static<T> T min(Comparator<T> cmp, T... args) {
return Arrays.stream(args).min(cmp).get();
}
// max
static<T extends Comparable<T>> T max(T... args) {
return min(Comparator.reverseOrder(), args);
}
static<T> T max(Comparator<T> cmp, T... args) {
return Arrays.stream(args).min(cmp).get();
}
// 通项公式求和
// 等差
static long apSum(int a1, int d, int n) {
return (long) n * a1 + (long) n * (n - 1) / 2 * d;
}
// 等比
static int pow(long a, long n, int MOD) {
a %= MOD;
int res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res = (int) (a * res % MOD);
}
a = a * a % MOD;
n >>= 1;
}
return res;
}
static int inv(long x, int MOD) {
return pow(x, MOD - 2, MOD);
}
static long gpSum(int a1, int q, int n, int MOD) {
return (long) a1 * ((1 - pow(q, n, MOD) + MOD) % MOD) % MOD * inv((1 - q + MOD) % MOD, MOD) % MOD;
}
// 枚举子集
for (int s = state; s > 0; s = (s - 1) & state) {
// t从小到大
int t = state ^ s;
}
动态规划
01背包问题
// 最大价值
static long _01BagMaxValue(int[][] monos, int V) {
int n = monos.length;
long[][] dp = new long[n + 5][V + 5];
for (int i = 1; i <= n; ++i) {
int weight = monos[i - 1][0], value = monos[i - 1][1];
for (int j = 0; j <= V; ++j) {
if (j < weight) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value);
}
}
}
return dp[n][V];
}
// 最大价值方案数
static int _01BagMaxValueWays(int[][] monos, int V, int MOD) {
int n = monos.length;
long[][] dp = new long[n + 5][V + 5];
int[][] cnt = new int[n + 5][V + 5];
Arrays.fill(cnt[0], 1);
for (int i = 1; i <= n; ++i) {
int weight = monos[i - 1][0], value = monos[i - 1][1];
for (int j = 0; j <= V; ++j) {
if (j < weight) {
cnt[i][j] = cnt[i - 1][j];
dp[i][j] = dp[i - 1][j];
} else {
long notSelect = dp[i - 1][j], select = dp[i - 1][j - weight] + value;
if (notSelect > select) {
cnt[i][j] = cnt[i - 1][j];
dp[i][j] = notSelect;
} else if (notSelect < select) {
cnt[i][j] = cnt[i - 1][j - weight];
dp[i][j] = select;
} else {
cnt[i][j] = (cnt[i - 1][j] + cnt[i - 1][j - weight]) % MOD;
dp[i][j] = notSelect;
}
}
}
}
return cnt[n][V];
}
// 背包容量为V且价值最大的字典序最小的具体方案
static List<Integer> _01BagMaxValueConcretePlan(int[][] monos, int V) {
int n = monos.length;
long[][] dp = new long[n + 5][V + 5];
for (int i = n; i >= 1; --i) {
int weight = monos[i - 1][0], value = monos[i - 1][1];
for (int j = 0; j <= V; ++j) {
if (j < weight) {
dp[i][j] = dp[i + 1][j];
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - weight] + value);
}
}
}
List<Integer> plan = new ArrayList<>();
int remainV = V;
for (int i = 1; i <= n; ++i) {
int weight = monos[i - 1][0], value = monos[i - 1][1];
if (remainV >= weight && dp[i][remainV] == dp[i + 1][remainV - weight] + value) {
plan.add(i - 1);
remainV -= weight;
}
}
return plan;
}
数位dp
前缀和
long[][] dp = new long[20][100];
int[] digit = new int[20];
long dfs(int pos, boolean lead, boolean limit, int state) {
if (pos == 0) {
return lead ? 0 : 1;
}
if (!lead && !limit && dp[pos][state] > -1) {
return dp[pos][state];
}
long res = 0;
int up = limit ? digit[pos] : 9;
for (int i = 0; i <= up; ++i) {
res += dfs(pos - 1, lead && (i == 0), limit && (i == up), state);
}
if (!lead && !limit) {
dp[pos][state] = res;
}
return res;
}
long solve(long x) {
int len = 0;
while (x > 0) {
digit[++len] = (int) (x % 10);
x /= 10;
}
for (long[] dpi : dp) {
Arrays.fill(dpi, -1);
}
return dfs(len, true, true, 0);
}
区间(前缀和不满足时)
long[][] dp = new long[20][100];
int[] downdigit = new int[20], updigit = new int[20];
long dfs(int pos, boolean lead, boolean downlimit, boolean uplimit, int state) {
if (pos == 0) {
return lead ? 0 : 1;
}
if (!lead && !downlimit && !uplimit && dp[pos][state] > -1) {
return dp[pos][state];
}
long res = 0;
int down = downlimit ? downdigit[pos] : 0, up = uplimit ? updigit[pos] : 9;
for (int i = down; i <= up; ++i) {
res += dfs(pos - 1, lead && (i == 0), downlimit && (i == down), uplimit && (i == up), state);
}
if (!lead && !downlimit && !uplimit) {
dp[pos][state] = res;
}
return res;
}
long solve(int l, int r) {
toArray(downdigit, l);
toArray(updigit, r);
return dfs(18, true, true, true, 0);
}
void toArray(int[] digit, long x) {
int len = 0;
while (x > 0) {
digit[++len] = (int) (x % 10);
x /= 10;
}
for (long[] dpi : dp) {
Arrays.fill(dpi, -1);
}
}
数学
组合数
\[C_n^r=\frac{A_n^r}{A_r^r}=\frac{n(n-1)(n-2)\cdots(n-r+1)}{r!}
\]
\]
\(1.\)有\(n\)种物品，每种物品分别有\(a_1,a_2, \cdots ,a_n\)个，不同的排列方案数为\(\frac{(\sum_{i=1}^n a_i)!}{\prod_{i=1}^n a_i}\)。
\(2.\)小球放盒问题
class Combination {
static int MAXN = (int) 1e5 + 5, MOD = (int) 1e9 + 7;
static int[] fact = new int[MAXN], ifact = new int[MAXN];
static {
fact[0] = 1;
for (int i = 1; i < MAXN; ++i) {
fact[i] = (int) ((long) fact[i - 1] * i % MOD);
}
ifact[MAXN - 1] = inv(fact[MAXN - 1]);
for (int i = MAXN - 2; i >= 0; --i) {
ifact[i] = (int) ((long) ifact[i + 1] * (i + 1) % MOD);
}
}
static int pow(long a, long n) {
a %= MOD;
int res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res = (int) (a * res % MOD);
}
a = a * a % MOD;
n >>= 1;
}
return res;
}
static int inv(long x) {
return pow(x, MOD - 2);
}
static int C(int n, int r) {
if (n - r < 0) {
return 0;
}
return (int) ((long) fact[n] * ifact[r] % MOD * ifact[n - r] % MOD);
}
}
运算
static long gcd(long x, long y) {
return y == 0 ? x : gcd(y, x % y);
}
static long lcm(long x, long y) {
return x / gcd(x, y) * y;
}
static long pow(long a, long n) {
long res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res *= a;
}
a *= a;
n >>= 1;
}
return res;
}
static int pow(long a, long n, int MOD) {
a %= MOD;
int res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res = (int) (a * res % MOD);
}
a = a * a % MOD;
n >>= 1;
}
return res;
}
static int inv(long x, int MOD) {
return pow(x, MOD - 2, MOD);
}
素数
判断素数
static boolean isPrime(int x) {
if (x == 2 || x == 3) {
return true;
}
if ((x % 6 != 1 && x % 6 != 5) || x == 1) {
return false;
}
for (int i = 5; i * i <= x; i += 6) {
if (x % i == 0 || x % (i + 2) == 0) {
return false;
}
}
return true;
}
素数筛
static int MAXN = (int) 1e6 + 5;
static boolean[] np = new boolean[MAXN];
static List<Integer> primes = new ArrayList<>();
static {
for (int i = 2; i < MAXN; ++i) {
if (!np[i]) {
primes.add(i);
}
for (int prime : primes) {
if (i * prime >= N) {
break;
}
np[i * prime] = true;
if (i % prime == 0) {
break;
}
}
}
}
分解质因数
static List<Pair<Integer, Integer>>[] factorize(int n) {
List<Pair<Integer, Integer>>[] d = new List[n + 5];
Arrays.setAll(d, di -> factorize0(di));
return d;
}
static List<Pair<Integer, Integer>> factorize0(int x) {
List<Pair<Integer, Integer>> d = new ArrayList<>();
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
int cnt = 0;
while (x % i == 0) {
++cnt;
x /= i;
}
d.add(new Pair<>(i, cnt));
}
}
if (x > 1) {
d.add(new Pair<>(x, 1));
}
return d;
}
求约数
static List<Integer>[] divide(int n) {
List<Integer>[] d = new List[n + 5];
Arrays.setAll(d, di -> divide0(di));
return d;
}
static List<Integer> divide0(int x) {
List<Integer> d = new ArrayList<>();
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
d.add(i);
d.add(x / i);
}
}
d.sort(Comparator.comparingInt(a -> a));
return d;
}
计算几何
// 关于两点距离等函数可以参考java.awt.geom包下的内容以及java.awt.geom.Point2D类
import java.awt.geom.*;
static double eps = 1e-6;
// 计算两点中点
static Point2D.Double middle(Point2D.Double A, Point2D.Double B) {
return new Point2D.Double((A.x + B.x) / 2, (A.y + B.y) / 2);
}
// 根据两点和半径求出一个圆心, 要求另一个圆心只需要交换A和B
static Point2D.Double theCenterOfACircle(Point2D.Double A, Point2D.Double B, double r) {
double d = A.distance(B);
double cs = (A.x - B.x) / d, sn = (A.y - B.y) / d;
double ca = d / (2 * r), sa = Math.sqrt(1 - ca * ca);
double midx = (cs * ca - sn * sa) * r + B.x;
double midy = (cs * sa + sn * ca) * r + B.y;
return new Point2D.Double(midx, midy);
}
// 判断点是否在多边形内部
static boolean isPointInPolygon(List<Point2D.Double> polygon, Point2D.Double point) {
GeneralPath p = new GeneralPath();
Point2D.Double first = polygon.get(0);
p.moveTo(first.x, first.y);
polygon.remove(0);
for (Point2D.Double d : polygon) {
p.lineTo(d.x, d.y);
}
p.lineTo(first.x, first.y);
p.closePath();
return p.contains(point);
}
/**
* 浮点数比较大小
* x == y: 0
* x < y: 1
* x > y: -1
* x <= y: <= 0
* x >= y: >= 0
*/
static int dcmp(double x, double y) {
return Math.abs(x - y) <= eps ? 0 : Double.compare(x, y);
}
图论
最短路
interface Zarya {
long apply(int u, int v, int w, long d);
}
static long INF = Long.MAX_VALUE >> 1;
static long[] dijkstra(List<int[]>[] e, int s, Zarya Z) {
boolean[] vis = new boolean[e.length];
long[] d = new long[e.length];
Arrays.fill(d, INF);
Queue<Pair<Integer, Long>> q = new PriorityQueue<>(Comparator.comparingLong(Pair::getValue));
q.offer(new Pair<>(s, d[s] = 0));
while (!q.isEmpty()) {
int u = q.poll().getKey();
if (vis[u]) {
continue;
}
vis[u] = true;
for (int[] edge : e[u]) {
int v = edge[0], w = edge[1];
long fromU = Z.apply(u, v, w, d[u]);
if (fromU < d[v]) {
q.offer(new Pair<>(v, d[v] = fromU));
}
}
}
return d;
}
最小生成树
static int find(int[] fa, int x) {
return fa[x] == x ? x : (fa[x] = find(fa, fa[x]));
}
static long kruskal(List<int[]> edges, int n) {
edges.sort(Comparator.comparingInt(o -> o[2]));
int[] fa = IntStream.range(0, n).toArray();
int cnt = 0;
long ans = 0;
for (int[] edge : edges) {
if (cnt == n - 1) {
break;
}
int x = find(fa, edge[0]), y = find(fa, edge[1]), w = edge[2];
if (x != y) {
++cnt;
ans += w;
fa[x] = y;
}
}
return ans;
}
二分图
二分图最大匹配
static boolean dfs(List<Integer>[] e, int[] vis, int[] match, int u, int sgn) {
if (vis[u] == sgn) {
return false;
}
vis[u] = sgn;
for (int v : e[u]) {
if (match[v] == -1 || dfs(e, vis, match, match[v], sgn)) {
match[v] = u;
return true;
}
}
return false;
}
static int hungary(List<Integer>[] e, int n) {
int ans = 0;
int[] vis = IntStream.range(0, n).map(x -> -1).toArray();
int[] match = IntStream.range(0, n).map(x -> -1).toArray();
for (int i = 0; i < n; ++i) {
if (dfs(e, vis, match, i, i)) {
++ans;
}
}
return ans;
}
二分图判断
static boolean dfs(List<Integer>[] e, int[] col, int u, int c) {
col[u] = c;
for (int v : e[u]) {
if (col[v] > 0) {
if (col[v] == c) {
return false;
}
} else if (!dfs(e, v, 3 - c)) {
return false;
}
}
return true;
}
static boolean check(List<Integer>[] e, int n) {
int[] col = new int[n];
for (int i = 0; i < n; ++i) {
if (col[i] > 0) {
continue;
}
if (!dfs(e, col, i, 1)) {
return false;
}
}
return true;
}
欧拉路径(一笔画问题)
static void dfs(List[] e, List<Integer> path, int u) {
while (!e[u].isEmpty()) {
int v = path.get(path.size() - 1);
path.remove(path.size() - 1);
dfs(e, path, v);
}
path.add(u);
}
// s为入度为0的点, 没有则任意取
static List<Integer> euler(List[] e, int s) {
List<Integer> path = new ArrayList<>();
dfs(e, path, s);
Collections.reverse(path);
return path;
}
网络流
最大流
class Edge {
int to, next, flow;
Edge(int _to, int _next, int _flow) {
to = _to;
next = _next;
flow = _flow;
}
}
class MFNet {
int INF = Integer.MAX_VALUE >> 1;
// 链式前向星存储图结构
int[] head;
Edge[] e;
int index = 1;
// 最大流
int[] depth, cur;
MFNet(int n, int m) {
head = new int[n + 5];
e = new Edge[(m + 5) << 1];
depth = new int[n + 5];
cur = new int[n + 5];
}
void add(int u, int v, int flow) {
e[++index] = new Edge(v, head[u], flow);
head[u] = index;
}
void addedge(int u, int v, int flow) {
add(u, v, flow);
add(v, u, 0);
}
boolean bfs(int s, int t) {
cur[s] = head[s];
Arrays.fill(depth, INF);
depth[s] = 0;
Queue<Integer> q = new ArrayDeque<>(List.of(s));
while (!q.isEmpty()) {
int u = q.poll();
if (u == t) {
return true;
}
for (int i = head[u]; i > 0; i = e[i].next) {
int v = e[i].to, w = e[i].flow;
if (depth[v] == INF && w > 0) {
cur[v] = head[v];
depth[v] = depth[u] + 1;
q.offer(v);
}
}
}
return false;
}
int dfs(int u, int t, int limit) {
if (limit == 0 || u == t) {
return limit;
}
int flow = 0;
for (int i = cur[u]; i > 0; i = e[i].next) {
cur[u] = i;
int v = e[i].to, w = e[i].flow;
if (depth[v] == depth[u] + 1 && w > 0) {
int k = dfs(v, t, Math.min(limit, w));
flow += k;
limit -= k;
e[i].flow -= k;
e[i ^ 1].flow += k;
if (limit == 0) {
break;
}
}
}
return flow;
}
int grow(int s, int t) {
int maxflow = 0;
while (bfs(s, t)) {
maxflow += dfs(s, t, INF);
}
return maxflow;
}
}
最小费用最大流
class Edge {
int to, next, flow;
long cost;
Edge(int _to, int _next, int _flow, long _cost) {
to = _to;
next = _next;
flow = _flow;
cost = _cost;
}
}
class MCMFNet {
long INF = Long.MAX_VALUE >> 1;
// 链式前向星存储图结构
int[] head;
Edge[] e;
int index = 1;
// spfa
long[] d;
boolean[] vis;
// 最小费用和最大流
long mincost;
int maxflow;
int[] cur;
MCMFNet(int n, int m) {
head = new int[n + 5];
e = new Edge[(m + 5) << 1];
d = new long[n + 5];
vis = new boolean[n + 5];
}
void add(int u, int v, int flow, int cost) {
e[++index] = new Edge(v, head[u], flow, cost);
head[u] = index;
}
void addedge(int u, int v, int flow, int cost) {
add(u, v, flow, cost);
add(v, u, 0, -cost);
}
boolean spfa(int s, int t) {
Arrays.fill(d, INF);
d[s] = 0L;
Queue<Integer> q = new ArrayDeque<>(List.of(s));
while (!q.isEmpty()) {
int u = q.poll();
vis[u] = false;
for (int i = head[u]; i > 0; i = e[i].next) {
int v = e[i].to;
long w = e[i].cost;
if (e[i].flow > 0 && d[u] + w < d[v]) {
d[v] = d[u] + w;
if (!vis[v]) {
vis[v] = true;
q.offer(v);
}
}
}
}
return d[t] != INF;
}
int dfs(int u, int t, long limit) {
if (limit == 0L || u == t) {
return limit;
}
vis[u] = true;
int flow = 0;
for (int i = head[u]; i > 0; i = e[i].next) {
cur[u] = i;
int v = e[i].to, w = e[i].flow;
if (!vis[v] && e[i].flow > 0 && d[u] + e[i].cost == d[v]) {
int k = dfs(v, t, Math.min(limit, w));
if (k == 0) {
continue;
}
flow += k;
limit -= k;
e[i].flow -= k;
e[i ^ 1].flow += k;
mincost += e[i].cost * k;
if (limit == 0) {
break;
}
}
}
vis[u] = false;
return flow;
}
Pair<Long, Integer> grow(int s, int t) {
while (spfa(s, t)) {
cur = Arrays.copyOf(head, head.length);
maxflow += dfs(s, t, INF);
}
return new Pair<>(mincost, maxflow);
}
}
数据结构
并查集
简洁版
class UnionFindSet {
int[] fa;
UnionFindSet(int _n) {
fa = IntStream.range(0, _n).toArray();
}
int find(int x) {
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y) {
fa[find(x)] = find(y);
}
}
不简洁版
class UnionFindSet {
int n;
int[] fa, sz;
UnionFindSet(int _n) {
n = _n;
fa = IntStream.range(0, n).toArray();
sz = IntStream.range(0, n).map(x -> 1).toArray();
}
int find(int x) {
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
boolean merge(int x, int y) {
if ((x = find(x)) == (y = find(y))) {
return false;
}
fa[x] = y;
sz[y] += sz[x];
--n;
return true;
}
int sizeOf(int x) {
return sz[find(x)];
}
boolean isRoot(int x) {
return x == find(x);
}
boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}
字典树
class Trie {
class Node {
Node[] e = new Node[26];
boolean isEnd;
}
Node root = new Node();
void insert(String s) {
Node u = root;
for (char c : s.toCharArray()) {
int v = c - 'a';
if (u.e[v] == null) {
u.e[v] = new Node();
}
u = u.e[v];
}
u.isEnd = true;
}
void query(String s) {
Node u = root;
for (char c : s.toCharArray()) {
int v = c - 'a';
if (u.e[v] == null) {
break;
}
u = u.e[v];
}
}
}
一维树状数组
树状数组详解 – Xenny – 博客园 (cnblogs.com)
高级树状数组——区间修改区间查询、二维树状数组 – 胡小兔 – 博客园 (cnblogs.com)
class FenwickTree {
int n;
long[] sum, isum;
FenwickTree(int _n) {
n = _n;
sum = new long[n + 5];
isum = new long[n + 5];
}
void add(int l, int r, int k) {
add(l, k);
add(r + 1, -k);
}
void add(int p, int k) {
for (int i = p; i <= n; i += i & -i) {
sum[i] += k;
isum[i] += (long) k * p;
}
}
long sum(int l, int r) {
return sum(r) - sum(l - 1);
}
long sum(int p) {
long res = 0;
for (int i = p; i > 0; i -= i & -i) {
res += sum[i] * (p + 1) - isum[i];
}
return res;
}
}
二维树状数组
class FenwickTree2D {
int n, m;
long[][] t1, t2, t3, t4;
FenwickTree2D(int _n, int _m) {
n = _n;
m = _m;
t1 = new long[n + 5][m + 5];
t2 = new long[n + 5][m + 5];
t3 = new long[n + 5][m + 5];
t4 = new long[n + 5][m + 5];
}
void add(int x1, int y1, int x2, int y2, int k) {
add(x1, y1, k);
add(x1, y2 + 1, -k);
add(x2 + 1, y1, -k);
add(x2 + 1, y2 + 1, k);
}
void add(int x, int y, int k) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
t1[i][j] += k;
t2[i][j] += (long) k * x;
t3[i][j] += (long) k * y;
t4[i][j] += (long) k * x * y;
}
}
}
long sum(int x1, int y1, int x2, int y2) {
return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}
long sum(int x, int y) {
long res = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
res += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
}
}
return res;
}
}
ZKW线段树
307. 区域和检索 – 数组可修改 – 力扣（LeetCode）
class Node {
int l, r, mid, len;
Node(int _l, int _r) {
l = _l;
r = _r;
mid = (l + r) >> 1;
len = r - l + 1;
}
void update(int k) {
}
void merge(Node left, Node right) {
}
}
class STree {
int m = 1; // [1, m-1]非叶子节点, [m, 2*m-1]叶子节点
Node[] tree;
STree(int _n, int... args) {
while (m < _n + 2) {
m <<= 1;
}
tree = new Node[m << 1];
for (int i = 0; i < m; ++i) {
tree[i + m] = new Node(i, i);
}
if (args.length > 0) {
// 叶子节点初始化
for (int i = 1; i <= _n; ++i) {
// tree[i + m], args[i - 1]
}
}
for (int i = m - 1; i >= 1; --i) {
tree[i] = new Node(tree[i << 1].l, tree[i << 1 | 1].r);
tree[i].merge(tree[i << 1], tree[i << 1 | 1]);
}
}
void modify(int i, int k) {
for (i += m; i >= 1; i >>= 1) {
}
}
int query(int l, int r) {
for (l += m - 1, r += m + 1; (l ^ r) != 1; l >>= 1, r >>= 1) {
if ((l & 1) == 0) {
}
if ((r & 1) == 1) {
}
}
return res;
}
}
线段树
1825. 求出 MK 平均值 – 力扣（LeetCode）
2286. 以组为单位订音乐会的门票 – 力扣（LeetCode）
class Node {
int l, r, mid, len;
// int tag = 0;
Node(int _l, int _r) {
l = _l;
r = _r;
mid = (l + r) >> 1;
len = r - l + 1;
}
// 更新当前节点
void update(int k) {
}
// 合并左右节点信息
void merge(Node left, Node right) {
}
// 标记下推
void spread(Node left, Node right) {
// left.update(tag);
// right.update(tag);
// tag = 0;
}
}
class STree {
Node[] tree;
// args: 额外携带的初始化数组信息(可以不传入)
STree(int _n, int... args) {
tree = new Node[(_n + 5) << 2];
// 根据情况选择维护的区间为[0,n]或[1,n]
build(1, 1, _n, args);
}
int ls(int p) {
return p << 1;
}
int rs(int p) {
return p << 1 | 1;
}
void build(int p, int l, int r, int... args) {
tree[p] = new Node(l, r);
if (l == r) {
// args[l -1]
return;
}
int mid = (l + r) >> 1;
build(ls(p), l, mid, args);
build(rs(p), mid + 1, r, args);
tree[p].merge(tree[ls(p)], tree[rs(p)]);
}
void modify(int l, int r) {
modify(1, l, r);
}
void modify(int p, int l, int r) {
if (l <= tree[p].l && tree[p].r <= r) {
tree[p].update();
return;
}
tree[p].spread(tree[ls(p)], tree[rs(p)]);
if (l <= tree[p].mid) {
modify(p << 1, l, r);
}
if (tree[p].mid + 1 <= r) {
modify(p << 1 | 1, l, r);
}
tree[p].merge(tree[ls(p)], tree[rs(p)]);
}
int query(int l, int r) {
return query(1, l, r);
}
int query(int p, int l, int r) {
if (l <= tree[p].l && tree[p].r <= r) {
return 0;
}
tree[p].spread(tree[ls(p)], tree[rs(p)]);
if (l <= tree[p].mid) {
query(p << 1, l, r);
}
if (tree[p].mid + 1 <= r) {
query(p << 1 | 1, l, r);
}
return 0;
}
}
动态开点线段树
class Node {
// 左右儿子
Node left, right;
// 维护的区间
int l, r, mid, len;
// int tag = 0;
Node(int _l, int _r) {
l = _l;
r = _r;
mid = (l + r) >> 1;
len = r - l + 1;
}
void update(int k) {
}
void merge() {
}
void spread() {
if (left == null) {
left = new Node(l, mid);
}
if (right == null) {
right = new Node(mid + 1, r);
}
// left.update(tag);
// right.update(tag);
// tag = 0;
}
}
class CodomainSTree {
Node root;
CodomainSTree(int _l, int _r) {
root = new Node(_l, _r);
}
void modify(int l, int r, int k) {
modify(root, l, r, k);
}
void modify(Node p, int l, int r, int k) {
if (l <= p.l && p.r <= r) {
p.update(k);
return;
}
p.spread();
if (l <= p.mid) {
modify(p.left, l, r, k);
}
if (p.mid + 1 <= r) {
modify(p.right, l, r, k);
}
p.merge();
}
int query(int l, int r) {
return query(root, l, r);
}
int query(Node p, int l, int r) {
if (l <= p.l && p.r <= r) {
return 0;
}
p.spread();
if (l <= p.mid) {
query(p.left, l, r);
}
if (p.mid + 1 <= r) {
query(p.right, l, r);
}
return 0;
}
}
线段树合并
2003. 每棵子树内缺失的最小基因值 – 力扣（LeetCode）
class Node {
// 左右儿子
Node left, right;
// 维护的区间
int l, r, mid, len;
// int tag = 0;
Node(int _l, int _r) {
l = _l;
r = _r;
mid = (l + r) >> 1;
len = r - l + 1;
}
void update(int k) {
}
void merge() {
}
void spread() {
if (left == null) {
left = new Node(l, mid);
}
if (right == null) {
right = new Node(mid + 1, r);
}
// left.update(tag);
// right.update(tag);
// tag = 0;
}
}
/**
* MergedCodomainSTree[] tree = new MergedCodomainSTree[n + 5];
* Arrays.setAll(tree, treei -> new MergedCodomainSTree(l, r));
*/
class MergedCodomainSTree {
Node root;
MergedCodomainSTree(int _l, int _r) {
root = new Node(_l, _r);
}
void merge(MergedCodomainSTree y) {
merge(root, y.root);
}
Node merge(Node x, Node y) {
if (x == null) {
return y;
}
if (y == null) {
return x;
}
// 将y的结果合并到x上
if (x.l == x.r) {
return x;
}
x.left = merge(x.left, y.left);
x.right = merge(x.right, y.right);
return x;
}
void modify(int l, int r) {
modify(root, l, r);
}
void modify(Node p, int l, int r) {
if (l <= p.l && p.r <= r) {
p.update(k);
return;
}
p.spread();
if (l <= p.mid) {
modify(p.left, l, r);
}
if (p.mid + 1 <= r) {
modify(p.right, l, r);
}
p.merge();
}
int query(int l, int r) {
return query(root, l, r);
}
int query(Node p, int l, int r) {
if (l <= p.l && p.r <= r) {
return 0;
}
p.spread();
if (l <= p.mid) {
query(p.left, l, r);
}
if (p.mid + 1 <= r) {
query(p.right, l, r);
}
return 0;
}
}
序列问题
最小表示法
假设对于字符串\(s\)，我们正在比较以\(i\)和\(j\)为起点的字符串，如果前\(k\)个字符都相同，即\(s[i:i+k-1]=s[j:j+k-1]\)，考虑\(s[i+k]>s[j+k]\)的情况，那么以\([i,i+k]\)为起点的字符串都不会是最小字符串，可以以此来优化枚举过程，复杂度为\(O(n)\)。
int minExp(char[] s) {
int n = s.length;
int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
if (s[(i + k) % n] == s[(j + k) % n]) {
++k;
} else {
if (s[(i + k) % n] > s[(j + k) % n]) {
i = i + k + 1;
} else {
j = j + k + 1;
}
if (i == j) {
++i;
}
k = 0;
}
}
return Math.min(i, j);
}
字符串哈希
该类所有函数下标都从\(1\)开始，对于传入的数组默认从\(0\)开始，对于字符串可以调用\(toCharArray()\)方法获得\(char\)数组，\(h[i]\)代表\(s[0:i-1]\)的哈希值，\(p[i]\)代表\(P^i\)。
假设有字符串\(s=abca\)，那么\(h[1]=a,h[2]=a*P+b,h[3]=a*P^2+b*P+c,h[4]=a*P^3+b*P^2+c*P+a\)。
可以发现类似于一个\(P\)进制数，其中最低位为字符串末尾字符。
想要快速计算区间哈希值，有如下公式：
\[h[l:r]=h[r]-h[l-1]*p^{r-l+1}
\]
\]
举个例子，例如以上字符串，如果要求\(s[3:4]\)，那么要求的就是\(c*P+a\)，根据\(h[4]=a*P^3+b*P^2+c*P+a\)，\(h[2]=a*P+b\)，我们可以发现要求的就是\(h[4]-?*h[2]\)，这个\(?\)就是\(P^{4-3+1}=P^2\)。
以下模板中额外存储了\(s\)反转后的\(h\)数组\(rh\)，配合原\(h\)数组可以快速求出一个区间是否是回文串。
简洁版
class Hash {
static int P = 131, MOD = (int) 1e9 + 7;
int n;
int[] h, p;
Hash(char[] s) {
n = s.length;
h = new int[n + 5];
p = new int[n + 5];
p[0] = 1;
for (int i = 1; i <= n; ++i) {
h[i] = (int) (((long) h[i - 1] * P % MOD + s[i - 1]) % MOD);
p[i] = (int) ((long) p[i - 1] * P % MOD);
}
}
int get(int l, int r) {
return (h[r] - (int) ((long) h[l - 1] * p[r - l + 1] % MOD) + MOD) % MOD;
}
}
回文版
class Hash {
static int P = 131, MOD = (int) 1e9 + 7;
int n;
int[] h, rh, p;
Hash(char[] s) {
this(s, 131);
}
Hash(char[] s, int _P) {
P = _P;
n = s.length;
h = new int[n + 5];
rh = new int[n + 5];
p = new int[n + 5];
p[0] = 1;
for (int i = 1; i <= n; ++i) {
h[i] = (int) (((long) h[i - 1] * P % MOD + s[i - 1]) % MOD);
rh[i] = (int) (((long) rh[i - 1] * P % MOD + s[n - i]) % MOD);
p[i] = (int) ((long) p[i - 1] * P % MOD);
}
}
int get(int l, int r) {
return get(h, l, r);
}
int get(int[] h, int l, int r) {
return (h[r] - (int) ((long) h[l - 1] * p[r - l + 1] % MOD) + MOD) % MOD;
}
boolean isPalindrome(int l, int r) {
return get(h, l, r) == get(rh, n - r + 1, n - l + 1);
}
}
版权声明：本文为Stler4j原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。