题目大意 给定一个 $n$ 个点 $m$ 条边的带标号无向图，它有 $k$ 个连通块，求添加 $k-1$ 条边使得整个图连通的方案数，答案对 $p$ 取模。$(1 \le n \le 10^5, 0 \le m \le 10^5, 1 \le k \le 10^9)$ 解题思路 设 $s_i$ 为第 $i$ 个连通块的点数， $d_i$ 为第 $i…

问题描述 给 $m$ 个区间 $[l, r]$ 以及一个数 $x$，每次在区间 $[l, r]$ 上的每一个点放置一个物品 $x$，问： $[1, n]$ 中哪个点的物品种类最多？ $[1, n]$ 中每个点数量最多的物品是哪种？ ...... 解题思路： 首先利用差分，将序列操作变成区间操作：在 $l$ 上放置一个二元组标记 $<x, 1>…

斐波那契数列的区间操作 题目：华尔街的雪 题目大意： 斐波那契序列 $f_n$ 满足 $f_0=f_1=1,f_{n+2}=f_n+f_{n+1}$，$n$ 为自然数。现在有 $n$ 个可重集合排成一列，编号分别为 $1-n$，每个集合初始包含一个数 $f_1$。请支持如下四种操作： 1. 在第l~r号集合中各加入一个斐波那契数 $f_k$ 2. …

倍增 #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 50; int n, m, s; int head[N], tot; int lg[N]; // log2(i)+1 int fa[N][22], dep[N]; struct Edge { int …

点差分 例题：P3128 [USACO15DEC]Max Flow P 题目大意： 给 $k$ 条树上路径，求哪个点被经过的次数最多、被经过了多少次。 解题思路： 树上差分算法。对于每条路径 $(a,b)$，对 num[a]++，num[b]++，num[lca(a, b)]--，num[fa[lca(a, b)]]--。 这样再做一次 dfs 后…

题目：P3292 [SCOI2016]幸运数字 题目大意： 给一颗树 $(n\le 10^4)$，每个点有一个权值。有 $q$ 组询问 $(q\le 10^5)$，问两点之间树上路径点的最大异或和。 解题思路： 首先树剖，给点重新赋 $id$；用树剖算 lca 的过程中，对每条链维护一个线性基，每次将链的线性基和答案的线性基合并。由于经过了树剖重新…

norm() 计算向量的模长 db det(const pt &a, const pt &b) 计算两个向量的叉积 db dot(const pt &a, const pt &b) 计算两个向量的点积 db dist(const pt &a, const pt &b) 计算两个点的距离 pt rota…

db dis_pt_seg(const pt p, const pt s, const pt t) 求点 p 到线段 st 的距离 pt pt_projline(const pt p, const pt s, const pt t) 求点 p 到线段 st 的垂足 bool pt_on_seg(pt p, pt s, pt t) 判断点 p 是否在…

db cir() 计算多边形周长 db dir_area() 计算多边形有向面积 db area() 计算多边形面积 void fix() 如果点是以顺时针顺序存储，则改为逆时针 int poly::point_in(pt t) 判断点和多边形的关系：0 在外面，1 在内部，2 在边上 int poly::Border_pt_num() 计算多边形…

凸包类 conv get_convex(vector<pt> a) 用点集求出凸包（逆时针保存） bool isconvex(const vector<pt> &a) 对给定的点集（顺逆时针均可），判断是否构成凸包 bool containOn(const conv &a, const pt &b) …