标签：常用 return int res ll ACM vector const 模板
useful skill
连续区间求和
ll sum(ll l,ll r){
return (l+r)*(r-l+1)/2;
}
内置位运算
__builtin_ffs(x)：返回x中最后一个为1的位是从后向前的第几位，如__builtin_ffs(0x789)=1, __builtin_ffs(0x78c)=3。于是，__builtin_ffs(x) - 1就是x中最后一个为1的位的位置。
__builtin_popcount(x)：x中1的个数。
__builtin_ctz(x)：x末尾0的个数。x=0时结果未定义。
__builtin_clz(x)：x前导0的个数。x=0时结果未定义。
__builtin_parity(x)：x中1的奇偶性。
jiangly取模类
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MLong {
i64 x;
constexpr MLong() : x{} {}
constexpr MLong(i64 x) : x{norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
explicit constexpr operator i64() const {
return x;
}
constexpr MLong operator-() const {
MLong res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MLong &operator*=(MLong rhs) & {
x = mul(x, rhs.x, getMod());
return *this;
}
constexpr MLong &operator+=(MLong rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong &operator-=(MLong rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong &operator/=(MLong rhs) & {
return *this *= rhs.inv();
}
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
i64 v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};
template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 1000000007;
using Z = MInt<P>;
其他
高精
const int base = 1000000000;
const int base_digits = 9; // 分解为九个数位一个数字
struct bigint {
vector<int> a;
int sign;
bigint() : sign(1) {}
bigint operator-() const {
bigint res = *this;
res.sign = -sign;
return res;
}
bigint(long long v) {
*this = v;
}
bigint(const string &s) {
read(s);
}
void operator=(const bigint &v) {
sign = v.sign;
a = v.a;
}
void operator=(long long v) {
a.clear();
sign = 1;
if (v < 0) sign = -1, v = -v;
for (; v > 0; v = v / base) {
a.push_back(v % base);
}
}
// 基础加减乘除
bigint operator+(const bigint &v) const {
if (sign == v.sign) {
bigint res = v;
for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i) {
if (i == (int)res.a.size()) {
res.a.push_back(0);
}
res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
carry = res.a[i] >= base;
if (carry) {
res.a[i] -= base;
}
}
return res;
}
return *this - (-v);
}
bigint operator-(const bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
bigint res = *this;
for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i) {
res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
carry = res.a[i] < 0;
if (carry) {
res.a[i] += base;
}
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
}
void operator*=(int v) {
check(v);
for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
if (i == (int)a.size()) {
a.push_back(0);
}
long long cur = a[i] * (long long)v + carry;
carry = (int)(cur / base);
a[i] = (int)(cur % base);
}
trim();
}
void operator/=(int v) {
check(v);
for (int i = (int)a.size() - 1, rem = 0; i >= 0; --i) {
long long cur = a[i] + rem * (long long)base;
a[i] = (int)(cur / v);
rem = (int)(cur % v);
}
trim();
}
int operator%(int v) const {
if (v < 0) {
v = -v;
}
int m = 0;
for (int i = a.size() - 1; i >= 0; --i) {
m = (a[i] + m * (long long)base) % v;
}
return m * sign;
}
void operator+=(const bigint &v) {
*this = *this + v;
}
void operator-=(const bigint &v) {
*this = *this - v;
}
bigint operator*(int v) const {
bigint res = *this;
res *= v;
return res;
}
bigint operator/(int v) const {
bigint res = *this;
res /= v;
return res;
}
void operator%=(const int &v) {
*this = *this % v;
}
bool operator<(const bigint &v) const {
if (sign != v.sign) return sign < v.sign;
if (a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign;
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign;
return false;
}
bool operator>(const bigint &v) const {
return v < *this;
}
bool operator<=(const bigint &v) const {
return !(v < *this);
}
bool operator>=(const bigint &v) const {
return !(*this < v);
}
bool operator==(const bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const bigint &v) const {
return *this < v || v < *this;
}
bigint abs() const {
bigint res = *this;
res.sign *= res.sign;
return res;
}
void check(int v) { // 检查输入的是否为负数
if (v < 0) {
sign = -sign;
v = -v;
}
}
void trim() { // 去除前导零
while (!a.empty() && !a.back()) a.pop_back();
if (a.empty()) sign = 1;
}
bool isZero() const { // 判断是否等于零
return a.empty() || (a.size() == 1 && !a[0]);
}
friend bigint gcd(bigint a,bigint b){
int tims(0);if(a<b) swap(a,b);
while(!(a%2)&&!(b%2)) a=a/2,b=b/2,++tims;
while(!(a==b)){
int t1(a%2),t2(b%2);
!t1?a=a/2:(!t2?b=b/2:a=a-b);
if(a<b) swap(a,b);
}
while(tims--) a=a*2;
return a;
}
friend bigint lcm(const bigint &a, const bigint &b) {
return a / gcd(a, b) * b;
}
friend bigint qpow(bigint a, bigint n){
bigint res = 1;
while (n>0){
if (n%2==1) res = res * a;
a = a * a;
n /= 2;
}
return res;
}
friend bigint sqrt(bigint x,bigint y){
if(x==1) return x;
bigint l=0,r=x+1;
while(l<r){
bigint mid=(l+r)/2;
if(qpow(mid,y)>x) r=mid;
else l=mid+1;
}
return l-1;
}
friend bigint factorial(bigint x){
bigint ans=1;
for(bigint i=1;i<=x;i+=1) ans*=i;
return ans;
}
void read(const string &s) {
sign = 1;
a.clear();
int pos = 0;
while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-') sign = -sign;
++pos;
}
for (int i = s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0';
a.push_back(x);
}
trim();
}
friend istream &operator>>(istream &stream, bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
}
friend ostream &operator<<(ostream &stream, const bigint &v) {
if (v.sign == -1) stream << '-';
stream << (v.a.empty() ? 0 : v.a.back());
for (int i = (int)v.a.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.a[i];
return stream;
}
/* 大整数乘除大整数部分 */
typedef vector<long long> vll;
bigint operator*(const bigint &v) const { // 大整数乘大整数
vector<int> a6 = convert_base(this->a, base_digits, 6);
vector<int> b6 = convert_base(v.a, base_digits, 6);
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size()) a.push_back(0);
while (b.size() < a.size()) b.push_back(0);
while (a.size() & (a.size() - 1)) a.push_back(0), b.push_back(0);
vll c = karatsubaMultiply(a, b);
bigint res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < (int)c.size(); i++) {
long long cur = c[i] + carry;
res.a.push_back((int)(cur % 1000000));
carry = (int)(cur / 1000000);
}
res.a = convert_base(res.a, 6, base_digits);
res.trim();
return res;
}
friend pair<bigint, bigint> divmod(const bigint &a1,
const bigint &b1) { // 大整数除大整数，同时返回答案与余数
int norm = base / (b1.a.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.a.resize(a.a.size());
for (int i = a.a.size() - 1; i >= 0; i--) {
r *= base;
r += a.a[i];
int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
int d = ((long long)base * s1 + s2) / b.a.back();
r -= b * d;
while (r < 0) r += b, --d;
q.a[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
}
static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < (int)p.size(); i++) p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int i = 0; i < (int)a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back((int)(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int)cur);
while (!res.empty() && !res.back()) res.pop_back();
return res;
}
static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= 32) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
res[i + j] += a[i] * b[j];
}
}
return res;
}
int k = n >> 1;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end());
vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2);
for (int i = 0; i < k; i++) a2[i] += a1[i];
for (int i = 0; i < k; i++) b2[i] += b1[i];
vll r = karatsubaMultiply(a2, b2);
for (int i = 0; i < (int)a1b1.size(); i++) r[i] -= a1b1[i];
for (int i = 0; i < (int)a2b2.size(); i++) r[i] -= a2b2[i];
for (int i = 0; i < (int)r.size(); i++) res[i + k] += r[i];
for (int i = 0; i < (int)a1b1.size(); i++) res[i] += a1b1[i];
for (int i = 0; i < (int)a2b2.size(); i++) res[i + n] += a2b2[i];
return res;
}
void operator*=(const bigint &v) {
*this = *this * v;
}
bigint operator/(const bigint &v) const {
return divmod(*this, v).first;
}
void operator/=(const bigint &v) {
*this = *this / v;
}
bigint operator%(const bigint &v) const {
return divmod(*this, v).second;
}
void operator%=(const bigint &v) {
*this = *this % v;
}
};
高精2
const int MAXN = 10010;
struct BInt
{
int len, s[MAXN];
BInt ()
{
memset(s, 0, sizeof(s));
len = 1;
}
BInt (int num) { *this = num; }
BInt (const char *num) { *this = num; }
BInt operator = (const int num)
{
char s[MAXN];
sprintf(s, "%d", num);
*this = s;
return *this;
}
BInt operator = (const char *num)
{
for(int i = 0; num[i] == '0'; num++) ;
len = strlen(num);
for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
return *this;
}
BInt operator + (const BInt &b) const
{
BInt c;
c.len = 0;
for(int i = 0, g = 0; g || i < max(len, b.len); i++)
{
int x = g;
if(i < len) x += s[i];
if(i < b.len) x += b.s[i];
c.s[c.len++] = x % 10;
g = x / 10;
}
return c;
}
BInt operator += (const BInt &b)
{
*this = *this + b;
return *this;
}
void clean()
{
while(len > 1 && !s[len-1]) len--;
}
BInt operator * (const BInt &b)
{
BInt c;
c.len = len + b.len;
for(int i = 0; i < len; i++)
{
for(int j = 0; j < b.len; j++)
{
c.s[i+j] += s[i] * b.s[j];
}
}
for(int i = 0; i < c.len; i++)
{
c.s[i+1] += c.s[i]/10;
c.s[i] %= 10;
}
c.clean();
return c;
}
BInt operator *= (const BInt &b)
{
*this = *this * b;
return *this;
}
BInt operator - (const BInt &b)
{
BInt c;
c.len = 0;
for(int i = 0, g = 0; i < len; i++)
{
int x = s[i] - g;
if(i < b.len) x -= b.s[i];
if(x >= 0) g = 0;
else
{
g = 1;
x += 10;
}
c.s[c.len++] = x;
}
c.clean();
return c;
}
BInt operator -= (const BInt &b)
{
*this = *this - b;
return *this;
}
BInt operator / (const BInt &b)
{
BInt c, f = 0;
for(int i = len-1; i >= 0; i--)
{
f = f*10;
f.s[0] = s[i];
while(f >= b)
{
f -= b;
c.s[i]++;
}
}
c.len = len;
c.clean();
return c;
}
BInt operator /= (const BInt &b)
{
*this = *this / b;
return *this;
}
BInt operator % (const BInt &b)
{
BInt r = *this / b;
r = *this - r*b;
r.clean();
return r;
}
BInt operator %= (const BInt &b)
{
*this = *this % b;
return *this;
}
bool operator < (const BInt &b)
{
if(len != b.len) return len < b.len;
for(int i = len-1; i != -1; i--)
{
if(s[i] != b.s[i]) return s[i] < b.s[i];
}
return false;
}
bool operator > (const BInt &b)
{
if(len != b.len) return len > b.len;
for(int i = len-1; i != -1; i--)
{
if(s[i] != b.s[i]) return s[i] > b.s[i];
}
return false;
}
bool operator == (const BInt &b)
{
return !(*this > b) && !(*this < b);
}
bool operator != (const BInt &b)
{
return !(*this == b);
}
bool operator <= (const BInt &b)
{
return *this < b || *this == b;
}
bool operator >= (const BInt &b)
{
return *this > b || *this == b;
}
string str() const
{
string res = "";
for(int i = 0; i < len; i++) res = char(s[i]+'0')+res;
return res;
}
};
istream& operator >> (istream &in, BInt &x)
{
string s;
in >> s;
x = s.c_str();
return in;
}
ostream& operator << (ostream &out, const BInt &x)
{
out << x.str();
return out;
}
inline BInt fac(BInt x){
BInt ans=1;
for(BInt i=1;i<=x;i+=1) ans*=i;
return ans;
}
inline BInt qpow(BInt a,BInt b){
BInt x=a,y=b;
BInt result=1;
while(y>=1){
if(y%2==1) result=result*x;
x=x*x;
y/=2;
}
return result;
}
inline BInt sqrt(BInt x,BInt y){
if(x==1) return x;
BInt l=0,r=x+1;
while(l<r){
BInt mid=(l+r)/2;
if(qpow(mid,y)>x) r=mid;
else l=mid+1;
}
return l-1;
}
离散化
template <typename T> struct Compress_ {
int n, shift = 0; // shift 用于标记下标偏移量
vector<T> alls;
Compress_() {}
Compress_(auto in) : alls(in) {
init();
}
void add(T x) {
alls.emplace_back(x);
}
template <typename... Args> void add(T x, Args... args) {
add(x), add(args...);
}
void init() {
alls.emplace_back(numeric_limits<T>::max());
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
this->n = alls.size();
}
int size() {
return n;
}
int operator[](T x) { // 返回 x 元素的新下标
return upper_bound(alls.begin(), alls.end(), x) - alls.begin() + shift;
}
T Get(int x) { // 根据新下标返回原来元素
assert(x - shift < n);
return x - shift < n ? alls[x - shift] : -1;
}
bool count(T x) { // 查找元素 x 是否存在
return binary_search(alls.begin(), alls.end(), x);
}
friend auto &operator<<(ostream &o, const auto &j) {
cout << "{";
for (auto it : j.alls) {
o << it << " ";
}
return o << "}";
}
};
using Compress = Compress_<int>;
//不封装简洁版
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
auto get = [&](int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
};
二维前缀和
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> a(n+1,vector<int>(m+1,0));
vector<vector<int>> pre(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
pre[i][j]=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+a[i][j];
}
}
int maxn=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=i;k<=n;k++){
for(int r=j;r<=m;r++){
maxn=max(maxn,pre[k][r]-pre[k][j-1]-pre[i-1][r]+pre[i-1][j-1]);
}
}
}
}
}
二维差分
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N];
int b[N][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
}
}
while(m--){
int sx,sy,ex,ey;
cin>>sx>>sy>>ex>>ey;
++b[sx][sy];
--b[ex+1][sy];
--b[sx][ey+1];
++b[ex+1][ey+1];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
数学
进制转换
// 2~36 base converter
struct BaseConverter {
int s;int t;bool u=false;
BaseConverter(int source, int target,bool upper) : s(source), t(target),u(upper) {}
BaseConverter(int source, int target) : s(source), t(target){}
BaseConverter(bool upper):u(upper){}
BaseConverter(){}
string work(const string& source) {
int v = XTD(source, s);
return DTX(v, t);
}
// 将源进制的数字字符串转为十进制
int XTD(const string& source, int b) {
int v = 0;
int p = 1;
for (int i = source.length() - 1; i >= 0; --i) {
int bits = charToDigit(source[i]);
if (bits == -1 || bits >= b) {
cerr << "Invalid x in source number.\n";
return -1;
}
v += bits * p;
p *= b;
}
return v;
}
// 将十进制的值转为目标进制的字符串
string DTX(int v, int b) {
if (v == 0) return "0";
string res = "";
while (v > 0) {
int rem = v % b;
res = digitToChar(rem) + res;
v /= b;
}
return res;
}
// 获取字符对应的数字值
int charToDigit(char x) {
if (x >= '0' && x <= '9') {
return x - '0';
} else if (x >= 'A' && x <= 'Z') {
return x - 'A' + 10;
} else if (x >= 'a' && x <= 'z') {
return x - 'a' + 10;
}
return -1;
}
// 获取数字值对应的字符
char digitToChar(int val) {
if (val >= 0 && val <= 9) {
return '0' + val;
} else if (val >= 10 && val <= 35) {
if(!u){
return 'a' + val - 10;
}else{
return 'A'+val-10;
}
}
return '\0';
}
};
求约数
vector<int> get_divisors(int x){
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0){
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
判质数
bool isPrime(int x){
if(x<2){
return false;
}
for(int i=2;i<=x/i;i++){
if(x%i==0){
return false;
}
}
return true;
}
//常数优化 sqrt(x)/3
bool isPrime(int n) {
if (n == 1) return false;
if (n == 2 || n == 3) return true;
if (n % 6 != 1 && n % 6 != 5) return false;
for (int i = 5, j = n / i; i <= j; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
分解质因数
map<int,int> cnt;
void divide(int x){
for(int i=2;i<=x/i;i++){
if(x%i==0){
while(x%i==0){
x/=i;
cnt[i]++;
}
}
}
if(x>1) cnt[x]++;
}
GCD&LCM
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
//加速版gcd
ll gcd(ll a,ll b){
int tims(0);if(a<b) swap(a,b);
while(!(a%2)&&!(b%2)) a=a/2,b=b/2,++tims;
while(!(a==b)){
int t1(a%2),t2(b%2);
!t1?a=a/2:(!t2?b=b/2:a=a-b);
if(a<b) swap(a,b);
}
while(tims--) a=a*2;
return a;
}
int lcm(int m,int n){
int g1,b;
g1 = __gcd(m,n);
b = (m*n) / g1; //最小公倍数=两数之积/最大公约数
return b;
}
龟速乘
ll smul(ll a,ll b,ll mod){
ll res = 0;
while (b){
if (b & 1) res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res%mod;
}
快速幂
ll qpow(ll a, ll n, ll mod){
ll res = 1;
while (n){
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res%mod;
}
质数筛
constexpr int N =1e6+10;
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n){
for (int i = 2; i <= n; i ++ ){
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ ){
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
//欧拉筛
vector<int> prime;
auto euler_Prime = [&](int n){
int cnt=0;
vector<int> v(n + 1);
for (int i = 2; i <= n; ++i) {
if (!v[i]) {
v[i] = i;cnt+=i;
prime.push_back(i);
}
for (int j = 0; j < prime.size(); ++j) {
if (prime[j] > v[i] || prime[j] > n / i) break;
v[i * prime[j]] = prime[j];
cnt+=prime[j];
}
}
//return sum of 1~n min prime factor
return cnt;
};
欧拉函数
int phi(int x){
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0){
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
//扩展欧拉定理降幂 p = phi(m) b为次数
auto depow = [&](string str){
int b=0;
bool flag=false;
for(int i=0;i<str.size();i++){
b=b*10+str[i]-'0';
if(b>=p){
flag=true;
b%=p;
}
}
if(flag){
b+=p;
}
return b;
};
欧拉函数筛
const int N = 1e6+10;
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n){
euler[1] = 1;
for (int i = 2; i <= n; i ++ ){
if (!st[i]){
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ ){
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0){
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
Stirling
const int mod = 1e9+7;
const int N = 1e6+100;
int fac[N+2],invfac[N+2];
int qpow(int a,int b,int mod){
int res=1;while(b){if(b&1){res=res*a%mod;}a=a*a%mod;b>>=1;}return res;
}
int inv(int x){return qpow(x,mod-2,mod);}
void init(int n){
fac[0] = 1;for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
invfac[n] = inv(fac[n]);for (int i = n - 1; i >= 0; --i) invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
}
int C(int n,int m){
if (n < m || m < 0) return 0;return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
int S(int n,int k){
int ans=0;
for(int i=0;i<=k;i++){
ans=(ans+mod)%mod;
ans=(ans+(i%2?-1:1)*C(k,i)%mod*qpow(k-i,n,mod)%mod)%mod;
}
ans=ans*invfac[k]%mod;
return ans;
}
Catalan
template<typename T>
struct Catalan{
T c=1;
T C(int x, int y){
T m;
if( x < 0 || y < 0 || y > x ){
m = 0;
}
else if( y == 0 ){
m = 1;
}
else if( y > x / 2 ){
y = x - y;
m = C( x , y );
}
else{
m = C( x - 1, y - 1)*x / y;
}
return m;
};
T query1(int n){
for(int i=1;i<=n;i++){
c=c*(4*i-2)/(i+1);
}
return c;
}
T query2(int n,int m){
return C(n+m,n)-C(n+m,m-1);
}
T query3(int n){
return C(2*n,n)/(n+1);
}
};
Lucas
struct Lucas{
ll mod;
ll qpow(ll a,ll b){
ll s=1;
while(b)
{
if(b&1) s=s*a%mod;
a=a*a%mod;
b>>=1;
}
return s;
}
ll C(ll n,ll m){
if(m>n) return 0;
ll a=1,b=1;
for(ll i=n-m+1;i<=n;++i)
a=a*i%mod;
for(ll i=2;i<=m;++i)
b=b*i%mod;
return a*qpow(b,mod-2)%mod;
}
ll query(ll n,ll m){
if(!m) return 1;
else return (C(n%mod,m%mod)*query(n/mod,m/mod))%mod;
}
Lucas(ll mod){
this->mod=mod;
}
};
组合数
const int mod = 1e9+7;
const int N = 1e6+100;
int fac[N+2],invfac[N+2];
int qpow(int a,int b){
int res=1;while(b){if(b&1){res=res*a%mod;}a=a*a%mod;b>>=1;}return res;
}
int inv(int x){return qpow(x,mod-2);}
void init(int n){
fac[0] = 1;for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
invfac[n] = inv(fac[n]);for (int i = n - 1; i >= 0; --i) invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
}
int C(int n,int m){
if (n < m || m < 0) return 0;return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
int A(int n,int m){
if (n < m || m < 0) return 0;return fac[n]*invfac[n-m]%mod;
}
// int D[N+2]
//错排：D[i]=(i-1)*(D[i-1]+D[i-2]) D[0]=1,D[1]=0,D[2]=1,D[3]=2;
矩阵运算
using ll = long long;
template <typename T>
class Matrix {
public:
std::vector<std::vector<T>> mat;
int rows, cols;
int mod;
Matrix(int rows, int cols) : rows(rows), cols(cols) {
mat.resize(rows, std::vector<T>(cols, 0));
}
Matrix(int rows, int cols, const T& initial) : rows(rows), cols(cols) {
mat.resize(rows, std::vector<T>(cols, initial));
}
Matrix(const std::vector<std::vector<T>>& data) {
rows = static_cast<int>(data.size());
if (rows > 0) {
cols = static_cast<int>(data[0].size());
mat = data;
} else {
rows = 0;
cols = 0;
}
}
Matrix(const Matrix& other) {
rows = other.rows;
cols = other.cols;
mat = other.mat;
}
//运算
Matrix& operator=(const Matrix& other) {
if (this != &other) {
rows = other.rows;
cols = other.cols;
mat = other.mat;
}
return *this;
}
Matrix operator+(const T& scalar) const {
Matrix result(rows, cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result.mat[i][j] = mat[i][j] + scalar;
}
}
return result;
}
Matrix operator+(const Matrix& other) const {
Matrix result(rows, cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result.mat[i][j] = mat[i][j] + other.mat[i][j];
}
}
return result;
}
Matrix& operator+=(const Matrix& other) {
*this = *this + other;
return *this;
}
Matrix& operator+=(const T& scalar) {
*this = *this + scalar;
return *this;
}
Matrix operator-(const T& scalar) const {
Matrix result(rows, cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result.mat[i][j] = mat[i][j] - scalar;
}
}
return result;
}
Matrix operator-(const Matrix& other) const {
Matrix result(rows, cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result.mat[i][j] = mat[i][j] - other.mat[i][j];
}
}
return result;
}
Matrix& operator-=(const Matrix& other) {
*this = *this - other;
return *this;
}
Matrix& operator-=(const T& scalar) {
*this = *this - scalar;
return *this;
}
Matrix operator*(const Matrix& other) const {
if (cols != other.rows) {
throw std::invalid_argument("Matrix dimensions do not match for multiplication.");
}
Matrix result(rows, other.cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < other.cols; j++) {
for (int k = 0; k < cols; k++) {
result.mat[i][j] += mat[i][k] * other.mat[k][j];
}
}
}
return result;
}
Matrix& operator*=(const Matrix& other) {
*this = *this * other;
return *this;
}
friend std::ostream& operator<<(std::ostream& os, const Matrix& matrix) {
for (int i = 0; i < matrix.rows; i++) {
for (int j = 0; j < matrix.cols; j++) {
os << matrix.mat[i][j] << " ";
}
os << std::endl;
}
return os;
}
std::vector<T>& operator[](int index) {
if (index < 0 || index >= rows) {
throw std::out_of_range("Matrix index out of range.");
}
return mat[index];
}
static Matrix<T> power(const Matrix<T>& base, int exponent) {
if (exponent == 0) {
Matrix<T> result(base.rows, base.cols);
for (int i = 0; i < base.rows; i++) {
result.mat[i][i] = 1;
}
return result;
}
if (exponent % 2 == 0) {
Matrix<T> half_pow = power(base, exponent / 2);
return half_pow * half_pow;
} else {
return base * power(base, exponent - 1);
}
}
//求行列式
T determinant(int mod){
this->mod=mod;
int res=1,w=1;
for(int i=0;i<rows;i++){
for(int j=i+1;j<cols;++j){
while(mat[i][i]){
int div=mat[j][i]/mat[i][i];
for(int k=i;k<rows;++k){
mat[j][k]=(mat[j][k]-1ll*div*mat[i][k]%mod+mod)%mod;
}
swap(mat[i],mat[j]);w=-w;
}
swap(mat[i],mat[j]);w=-w;
}
}
for(int i=0;i<rows;i++)res=1ll*mat[i][i]*res%mod;
res=1ll*w*res;
return (res+mod)%mod;
}
//转置
Matrix<T> transpose() const {
Matrix<T> result(cols, rows);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result.mat[j][i] = mat[i][j];
}
}
return result;
}
//点乘
Matrix<T> EWMultiply(const Matrix& other) const {
if (rows != other.rows || cols != other.cols) {
throw std::invalid_argument("Matrix dimensions do not match for element-wise multiplication.");
}
Matrix<T> result(rows, cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result.mat[i][j] = mat[i][j] * other.mat[i][j];
}
}
return result;
}
Matrix<T> EWMultiply_Vec(const vector<T>& other) const {
Matrix<T> result(rows, cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result.mat[i][j] = mat[i][j] * other[i];
}
}
return result;
}
};
using Matri = Matrix<ll>;
矩阵加速
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//MatPow
constexpr ll MOD = 1e9+7;
struct Matrix {
ll s[105][105];
ll n;
Matrix(ll n):n(n){
memset(s, 0, sizeof(s));
}
inline void unit() {
for (ll i = 1; i <= n; i++)
s[i][i] = 1;
}
Matrix operator* (const Matrix &b) const{
Matrix c(n);
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= n; j++) {
for (ll k = 1; k <= n; k++) {
c.s[i][j] = (c.s[i][j] + s[i][k] * b.s[k][j]) % MOD;
}
}
}
return c;
}
Matrix operator *= (const Matrix &b){
*this = *this*b;
return *this;
}
Matrix operator ^(ll b){
Matrix tmp(n);
tmp.unit();
while (b) {
if (b&1)
tmp*=*this;
*this*=*this;
b >>= 1;
}
return tmp;
}
Matrix operator ^=(ll b){
*this=*this^b;
return *this;
}
ll* operator[](ll index) {
return s[index];
}
};
博弈论
//1堆n个石子每次最多取m个、最少取1个
struct Bash{
int n,k;
Bash(int n,int k):n(n),k(k){};
bool work(){
return n%(k+1);//true 为先手赢
}
};
//有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜
struct Wythoff{
int a,b,diff;
double p=(sqrt((double)5)+1)/double(2);
Wythoff(int a,int b):a(a),b(b),diff(abs(a-b)){};
bool work(){
int r=a<b?a:b;
if(r==(int)(p*diff)){
return false;
}
return true;
}
};
//有n堆石子，每堆石子的数量是a1,a2,a3……，二个人依次从这些石子堆中的一个拿取任意的石子，至少一个，最后一个拿光石子的人胜利
struct Nim{
#define MAXN 50010
int cnt,s,n;
int a[MAXN];
int ans[MAXN][2];
Nim(int n):n(n){}
void input(){
for(int i=0;i<n;i++){
cin>>a[i];
s^=a[i];
}
}
bool work(){
for(int i=0;i<n;i++){
if(a[i] > (s^a[i])){
ans[cnt][0] = a[i];
ans[cnt][1] = s^a[i];
cnt++;
}
}
return cnt;//先手赢为true
}
//输出若先手为胜的走法
void getWays(){
for(int i=0;i<cnt;i++){
cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
}
}
//使先手为胜的方案的数目
int WinCount(){
return cnt;
}
#undef MAXN
};
BSGS&exBSGS
namespace BSGS {
ll a, b, p;
map<ll, ll> f;
inline ll gcd(ll a, ll b) { return b > 0 ? gcd(b, a % b) : a; }
inline ll qpow(ll n, ll k, int p) {
ll r = 1;
for (; k; k >>= 1) {
if (k & 1) r = r * n % p;
n = n * n % p;
}
return r;
}
void exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
} else {
exgcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - a / b * y;
}
}
ll inv(ll a, ll b) {
ll x, y;
exgcd(a, b, x, y);
return (x % b + b) % b;
}
ll bsgs(ll a, ll b, ll p) {
f.clear();
int m = ceil(sqrt(p));
b %= p;
for (int i = 1; i <= m; i++) {
b = b * a % p;
f[b] = i;
}
ll tmp = qpow(a, m, p);
b = 1;
for (int i = 1; i <= m; i++) {
b = b * tmp % p;
if (f.count(b) > 0) return (i * m - f[b] + p) % p;
}
return -1;
}
ll exbsgs(ll a, ll b, ll p) { //a^x ≡ b(mod p)
a %= p,b %= p;
if (b == 1 || p == 1) return 0;
ll g = gcd(a, p), k = 0, na = 1;
while (g > 1) {
if (b % g != 0) return -1;
k++;
b /= g;
p /= g;
na = na * (a / g) % p;
if (na == b) return k;
g = gcd(a, p);
}
ll f = bsgs(a, b * inv(na, p) % p, p);
if (f == -1) return -1;
return f + k;
}
} using namespace BSGS;
exCRT
using ll = long long;
const int N = 1e5+10;
ll Ai[N], Mi[N];
int n;
constexpr int qpow(int n, int k, int p) {
int r = 1;
for (; k; k >>= 1, n = n * n % p)
if (k & 1) r = r * n % p;
return r;
}
constexpr ll mul(ll a, ll b, ll p) {
ll res = a * b - ll(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1, y = 0; return a; }
ll gcd = exgcd(b, a % b, x, y), tp = x;
x = y, y = tp - a / b * y;
return gcd;
}
ll excrt() {
ll x, y, k;
ll M = Mi[1], ans = Ai[1];
for (int i = 2; i <= n; ++ i) {
ll a = M, b = Mi[i], c = (Ai[i] - ans % b + b) % b;
ll gcd = exgcd(a, b, x, y), bg = b / gcd;
if (c % gcd != 0) return -1;
x = mul(x, c / gcd, bg);
ans += x * M;
M *= bg;
ans = (ans % M + M) % M;
}
return (ans % M + M) % M;
}
exGCD
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
//求逆元，要求a与p互质
int inv(int a, int p){
int x, y;
exgcd(a, p, x, y);
return (p + x % p) % p;
}
auto calc = [&](int a,int b,int c)->int{
int x, y, d = exgcd(a, b, x, y);
if (c % d != 0) {
return -1;
}
return (x*c/d%b/d+b/d)%b/d;
};
exLucas
struct exlucas{
using ll = long long;
int p;
exlucas(int p):p(p){}
ll cnt,pr[1010],al[1010];
void exgcd(ll a,ll b,ll &x,ll &y){
if (!b) return (void)(x=1,y=0);
exgcd(b,a%b,x,y);
ll tmp=x;x=y;y=tmp-a/b*y;
}
ll inv(ll a,ll p){
ll x,y;
exgcd(a,p,x,y);
return (x+p)%p;
}
ll qpow(ll a,ll b,ll p){
ll t=1;
a%=p;
for(;b;b>>=1){
if(b&1) t=t*a%p;
a=a*a%p;
}
return t;
}
ll fac(ll n,ll p,ll ppa){
if (n==0) return 1;
ll cir=1,rem=1;
for (ll i=1;i<=ppa;i++) if(i%p) cir=cir*i%ppa;
cir=qpow(cir,n/ppa,ppa);
for(ll i=ppa*(n/ppa);i<=n;i++) if(i%p) rem=rem*(i%ppa)%ppa;
return fac(n/p,p,ppa)*cir%ppa*rem%ppa;
}
ll sum_fac(ll n,ll p){
return n<p?0:sum_fac(n/p,p)+(n/p);
}
ll C(ll n,ll m,ll p,ll ppa){
ll fz=fac(n,p,ppa),fm1=inv(fac(m,p,ppa),ppa),fm2=inv(fac(n-m,p,ppa),ppa);
ll mi=qpow(p,sum_fac(n,p)-sum_fac(m,p)-sum_fac(n-m,p),ppa);
return fz*fm1%ppa*fm2%ppa*mi%ppa;
}
void split(ll n,ll m){
ll P=p;
for(ll i=2;i*i<=p;i++){
if(!(P%i)){
ll ppa=1;
while(!(P%i)) ppa*=i,P/=i;
pr[++cnt]=ppa;
al[cnt]=C(n,m,i,ppa);
}
}
if(P!=1) pr[++cnt]=P,al[cnt]=C(n,m,P,P);
}
ll crt(){
ll ans=0;
for(ll i=1;i<=cnt;i++){
ll M=p/pr[i],T=inv(M,pr[i]);
ans=(ans+al[i]*M%p*T%p)%p;
}
return ans;
}
ll work(ll n,ll m){
split(n,m);
return crt();
}
};
高斯消元
const int N = 110;
struct Gauss{
const double eps = 1e-8;
double a[N][N];
ll n;
Gauss(int n):n(n){}
ll gauss(){
ll c, r;
for (c = 0, r = 0; c < n; c ++ ){
ll t = r;
for (int i = r; i < n; i ++ )
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue;
for (int j = c; j < n + 1; j ++ ) swap(a[t][j], a[r][j]);
for (int j = n; j >= c; j -- ) a[r][j] /= a[r][c];
for (int i = r + 1; i < n; i ++ )
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
r ++ ;
}
if (r < n){
for (int i = r; i < n; i ++ )
if (fabs(a[i][n]) > eps)
return 2;
return 1;
}
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];
return 0;
}
void work(){
int t=gauss();
if(t==0){
for (int i = 0; i < n; i ++ ){
if (fabs(a[i][n]) < eps) a[i][n] = abs(a[i][n]);
cout<<a[i][n]<<"\n";
}
}
else if (t == 1) cout << "Infinite group solutions\n";
else cout << "No solution\n";
}
};
Pollard Rho & Miller Rabin
ll mul(ll a, ll b, ll m) {
return static_cast<__int128_t>(a) * b % m;
}
ll power(ll a, ll b, ll m) {
ll res = 1 % m;
for (; b; b >>= 1, a = mul(a, a, m))
if (b & 1)
res = mul(res, a, m);
return res;
}
bool isprime(ll n) {
if (n < 2)
return false;
static constexpr int A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int s = __builtin_ctzll(n - 1);
ll d = (n - 1) >> s;
for (auto a : A) {
if (a == n)
return true;
ll x = power(a, d, n);
if (x == 1 || x == n - 1)
continue;
bool ok = false;
for (int i = 0; i < s - 1; ++i) {
x = mul(x, x, n);
if (x == n - 1) {
ok = true;
break;
}
}
if (!ok)
return false;
}
return true;
}
std::vector<ll> factorize(ll n) {
std::vector<ll> p;
std::function<void(ll)> f = [&](ll n) {
if (n <= 10000) {
for (int i = 2; i * i <= n; ++i)
for (; n % i == 0; n /= i)
p.push_back(i);
if (n > 1)
p.push_back(n);
return;
}
if (isprime(n)) {
p.push_back(n);
return;
}
auto g = [&](ll x) {
return (mul(x, x, n) + 1) % n;
};
ll x0 = 2;
while (true) {
ll x = x0;
ll y = x0;
ll d = 1;
ll power = 1, lam = 0;
ll v = 1;
while (d == 1) {
y = g(y);
++lam;
v = mul(v, std::abs(x - y), n);
if (lam % 127 == 0) {
d = std::__gcd(v, n);
v = 1;
}
if (power == lam) {
x = y;
power *= 2;
lam = 0;
d = std::__gcd(v, n);
v = 1;
}
}
if (d != n) {
f(d);
f(n / d);
return;
}
++x0;
}
};
f(n);
std::sort(p.begin(), p.end());
return p;
}
多项式(zhoukangyang poly)
#define Fo(i, j, k) for(int i = (j); i <= (k); ++i)
#define Rep(i, j, k) for(int i = (j); i >= (k); --i)
#define sz(a) ((int) (a).size())
const int mod = 998244353, _G = 3, N = (1 << 21), inv2 = (mod + 1) / 2;
#define add(a, b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a, b) (a < b ? a - b + mod : a - b)
int qpow(int x, int y = mod - 2) {
int res = 1;
for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod;
return res;
}
int fac[N + 1], ifac[N + 1], inv[N + 1];
void init(int x) {
fac[0] = ifac[0] = inv[1] = 1;
Fo(i, 2, x) inv[i] = (ll) inv[mod % i] * (mod - mod / i) % mod;
Fo(i, 1, x) fac[i] = (ll) fac[i - 1] * i % mod, ifac[i] = (ll) ifac[i - 1] * inv[i] % mod;
}
int C(int x, int y) {
return y < 0 || x < y ? 0 : (ll) fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
inline int sgn(int x) {
return (x & 1) ? mod - 1 : 1;
}
int rt[N], Lim;
void Pinit(int x) {
for(Lim = 1; Lim <= x; Lim <<= 1) ;
for(int i = 1; i < Lim; i <<= 1) {
int sG = qpow (_G, (mod - 1) / (i << 1));
rt[i] = 1;
Fo(j, i + 1, i * 2 - 1) rt[j] = (ll) rt[j - 1] * sG % mod;
}
}
struct poly {
vector<int> a;
int size() { return sz(a); }
int & operator [] (int x) { return a[x]; }
int v(int x) { return x < 0 || x >= sz(a) ? 0 : a[x]; }
void clear() { vector<int> ().swap(a); }
void rs(int x = 0) { a.resize(x); }
poly (int n = 0) { rs(n); }
poly (vector<int> o) { a = o; }
poly (const poly &o) { a = o.a; }
poly Rs(int x = 0) { vector<int> res = a; res.resize(x); return res; }
inline void dif() {
int n = sz(a);
for (int l = n >> 1; l >= 1; l >>= 1)
for(int j = 0; j < n; j += l << 1)
for(int k = 0, *w = rt + l; k < l; k++, w++) {
int x = a[j + k], y = a[j + k + l];
a[j + k] = add(x, y);
a[j + k + l] = (ll) * w * dec(x, y) % mod;
}
}
void dit () {
int n = sz(a);
for(int i = 2; i <= n; i <<= 1)
for(int j = 0, l = (i >> 1); j < n; j += i)
for(int k = 0, *w = rt + l; k < l; k++, w++) {
int pa = a[j + k], pb = (ll) a[j + k + l] * *w % mod;
a[j + k] = add(pa, pb), a[j + k + l] = dec(pa, pb);
}
reverse(a.begin() + 1, a.end());
for(int i = 0, iv = qpow(n); i < n; i++) a[i] = (ll) a[i] * iv % mod;
}
friend poly operator * (poly aa, poly bb) {
if(!sz(aa) || !sz(bb)) return {};
int lim, all = sz(aa) + sz(bb) - 1;
for(lim = 1; lim < all; lim <<= 1);
aa.rs(lim), bb.rs(lim), aa.dif(), bb.dif();
Fo(i, 0, lim - 1) aa[i] = (ll) aa[i] * bb[i] % mod;
aa.dit(), aa.a.resize(all);
return aa;
}
poly Inv() {
poly res, f, g;
res.rs(1), res[0] = qpow(a[0]);
for(int m = 1, pn; m < sz(a); m <<= 1) {
pn = m << 1, f = res, g.rs(pn), f.rs(pn);
for(int i = 0; i < pn; i++) g[i] = (*this).v(i);
f.dif(), g.dif();
for(int i = 0; i < pn; i++) g[i] = (ll) f[i] * g[i] % mod;
g.dit();
for(int i = 0; i < m; i++) g[i] = 0;
g.dif();
for(int i = 0; i < pn; i++) g[i] = (ll) f[i] * g[i] % mod;
g.dit(), res.rs(pn);
for(int i = m; i < min(pn, sz(a)); i++) res[i] = (mod - g[i]) % mod;
}
return res.rs(sz(a)), res;
}
poly Shift (int x) {
poly zm (sz(a) + x);
Fo(i, max(-x, 0ll), sz(a) - 1) zm[i + x] = a[i];
return zm;
}
friend poly operator * (poly aa, int bb) {
poly res(sz(aa));
Fo(i, 0, sz(aa) - 1) res[i] = (ll) aa[i] * bb % mod;
return res;
}
friend poly operator + (poly aa, poly bb) {
vector<int> res(max(sz(aa), sz(bb)));
Fo(i, 0, sz(res) - 1) res[i] = add(aa.v(i), bb.v(i));
return poly(res);
}
friend poly operator - (poly aa, poly bb) {
vector<int> res(max(sz(aa), sz(bb)));
Fo(i, 0, sz(res) - 1) res[i] = dec(aa.v(i), bb.v(i));
return poly(res);
}
poly & operator += (poly o) {
rs(max(sz(a), sz(o)));
Fo(i, 0, sz(a) - 1) (a[i] += o.v(i)) %= mod;
return (*this);
}
poly & operator -= (poly o) {
rs(max(sz(a), sz(o)));
Fo(i, 0, sz(a) - 1) (a[i] += mod - o.v(i)) %= mod;
return (*this);
}
poly & operator *= (poly o) {
return (*this) = (*this) * o;
}
poly Integ() {
if(!sz(a)) return poly();
poly res(sz(a) + 1);
Fo(i, 1, sz(a)) res[i] = (ll) a[i - 1] * inv[i] % mod;
return res;
}
poly Deriv() {
if(!sz(a)) return poly();
poly res(sz(a) - 1);
Fo(i, 1, sz(a) - 1) res[i - 1] = (ll) a[i] * i % mod;
return res;
}
poly Ln() {
poly g = ((*this).Inv() * (*this).Deriv()).Integ();
return g.rs(sz(a)), g;
}
poly Exp() {
poly res(1), f;
res[0] = 1;
for(int m = 1, pn; m < sz(a); m <<= 1) {
pn = min(m << 1, sz(a)), f.rs(pn), res.rs(pn);
for(int i = 0; i < pn; i++) f[i] = (*this).v(i);
f -= res.Ln(), (f[0] += 1) %= mod, res *= f, res.rs(pn);
}
return res.rs(sz(a)), res;
}
poly pow(int x, int rx = -1) { // x : the power % mod; rx : the power % (mod - 1)
if(rx == -1) rx = x;
int cnt = 0;
while (a[cnt] == 0 && cnt < sz(a)) cnt += 1;
poly res = (*this);
Fo(i, cnt, sz(a) - 1) res[i - cnt] = res[i];
Fo(i, sz(a) - cnt, sz(a) - 1) res[i] = 0;
int c = res[0], w = qpow (res[0]);
Fo(i, 0, sz(res) - 1) res[i] = (ll) res[i] * w % mod;
res = res.Ln();
Fo(i, 0, sz(res) - 1) res[i] = (ll) res[i] * x % mod;
res = res.Exp();
c = qpow (c, rx);
Fo(i, 0, sz(res) - 1) res[i] = (ll) res[i] * c % mod;
if((ll) cnt * x > sz(a)) Fo(i, 0, sz(a) - 1) res[i] = 0;
else if(cnt) {
Rep(i, sz(a) - cnt * x - 1, 0) res[i + cnt * x] = res[i];
Fo(i, 0, cnt * x - 1) res[i] = 0;
}
return res;
}
poly sqrt(int rt = 1) {
poly res(1), f;
res[0] = rt;
for(int m = 1, pn; m < sz(a); m <<= 1) {
pn = min(m << 1, sz(a)), f.rs(pn);
for(int i = 0; i < pn; i++) f[i] = (*this).v(i);
f += res * res, f.rs(pn), res.rs(pn), res = f * res.Inv(), res.rs(pn);
for(int i = 0; i < pn; i++) res[i] = (ll) res[i] * inv2 % mod;
}
return res;
}
void Rev() {
reverse(a.begin(), a.end());
}
friend pair < poly, poly > div (poly f, poly g) { /* f / g = first, f % g = second */
f.rs(max(sz(f), sz(g))), f.Rev(), g.Rev();
int n = sz(f), m = sz(g);
poly A = g.Rs(n - m + 1).Inv(), t;
A *= f.Rs(n - m + 1), A.rs(n - m + 1), A.Rev(), g.Rev(), f.Rev(), t = f - A * g, t.rs(m - 1);
return make_pair(A, t);
}
};
动态规划
01背包模型
const int N = 100010;
int dp[N], w[N], v[N];
int main(){
int n,m;
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
完全背包模型
const int N = 100010;
int dp[N], w[N], v[N];
int main(){
int n,m;
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
多重背包模型
int f[1010];
int a[10005],b[10005],c[10005]; //体积、价值、次数
int cnt,co[1000005],v[1000005];//尽可能开大，不要把空间开爆了 二进制优化后体积，价值
int main(){
int n,m;
//输入 a,b,c;
//
auto pre = [&](){
for(int i=1;i<=n;i++) {
int t=1;
while(c[i]) {
co[++cnt]=t*a[i];
v[cnt]=t*b[i];
c[i]-=t; t*=2;
if(c[i]<t) {//如果剩下的不能再拆，就直接放在一起
co[++cnt]=a[i]*c[i];
v[cnt]=b[i]*c[i];
break;
}
}
}
};
pre();
//01背包板子
for(int i=1;i<=cnt;i++){
for(int j=m;j>=co[i];j--){
f[j]=max(f[j],f[j-co[i]]+v[i]);
}
}
//
}
最长公共子序列
#include<bits/stdc++.h>
using namespace std;
//最长公共子序列
const int N=101000;
int a[N],ind[N],n;
int main(){
cin>>n;
int tmp;
memset(a,0x3f,sizeof(a));
for (int i=1;i<=n;i++){
cin>>tmp;
ind[tmp]=i;
}
for (int i=1;i<=n;i++){
cin>>tmp;
int x=ind[tmp];
*lower_bound(a+1,a+n+1,x)=x;
}
cout<<(lower_bound(a+1,a+n+1,a[0])-a-1);
return 0;
}
最长上升子序列(严格单调递增)
#include<bits/stdc++.h>
using namespace std;
//最长上升子序列(严格单调递增)
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int n;
cin>>n;
vector<int> a(n);
vector<int> st;
for(int i=0;i<n;i++){
cin>>a[i];
}
st.push_back(a[0]);
for(int i=1;i<n;i++){
if(a[i]>st.back()){
st.push_back(a[i]);
}else{
*lower_bound(st.begin(),st.end(),a[i]) = a[i];
}
}
cout<<st.size();
return 0;
}
拆位异或和
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000010;
int dp[N];
int cnt[2];
signed main(){
int n;
cin>>n;
vector<int> a(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
int sum=0;
for(int i=0;i<=20;i++){
for(int j=1;j<=n;j++){
if((a[j]>>i)&1) dp[j]=dp[j-1]^1;
else dp[j]=dp[j-1];
}
cnt[0]=cnt[1]=0;
for(int i=0;i<=n;i++){
cnt[dp[i]]++;
}
sum+=(1ll<<i)*cnt[0]*cnt[1];
}
cout<<sum<<"\n";
return 0;
}
数位dp
int work(int x,int t){
string str=to_string(x);
int m=str.size();
int mem[200][200];
memset(mem,-1,sizeof(mem));
function<int(int,int,bool,bool)> dfs = [&](int i,int sum,bool limit,bool isnum)->int{
if(i==m) return isnum?sum:0;
if(!limit&&isnum&&mem[i][sum]!=-1) return mem[i][sum];
int res=0;
if(!isnum) res=dfs(i+1,sum,false,false);
int up=limit?str[i]-'0':9;
for(int d=1-isnum;d<=up;d++){
res+=dfs(i+1,sum+(d==t),limit&&d==up,true);
}
if(!limit&&isnum){
mem[i][sum]=res;
}
return res;
};
return dfs(0,0,true,false);
}
图论树论
树论大板子
struct Tree {
int n;
vector<vector<pair<int, int>>> e;
vector<int> dep, parent, maxdep, d1, d2, s1, s2, up;
Tree(int n) {
this->n = n;
e.resize(n + 1);
dep.resize(n + 1);
parent.resize(n + 1);
maxdep.resize(n + 1);
d1.resize(n + 1);
d2.resize(n + 1);
s1.resize(n + 1);
s2.resize(n + 1);
up.resize(n + 1);
}
void add(int u, int v, int w) {
e[u].push_back({w, v});
e[v].push_back({w, u});
}
void dfs(int u, int fa) {
maxdep[u] = dep[u];
for (auto [w, v] : e[u]) {
if (v == fa) continue;
dep[v] = dep[u] + 1;
parent[v] = u;
dfs(v, u);
maxdep[u] = max(maxdep[u], maxdep[v]);
}
}
void dfs1(int u, int fa) {
for (auto [w, v] : e[u]) {
if (v == fa) continue;
dfs1(v, u);
int x = d1[v] + w;
if (x > d1[u]) {
d2[u] = d1[u], s2[u] = s1[u];
d1[u] = x, s1[u] = v;
} else if (x > d2[u]) {
d2[u] = x, s2[u] = v;
}
}
}
void dfs2(int u, int fa) {
for (auto [w, v] : e[u]) {
if (v == fa) continue;
if (s1[u] == v) {
up[v] = max(up[u], d2[u]) + w;
} else {
up[v] = max(up[u], d1[u]) + w;
}
dfs2(v, u);
}
}
int radius, center, diam;
void getCenter() {
center = 1; //中心
for (int i = 1; i <= n; i++) {
if (max(d1[i], up[i]) < max(d1[center], up[center])) {
center = i;
}
}
radius = max(d1[center], up[center]); //距离最远点的距离的最小值
diam = d1[center] + up[center] + 1; //直径
}
int rem; //删除重心后剩余连通块体积的最小值
int cog; //重心
vector<bool> vis;
void getCog() {
vis.resize(n);
rem = INT_MAX;
cog = 1;
dfsCog(1);
}
int dfsCog(int u) {
vis[u] = true;
int s = 1, res = 0;
for (auto [w, v] : e[u]) {
if (vis[v]) continue;
int t = dfsCog(v);
res = max(res, t);
s += t;
}
res = max(res, n - s);
if (res < rem) {
rem = res;
cog = u;
}
return s;
}
};
树论板子2
#include<bits/stdc++.h>
using namespace std;
struct Tree {
int n;
vector<vector<int>> ver, val;
vector<int> lg, dep, wid;//深度，宽度
Tree(int n) {
this->n = n;
ver.resize(n + 1);
val.resize(n + 1, vector<int>(30));
lg.resize(n + 1);
dep.resize(n + 1);
for (int i = 1; i <= n; i++) { //预处理 log
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
}
void add(int x, int y) {
ver[x].push_back(y);
}
void dfs(int x, int fa) {
val[x][0] = fa; // 储存 x 的父节点
dep[x] = dep[fa] + 1;
for (int i = 1; i <= lg[dep[x]]; i++) {
val[x][i] = val[val[x][i - 1]][i - 1];
}
for (auto y : ver[x]) {
if (y == fa) continue;
dfs(y, x);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
while (dep[x] > dep[y]) {
x = val[x][lg[dep[x] - dep[y]] - 1];
}
if (x == y) return x;
for (int k = lg[dep[x]] - 1; k >= 0; k--) {
if (val[x][k] == val[y][k]) continue;
x = val[x][k];
y = val[y][k];
}
return val[x][0];
}
int calc(int x, int y) { // 倍增查询两点间距离
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
void work(int root = 1) { // 在此初始化
dfs(root, 0);
bfs(root);
}
void bfs(int rt){
queue<int> q,tmp;
q.push(rt);
int ind=0;
while(ind<n){
while(q.size()){
int x=q.front();
ind++;
q.pop();
for(auto &v: ver[x]){
tmp.push(v);
}
}
int cnt=0;
while(tmp.size()){
q.push(tmp.front());
tmp.pop();
cnt++;
}
wid.push_back(cnt);
}
}
};
带权图LCA
#include<bits/stdc++.h>
using namespace std;
struct Tree {
int n;
vector<vector<int>> val, Max;
vector<vector<pair<int, int>>> ver;
vector<int> lg, dep;
Tree(int n) {
this->n = n;
ver.resize(n + 1);
val.resize(n + 1, vector<int>(30));
Max.resize(n + 1, vector<int>(30));
lg.resize(n + 1);
dep.resize(n + 1);
for (int i = 1; i <= n; i++) { //预处理 log
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
}
void add(int x, int y, int w) { // 建立双向边
ver[x].push_back({y, w});
ver[y].push_back({x, w});
}
void dfs(int x, int fa) {
val[x][0] = fa;
dep[x] = dep[fa] + 1;
for (int i = 1; i <= lg[dep[x]]; i++) {
val[x][i] = val[val[x][i - 1]][i - 1];
Max[x][i] = max(Max[x][i - 1], Max[val[x][i - 1]][i - 1]);
}
for (auto [y, w] : ver[x]) {
if (y == fa) continue;
Max[y][0] = w;
dfs(y, x);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
while (dep[x] > dep[y]) {
x = val[x][lg[dep[x] - dep[y]] - 1];
}
if (x == y) return x;
for (int k = lg[dep[x]] - 1; k >= 0; k--) {
if (val[x][k] == val[y][k]) continue;
x = val[x][k];
y = val[y][k];
}
return val[x][0];
}
int clac(int x, int y) { // 倍增查询两点间距离
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
int query(int x, int y) { // 倍增查询两点路径上的最大边权（带权图）
auto get = [&](int x, int y) -> int {
int ans = 0;
if (x == y) return ans;
for (int i = lg[dep[x]]; i >= 0; i--) {
if (dep[val[x][i]] > dep[y]) {
ans = max(ans, Max[x][i]);
x = val[x][i];
}
}
ans = max(ans, Max[x][0]);
return ans;
};
int fa = lca(x, y);
return max(get(x, fa), get(y, fa));
}
void work(int root = 1) { // 在此初始化
dfs(root, 0);
}
};
染色法判二分图
struct BipGraph{
vector<vector<int>> adj;
vector<int> color;
int n;
BipGraph(int n):n(n){
adj.resize(n+1);
color.resize(n+1);
}
void add(int a,int b){
adj[a].push_back(b);
adj[b].push_back(a);
}
bool dfs(int u,int c){
color[u] = c;
for(auto v:adj[u]){
int b = v;
if(!color[b]){
if(!dfs(b, 3 - c)) return false;
}
else if(color[b] && color[b] != 3 - c){
return false;
}
}
return true;
}
bool check(){
for(int i=1;i<=n;i++){
if(!color[i]){
if(!dfs(i,1)){
return false;
}
}
}
return true;
}
};
二分图最大匹配
#include<bits/stdc++.h>
using namespace std;
//二分图最大匹配
struct HopcroftKarp {
vector<vector<int>> g;
vector<int> pa, pb, vis;
int n, m, dfn, res;
HopcroftKarp(int _n, int _m) : n(_n + 1), m(_m + 1) {
assert(0 <= n && 0 <= m);
pa.assign(n, -1);
pb.assign(m, -1);
vis.resize(n);
g.resize(n);
res = 0;
dfn = 0;
}
void add(int x, int y) {
assert(0 <= x && x < n && 0 <= y && y < m);
g[x].push_back(y);
}
bool dfs(int v) {
vis[v] = dfn;
for (int u : g[v]) {
if (pb[u] == -1) {
pb[u] = v;
pa[v] = u;
return true;
}
}
for (int u : g[v]) {
if (vis[pb[u]] != dfn && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int work() {
while (1) {
dfn++;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
cnt++;
}
}
if (cnt == 0) break;
res += cnt;
}
return res;
}
};
signed main() {
int n1, n2, m;
cin >> n1 >> n2 >> m;
HopcroftKarp flow(n1, n2);
while (m--) {
int x, y;
cin >> x >> y;
flow.add(x, y);
}
cout << flow.work() << endl;
}
二分图最大权匹配
#include<bits/stdc++.h>
using namespace std;
//二分图最大权匹配
struct MaxCostMatch {
vector<int> ansl, ansr, pre;
vector<int> lx, ly;
vector<vector<int>> ver;
int n;
MaxCostMatch(int n) : n(n) {
ver.resize(n + 1, vector<int>(n + 1));
ansl.resize(n + 1, -1);
ansr.resize(n + 1, -1);
lx.resize(n + 1);
ly.resize(n + 1, -1E18);
pre.resize(n + 1);
}
void add(int x, int y, int w) {
ver[x][y] = w;
}
void bfs(int x) {
vector<bool> visl(n + 1), visr(n + 1);
vector<int> slack(n + 1, 1E18);
queue<int> q;
function<bool(int)> check = [&](int x) {
visr[x] = 1;
if (~ansr[x]) {
q.push(ansr[x]);
visl[ansr[x]] = 1;
return false;
}
while (~x) {
ansr[x] = pre[x];
swap(x, ansl[pre[x]]);
}
return true;
};
q.push(x);
visl[x] = 1;
while (1) {
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y = 1; y <= n; ++y) {
if (visr[y]) continue;
int del = lx[x] + ly[y] - ver[x][y];
if (del < slack[y]) {
pre[y] = x;
slack[y] = del;
if (!slack[y] && check(y)) return;
}
}
}
int val = 1E18;
for (int i = 1; i <= n; ++i) {
if (!visr[i]) {
val = min(val, slack[i]);
}
}
for (int i = 1; i <= n; ++i) {
if (visl[i]) lx[i] -= val;
if (visr[i]) {
ly[i] += val;
} else {
slack[i] -= val;
}
}
for (int i = 1; i <= n; ++i) {
if (!visr[i] && !slack[i] && check(i)) {
return;
}
}
}
}
int work() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
ly[i] = max(ly[i], ver[j][i]);
}
}
for (int i = 1; i <= n; ++i) bfs(i);
int res = 0;
for (int i = 1; i <= n; ++i) {
res += ver[i][ansl[i]];
}
return res;
}
void getMatch(int x, int y) { // 获取方案 (0代表无匹配)
for (int i = 1; i <= x; ++i) {
cout << (ver[i][ansl[i]] ? ansl[i] : 0) << " ";
}
cout << endl;
for (int i = 1; i <= y; ++i) {
cout << (ver[i][ansr[i]] ? ansr[i] : 0) << " ";
}
cout << endl;
}
};
signed main() {
int n1, n2, m;
cin >> n1 >> n2 >> m;
MaxCostMatch match(max(n1, n2));
for (int i = 1; i <= m; i++) {
int x, y, w;
cin >> x >> y >> w;
match.add(x, y, w);
}
cout << match.work() << '\n';
match.getMatch(n1, n2);
}
Prim
#define INF 0x3f3f3f3f
//稠密图
const int N = 550;
int g[N][N],d[N],v[N];
struct Prim{
int n;
Prim(int n):n(n){
memset(g,INF,sizeof(g));
memset(d,INF,sizeof(d));
}
void add(int x,int y,int w){
g[x][y]=g[y][x]=min(g[x][y],w);
}
int work() {
int ans = 0;
for (int i = 0; i < n; ++ i) {
int t = -1;
for (int j = 1; j <= n; ++ j)
if (v[j] == 0 && (t == -1 || d[j] < d[t]))
t = j;
v[t] = 1;
if (i && d[t] == INF) return INF;
if (i) ans += d[t];
for (int j = 1; j <= n; ++ j) d[j] = min(d[j], g[t][j]);
}
return ans;
}
};
Kruskal
struct DSU{
vector<int> p,size;
DSU(){}
DSU(int n){
init(n);
}
void init(int n){
p.resize(n+1);
iota(p.begin(),p.end(),0);
size.assign(n+1,1);
}
bool same(int a,int b){
return find(a)==find(b);
}
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
bool merge(int a,int b){
a=find(a);
b=find(b);
if(same(a,b)){
return false;
}
size[b]+=size[a];
p[a]=b;
return true;
}
int getSize(int x){
return size[find(x)];
}
};
struct Kruskal{
struct Edge{
int u,v,w;
};
int n,k;
vector<Edge> g;
Kruskal(int n,int k=1){
this->n=n;
this->k=k;
}
void add(int u,int v,int w){
g.push_back({u,v,w});
}
int work(){
DSU d(n);
int ans=0,cnt=0;
sort(g.begin(),g.end(),[&](Edge a,Edge b){
return a.w<b.w;
});
for(int i=0;i<g.size();i++){
int eu=d.find(g[i].u);
int ev=d.find(g[i].v);
if(eu==ev){
continue;
}
ans+=g[i].w;
d.merge(ev,eu);
if(++cnt==n-k){
break;
}
}
if(cnt!=n-k){
return 0x80808080;
}
return ans;
}
};
Dijkstra
template<typename T>
struct Dijkstra{
struct Node{
int v;
T w;
};
vector<vector<Node>> adj;
vector<T> dis;
vector<bool> vis;
Dijkstra(ll n){
adj.resize(n+1);
dis.resize(n+1,INF);
vis.resize(n+1);
}
void work(int st){
dis[st]=0;
priority_queue<pair<T,int>> pq;
pq.push({0,st});
while(pq.size()){
auto a = pq.top();
pq.pop();
int u=a.second;
if(vis[u]){
continue;
}
vis[u]=true;
for(auto &t:adj[u]){
int v=t.v;
T w=t.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
pq.push({-dis[v],v});
}
}
}
}
void add(int u,int v,T w){
if(u!=v){
adj[u].push_back({v,w});
}
}
T query(int ed){
return dis[ed];
}
};
SPFA
struct SPFA{
#define INFI 0x3f3f3f3f
#define NINFI 0x80808080
struct Node{
int v,w;
};
int n;
vector<vector<Node>> G;
vector<int> dis;
vector<int> cnt;
vector<bool> in;
SPFA(int n){
this->n=n;
G.resize(n+1);
}
//存在负环为true
bool work_sp(int st){
dis.resize(n+1,INFI);
in.resize(n+1,false);
cnt.resize(n+1,0);
queue <int> q;
q.push(st);
dis[st] = 0;
in[st] = true;
cnt[st] = 1;
while (!q.empty()){
int u = q.front();
q.pop();
in[u] = false;
for (auto &t:G[u]){
int v = t.v;
int w = t.w;
if (dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if (!in[v]){
cnt[v]++;
q.push(v);
in[v] = true;
if (cnt[v] >= n){
return true;
}
}
}
}
}
return false;
}
bool work_lp(int st){
dis.resize(n+1,NINFI);
in.resize(n+1,false);
cnt.resize(n+1,0);
queue <int> q;
q.push(st);
dis[st] = 0;
in[st] = true;
cnt[st] = 1;
while (!q.empty()){
int u = q.front();
q.pop();
in[u] = false;
for (auto &t:G[u]){
int v = t.v;
int w = t.w;
if (dis[v] < dis[u] + w){
dis[v] = dis[u] + w;
if (!in[v]){
cnt[v]++;
q.push(v);
in[v] = true;
if (cnt[v] >= n){
return true;
}
}
}
}
}
return false;
}
void add_one(int u,int v,int w){
G[u].push_back({v,w});
}
void add_two(int u,int v,int w){
G[u].push_back({v,w});
if(w>=0){
G[v].push_back({u,w});
}
}
int query(int n){
return dis[n];
}
};
Floyd
template<typename T>
struct Floyd{
#define MAXN 201
vector<T> d[MAXN];
int n;
Floyd(int n):n(n){
for(int i=0;i<=n;i++){
d[i].resize(n+1,INF);
for(int j=0;j<=n;j++){
if(i==j){
d[i][j]=0;
}
}
}
}
void work(){
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
// d[i][j] = max(d[i][j], min(d[i][k] , d[k][j])); 传递闭包
}
T query(int st,int ed){
if(d[st][ed]>INF/2){
return 0x80808080;
}
return d[st][ed];
}
void add(int u,int v,T w){
d[u][v]=min(d[u][v],w);
}
int cog;
T getCog(vector<int> surr){
MinSum(surr);
return cog;
}
T MinSum(vector<int> surr){
T Minval=INF;
for(int i=1;i<=n;i++){
T sum=0;
for(auto &v:surr){
sum+=query(i,v);
}
if(sum<Minval){
cog=i;
Minval=min(Minval,sum);
}
}
return Minval;
}
};
最大流
constexpr int inf = 1E9;
template<class T>
struct MaxFlow {
struct _Edge {
int to;
T cap;
_Edge(int to, T cap) : to(to), cap(cap) {}
};
int n;
std::vector<_Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> cur, h;
MaxFlow() {}
MaxFlow(int n) {
init(n+2);
}
void init(int n) {
this->n = n;
e.clear();
g.assign(n, {});
cur.resize(n);
h.resize(n);
}
bool bfs(int s, int t) {
h.assign(n, -1);
std::queue<int> que;
h[s] = 0;
que.push(s);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (int i : g[u]) {
auto [v, c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t) {
return true;
}
que.push(v);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) {
return f;
}
auto r = f;
for (int &i = cur[u]; i < int(g[u].size()); ++i) {
const int j = g[u][i];
auto [v, c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
auto a = dfs(v, t, std::min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0) {
return f;
}
}
}
return f - r;
}
void addEdge(int u, int v, T c) {
g[u].push_back(e.size());
e.emplace_back(v, c);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
T flow(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, std::numeric_limits<T>::max());
}
return ans;
}
std::vector<bool> minCut() {
std::vector<bool> c(n);
for (int i = 0; i < n; i++) {
c[i] = (h[i] != -1);
}
return c;
}
struct Edge {
int from;
int to;
T cap;
T flow;
};
std::vector<Edge> edges() {
std::vector<Edge> a;
for (int i = 0; i < e.size(); i += 2) {
Edge x;
x.from = e[i + 1].to;
x.to = e[i].to;
x.cap = e[i].cap + e[i + 1].cap;
x.flow = e[i + 1].cap;
a.push_back(x);
}
return a;
}
};
网络流+可行流
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct MCFGraph {
struct Edge {
int v, c, f;
Edge(int v, int c, int f) : v(v), c(c), f(f) {}
};
const int n;
std::vector<Edge> e;
std::vector<std::vector<int>> g;
std::vector<ll> h, dis;
std::vector<int> pre;
bool dijkstra(int s, int t) {
dis.assign(n, std::numeric_limits<ll>::max());
pre.assign(n, -1);
std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<std::pair<ll, int>>> que;
dis[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
ll d = que.top().first;
int u = que.top().second;
que.pop();
if (dis[u] < d) continue;
for (int i : g[u]) {
int v = e[i].v;
int c = e[i].c;
int f = e[i].f;
if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
dis[v] = d + h[u] - h[v] + f;
pre[v] = i;
que.emplace(dis[v], v);
}
}
}
return dis[t] != std::numeric_limits<ll>::max();
}
MCFGraph(int n) : n(n+1), g(n+1) {}
//可行流
// void addEdge(int u, int v, int c, int f) {
// if (f < 0) {
// g[u].push_back(e.size());
// e.emplace_back(v, 0, f);
// g[v].push_back(e.size());
// e.emplace_back(u, c, -f);
// } else {
// g[u].push_back(e.size());
// e.emplace_back(v, c, f);
// g[v].push_back(e.size());
// e.emplace_back(u, 0, -f);
// }
// }
//最大流
void addEdge(int u, int v, int c, int f) { // 最大流
g[u].push_back(e.size());
e.emplace_back(v, c, f);
g[v].push_back(e.size());
e.emplace_back(u, 0, -f);
}
std::pair<int, ll> flow(int s, int t) {
int flow = 0;
ll cost = 0;
h.assign(n, 0);
while (dijkstra(s, t)) {
for (int i = 0; i < n; ++i) h[i] += dis[i];
int aug = std::numeric_limits<int>::max();
for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);
for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
e[pre[i]].c -= aug;
e[pre[i] ^ 1].c += aug;
}
flow += aug;
cost += ll(aug) * h[t];
}
return std::make_pair(flow, cost);
}
};
预流推进最大流
template <typename T> struct PushRelabel {
const int inf = 0x3f3f3f3f;
const T INF = 0x3f3f3f3f3f3f3f3f;
struct Edge {
int to, cap, flow, anti;
Edge(int v = 0, int w = 0, int id = 0) : to(v), cap(w), flow(0), anti(id) {}
};
vector<vector<Edge>> e;
vector<vector<int>> gap;
vector<T> ex; // 超额流
vector<bool> ingap;
vector<int> h;
int n, gobalcnt, maxH = 0;
T maxflow = 0;
PushRelabel(int n) : n(n), e(n + 1), ex(n + 1), gap(n + 1) {}
void addedge(int u, int v, int w) {
e[u].push_back({v, w, (int)e[v].size()});
e[v].push_back({u, 0, (int)e[u].size() - 1});
}
void PushEdge(int u, Edge &edge) {
int v = edge.to, d = min(ex[u], 1LL * edge.cap - edge.flow);
ex[u] -= d;
ex[v] += d;
edge.flow += d;
e[v][edge.anti].flow -= d;
if (h[v] != inf && d > 0 && ex[v] == d && !ingap[v]) {
++gobalcnt;
gap[h[v]].push_back(v);
ingap[v] = 1;
}
}
void PushPoint(int u) {
for (auto k = e[u].begin(); k != e[u].end(); k++) {
if (h[k->to] + 1 == h[u] && k->cap > k->flow) {
PushEdge(u, *k);
if (!ex[u]) break;
}
}
if (!ex[u]) return;
if (gap[h[u]].empty()) {
for (int i = h[u] + 1; i <= min(maxH, n); i++) {
for (auto v : gap[i]) {
ingap[v] = 0;
}
gap[i].clear();
}
}
h[u] = inf;
for (auto [to, cap, flow, anti] : e[u]) {
if (cap > flow) {
h[u] = min(h[u], h[to] + 1);
}
}
if (h[u] >= n) return;
maxH = max(maxH, h[u]);
if (!ingap[u]) {
gap[h[u]].push_back(u);
ingap[u] = 1;
}
}
void init(int t, bool f = 1) {
ingap.assign(n + 1, 0);
for (int i = 1; i <= maxH; i++) {
gap[i].clear();
}
gobalcnt = 0, maxH = 0;
queue<int> q;
h.assign(n + 1, inf);
h[t] = 0, q.push(t);
while (q.size()) {
int u = q.front();
q.pop(), maxH = h[u];
for (auto &[v, cap, flow, anti] : e[u]) {
if (h[v] == inf && e[v][anti].cap > e[v][anti].flow) {
h[v] = h[u] + 1;
q.push(v);
if (f) {
gap[h[v]].push_back(v);
ingap[v] = 1;
}
}
}
}
}
T work(int s, int t) {
init(t, 0);
if (h[s] == inf) return maxflow;
h[s] = n;
ex[s] = INF;
ex[t] = -INF;
for (auto k = e[s].begin(); k != e[s].end(); k++) {
PushEdge(s, *k);
}
while (maxH > 0) {
if (gap[maxH].empty()) {
maxH--;
continue;
}
int u = gap[maxH].back();
gap[maxH].pop_back();
ingap[u] = 0;
PushPoint(u);
if (gobalcnt >= 10 * n) {
init(t);
}
}
ex[s] -= INF;
ex[t] += INF;
return maxflow = ex[t];
}
};
数据结构
单调队列
//查询区间k的最大最小值。
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100010;
deque<int> D;
int n,k,x,a[MAX];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
while(!D.empty() && a[D.back()]<=a[i]) D.pop_back();
D.emplace_back(i);
if(!D.empty()) if(i-D.front()>=k) D.pop_front();
if(i>=k)cout<<a[D.front()]<<endl;
}
return 0;
}
DSU
struct DSU{
vector<int> p,size;
DSU(){}
DSU(int n){
init(n);
}
void init(int n){
p.resize(n+1);
iota(p.begin(),p.end(),0);
size.assign(n+1,1);
}
bool same(int a,int b){
return find(a)==find(b);
}
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
bool merge(int a,int b){
a=find(a);
b=find(b);
if(same(a,b)){
return false;
}
size[b]+=size[a];
p[a]=b;
return true;
}
int getSize(int x){
return size[find(x)];
}
};
ST表
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int a[N],dp_max[N][22],dp_min[N][21];
void init(){ //先输入a再init a从下标1输入
for(int i=1;i<=n;i++){
dp_min[i][0]=a[i];
dp_max[i][0]=a[i];
}
int p=log2(n);
for(int k=1;k<=p;k++){
for(int s=1;s+(1<<k)<=n+1;s++){
dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]);
dp_min[s][k]=min(dp_min[s][k-1],dp_min[s+(1<<(k-1))][k-1]);
}
}
}
int query(int L,int R){
int k = log2(R-L+1);
int x=max(dp_max[L][k],dp_max[R-(1<<k)+1][k]);//取区间最大
int y=min(dp_min[L][k],dp_min[R-(1<<k)+1][k]);//取区间最小
return x;
}
线段树
const int N = 1e6+10;
#define ls(x) x<<1
#define rs(x) x<<1|1
struct Node{
int l,r;
}tr[N<<2];
int a[N];
void pushup(int u){
}
void build(int u,int l,int r){
if(l==r){
return;
}
tr[u]={l,r};
int mid=l+r>>1;
build(ls(u),l,mid);build(rs(u),mid+1,r);
pushup(u);
}
void modify(int u,int x,int v){
if(tr[u].l==x&&tr[u].r==x){
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid){
modify(ls(u),x,v);
}else{
modify(rs(u),x,v);
}
pushup(u);
}
int query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
}
int res=0;
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid){
res=query(ls(u),l,r);
}
if(r>mid){
}
return res;
}
懒标记线段树
const int N = 1e6+10;
#define ls(x) x<<1
#define rs(x) x<<1|1
struct Node{
int l,r;
}tr[N<<2];
int a[N];
void pushup(int u){
}
void build(int u,int l,int r){
if(l==r){
return;
}
tr[u]={l,r};
int mid=l+r>>1;
build(ls(u),l,mid);build(rs(u),mid+1,r);
pushup(u);
}
void apply(int u,int v){
}
void pushdown(int u){
}
void modify(int u,int l,int r,int v){
if(tr[u].l>=l&&tr[u].r<=r){
apply(u,v);
return;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid){
modify(ls(u),l,r,v);
}
if(r>mid){
modify(rs(u),l,r,v);
}
pushup(u);
}
int query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid){
res=query(ls(u),l,r);
}
if(r>mid){
}
return res;
}
珂朵莉树
struct ODT {
struct node {
int l, r;
mutable ll v;
node(int l, int r = -1, ll v = 0) : l(l), r(r), v(v) {}
bool operator<(const node &o) const {
return l < o.l;
}
};
set<node> s;
int sum=0;//区间一次和(特殊)
ODT() {
s.clear();
}
auto split(int pos) {
auto it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos) return it;
it--;
int l = it->l, r = it->r;
ll v = it->v;
s.erase(it);
s.insert(node(l, pos - 1, v));
return s.insert(node(pos, r, v)).first;
}
//区间赋值
void assign(int l, int r, ll x) {
auto itr = split(r + 1), itl = split(l) , it=itl;
for(;itl!=itr;++itl){
sum-=itl->v*(itl->r-itl->l+1);
}
s.erase(it, itr);
s.insert(node(l, r, x));
sum+=x*(r-l+1);
}
//区间加
void add(int l, int r, ll x) {
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++) {
it->v += x;
}
}
//区间第k小
ll kth(int l, int r, int k) {
vector<pair<ll, int>> a;
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++) {
a.push_back(pair<ll, int>(it->v, it->r - it->l + 1));
}
sort(a.begin(), a.end());
for (auto x : a) {
auto val = x.first;
auto len = x.second;
k -= len;
if (k <= 0) return val;
}
return 0;
}
ll power(ll a, int b, int mod) {
a %= mod;
ll res = 1;
for (; b; b /= 2, a = a * a % mod) {
if (b % 2) {
res = res * a % mod;
}
}
return res;
}
//区间幂次和
ll powersum(int l, int r, int x, int mod) {
auto itr = split(r + 1), itl = split(l);
ll ans = 0;
for (auto it = itl; it != itr; it++) {
ans = (ans + power(it->v, x, mod) * (it->r - it->l + 1) % mod) % mod;
}
return ans;
}
//区间一次和
ll sum_one(int l,int r,ll mod){
ll ret=0;
auto itl=split(l),itr=split(r+1);
for(;itl!=itr;itl++){
ret=(ret+(itl->r-itl->l+1)*itl->v)%mod;
}
return ret;
}
//匹配暴力搜索（质数搭配欧拉筛）
// void query(int l,int r){
// auto itr=split(r+1),itl=split(l);
// int res = 0;
// for (; itl != itr; itl ++ ){
// if (itl->v <= 1e7 && !st[itl->v])
// res += itl->r - itl->l + 1;
// }
// cout<<res<<"\n";
// }
};
ODT++
//ODT++
const ll MOD = 1e9+7;
struct node {
int l, r;
mutable ll v;
node(int l=0, int r = -1, ll v = 0) : l(l), r(r), v(v) {}
bool operator<(const node &o) const {
return l < o.l;
}
};
#define MAXN 500010
node a[MAXN],b[MAXN];
struct ODT {
set<node> s;
ODT() {
s.clear();
}
auto split(int pos) {
auto it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos) return it;
it--;
int l = it->l, r = it->r;
ll v = it->v;
s.erase(it);
s.insert(node(l, pos - 1, v));
return s.insert(node(pos, r, v)).first;
}
//区间赋值[推平]
void assign(int l, int r, ll x) {
auto itr = split(r + 1), itl = split(l) , it=itl;
s.erase(it, itr);
s.insert(node(l, r, x));
}
//区间加[l~r]每一个数加x
void add(int l, int r, ll x) {
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++) {
(it->v += x)%=MOD;
}
}
//区间第k小
ll kth(int l, int r, int k) {
vector<pair<ll, int>> a;
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++) {
a.push_back(pair<ll, int>(it->v, it->r - it->l + 1));
}
sort(a.begin(), a.end());
for (auto x : a) {
auto v = x.first;
auto len = x.second;
k -= len;
if (k <= 0) return v;
}
return 0;
}
ll power(ll a, int b) {
a %= MOD;
ll res = 1;
for (; b; b /= 2, a = a * a % MOD) {
if (b % 2) {
res = res * a % MOD;
}
}
return res;
}
//区间幂次和
ll powersum(int l, int r, int x) {
auto itr = split(r + 1), itl = split(l);
ll ans = 0;
for (auto it = itl; it != itr; it++) {
ans = (ans + power(it->v, x) * (it->r - it->l + 1) % MOD) % MOD;
}
return ans;
}
//区间一次和
ll sum_one(int l,int r){
ll ret=0;
auto itl=split(l),itr=split(r+1);
for(;itl!=itr;itl++){
(ret+=(ll)(itl->r-itl->l+1)*itl->v)%=MOD;
}
return ret;
}
// 匹配暴力搜索（质数搭配欧拉筛）
void query(int l,int r){
auto itr=split(r+1),itl=split(l);
int res = 0;
for (; itl != itr; itl ++ ){
// if (itl->v <= 1e7 && !st[itl->v])
// res += itl->r - itl->l + 1;
}
cout<<res<<"\n";
}
void insert(const int& x,vector<int>& a){
for(int i=1;i<=x;++i){
s.insert(node(i,i,a[i]));
}
}
void insert(int l,int r,int v){
s.insert(node{l,r,v});
}
void copy(int l1,int r1,int l2,int r2){
auto it1r=split(r1+1),it1l=split(l1);
int len=0;
for(auto it=it1l;it!=it1r;++it)
{
a[++len].l=it->l;
a[len].r=it->r;
a[len].v=it->v;
}
auto it2r=split(r2+1),it2l=split(l2);
s.erase(it2l,it2r);
for(int i=1;i<=len;++i)
{
s.insert(node(a[i].l - l1 + l2,a[i].r - l1 + l2,a[i].v));
}
}
void Swap(int l1,int r1,int l2,int r2){
if(l1>l2){swap(l1,l2);swap(r1,r2);}
int len1=0,len2=0;
auto it1r=split(r1+1),it1l=split(l1);
for(auto it=it1l;it!=it1r;++it)
{
a[++len1].l=it->l;
a[len1].r=it->r;
a[len1].v=it->v;
}
auto it2r=split(r2+1),it2l=split(l2);
for(auto it=it2l;it!=it2r;++it)
{
b[++len2].l=it->l;
b[len2].r=it->r;
b[len2].v=it->v;
}
it1r=split(r1+1),it1l=split(l1);
s.erase(it1l,it1r);
it2r=split(r2+1),it2l=split(l2);
s.erase(it2l,it2r);
for(int i=1;i<=len2;++i)s.insert(node(b[i].l - l2 + l1,b[i].r - l2 + l1,b[i].v));
for(int i=1;i<=len1;++i)s.insert(node(a[i].l - l1 + l2,a[i].r - l1 + l2,a[i].v));
}
void reverse(int l,int r){
if(l>r)swap(l,r);
auto it2=split(r+1),it1=split(l);
int len=0;
for(auto it=it1;it!=it2;++it)
{
a[++len].l=it->l;
a[len].r=it->r;
a[len].v=it->v;
}
s.erase(it1,it2);
for(int i=1;i<=len;++i)
{
s.insert(node(r-a[i].r+l, r-a[i].l+l, a[i].v));
}
}
void print(int n){
for(auto it=s.begin();it!=s.end()&&it->r<=n;++it){
for(int i=it->l;i<=it->r;++i) cout<<it->v<<" ";
}
cout<<"\n";
}
};
树状数组
template <typename T>
struct Fenwick {
int n;
vector<T> w;
Fenwick(int n) {
this->n = n;
w.resize(n + 1);
}
void add(int x, T k) {
for (; x <= n; x += x & -x) {
w[x] += k;
}
}
void add(int x, int y, T k) { // 区间修改
add(x, k), add(y + 1, -k);
}
T ask(int x) { //单点查询
auto ans = T();
for (; x; x -= x & -x) {
ans += w[x];
}
return ans;
}
T ask(int x, int y) { // 区间查询(区间和)
return ask(y) - ask(x - 1);
}
int kth(T k) { //查找第k大的值
int ans = 0;
for (int i = __lg(n); i >= 0; i--) {
int val = ans + (1 << i);
if (val < n && w[val] < k) {
k -= w[val];
ans = val;
}
}
return ans + 1;
}
};
//逆序对封装
template <typename T>
struct BIT {
int n;
vector<int> w;
BIT() {}
void add(int x, int k) {
for (; x <= n; x += x & -x) {
w[x] += k;
}
}
int ask(int x) {
int ans = 0;
for (; x; x -= x & -x) {
ans += w[x];
}
return ans;
}
int ask(int x, int y) {
return ask(y) - ask(x - 1);
}
int get(auto val) { // 获取逆序对数量
this->n = val.size() - 1; // 注意 n 不能 +1
w.resize(n + 1);
vector<pair<int, int>> alls;
for (int i = 1; i <= n; i++) {
alls.emplace_back(val[i], i);
}
sort(alls.begin(), alls.end());
int ans = 0;
for (auto [val, idx] : alls) {
ans += ask(idx + 1, n);
add(idx, 1);
}
return ans;
}
};
二维树状数组
//基础封装
template<typename T>
struct Fenwick2D {
int n, m;
vector<vector<T>> w;
Fenwick2D(int n, int m) : n(n), m(m) {
w.resize(n + 1, vector<T>(m + 1));
}
void add(int x, int y, T k) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
w[i][j] += k;
}
}
}
void add(int x, int y, int X, int Y, T k) { // 区块修改：二维差分
X++, Y++;
add(x, y, k), add(X, y, -k);
add(X, Y, k), add(x, Y, -k);
}
T ask(int x, int y) { // 单点查询
T ans = 0;
for (int i = x; i; i -= i & -i) {
for (int j = y; j; j -= j & -j) {
ans += w[i][j];
}
}
return ans;
}
T ask(int x, int y, int X, int Y) { // 区块查询：二维前缀和
x--, y--;
return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);
}
};
//操作全支持，时间复杂度*4
template<typename T>
struct Fenwick2D {
int n, m;
vector<vector<T>> b1, b2, b3, b4;
Fenwick2D(int n, int m) : n(n), m(m) {
b1.resize(n + 1, vector<T>(m + 1));
b2.resize(n + 1, vector<T>(m + 1));
b3.resize(n + 1, vector<T>(m + 1));
b4.resize(n + 1, vector<T>(m + 1));
}
void add(auto &w, int x, int y, T k) { // 单点修改
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
w[i][j] += k;
}
}
}
void add(int x, int y, T k) { // 多了一步计算
add(b1, x, y, k);
add(b2, x, y, k * (x - 1));
add(b3, x, y, k * (y - 1));
add(b4, x, y, k * (x - 1) * (y - 1));
}
void add(int x, int y, int X, int Y, T k) { // 区块修改：二维差分
X++, Y++;
add(x, y, k), add(X, y, -k);
add(X, Y, k), add(x, Y, -k);
}
T ask(auto &w, int x, int y) { // 单点查询
T ans = 0;
for (int i = x; i; i -= i & -i) {
for (int j = y; j; j -= j & -j) {
ans += w[i][j];
}
}
return ans;
}
T ask(int x, int y) { // 多了一步计算
T ans = 0;
ans += x * y * ask(b1, x, y);
ans -= y * ask(b2, x, y);
ans -= x * ask(b3, x, y);
ans += ask(b4, x, y);
return ans;
}
T ask(int x, int y, int X, int Y) { // 区块查询：二维前缀和
x--, y--;
return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);
}
};
字符串
KMP
struct KMP{
vector<int> ne;
vector<int> pos;
string s,p;
KMP(string s,string p){
ne.resize(p.size()+1);
this->s=s,this->p=p;
getNext(p);
}
KMP(string p){
ne.resize(p.size()+1);
this->p=p;
getNext(p);
}
inline void getNext(string p) {
int i=0,j;
ne[0]=j=-1;
while(i<p.size())
if(j==-1 || p[i]==p[j])
ne[++i]=++j;
else j=ne[j];
}
inline int work(){
int cnt=0;
int i=0,j=0;
while(i<s.size()) {
if(j==-1 || s[i]==p[j])
i++,j++;
else j=ne[j];
if(j==p.size()){
//剪断操作
// j=0;
//不剪断
pos.push_back(i-p.size());
j=ne[j];
cnt++;
}
}
return cnt;
}
inline int MLoop(){
return p.size()-ne[p.size()];
}
};
字母trie
constexpr int N = 1000010;
int son[N][26],idx,cnt[N];
void insert(string str){
int p=0;
for(int i=0;i<str.size();i++){
int u=str[i]-'a';
if(!son[p][u]){
son[p][u]=++idx;
}
p=son[p][u];
}
cnt[p]++;
}
int query(string str){
int p=0;
for(int i=0;i<str.size();i++){
int u=str[i]-'a';
if(!son[p][u]){
return 0;
}
p=son[p][u];
}
// cnt[p]++;
return cnt[p];
}
01trie
const int N = 100010;
int ch[31*N][2];
struct Trie {
int n, idx;
Trie(int n) {
this->n = n;
idx = 0;
}
void insert(int x) {
int u = 0;
for (int i = 30; ~i; i--) {
int &v = ch[u][x >> i & 1];
if (!v) v = ++idx;
u = v;
}
}
int query(int x) {
int u = 0, res = 0;
for (int i = 30; ~i; i--) {
int v = x >> i & 1;
if (ch[u][!v]) {
res += (1 << i);
u = ch[u][!v];
} else {
u = ch[u][v];
}
}
return res;
}
};
AC automaton
struct AhoCorasick {
static constexpr int ALPHABET = 26;
struct Node {
int len;
int link;
std::array<int, ALPHABET> next;
Node() : link{}, next{} {}
};
std::vector<Node> t;
AhoCorasick() {
init();
}
void init() {
t.assign(2, Node());
t[0].next.fill(1);
t[0].len = -1;
}
int newNode() {
t.emplace_back();
return t.size() - 1;
}
int add(const std::vector<int> &a) {
int p = 1;
for (auto x : a) {
if (t[p].next[x] == 0) {
t[p].next[x] = newNode();
t[t[p].next[x]].len = t[p].len + 1;
}
p = t[p].next[x];
}
return p;
}
int add(const std::string &a, char offset = 'a') {
std::vector<int> b(a.size());
for (int i = 0; i < a.size(); i++) {
b[i] = a[i] - offset;
}
return add(b);
}
void work() {
std::queue<int> q;
q.push(1);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < ALPHABET; i++) {
if (t[x].next[i] == 0) {
t[x].next[i] = t[t[x].link].next[i];
} else {
t[t[x].next[i]].link = t[t[x].link].next[i];
q.push(t[x].next[i]);
}
}
}
}
int next(int p, int x) {
return t[p].next[x];
}
int next(int p, char c, char offset = 'a') {
return next(p, c - 'a');
}
int link(int p) {
return t[p].link;
}
int len(int p) {
return t[p].len;
}
int size() {
return t.size();
}
};
Manacher
struct Manacher{
string s;
Manacher(string str):s(str){}
vector<int> work(){
int n = s.length();
string t = "-#";
for (int i = 0; i < n; i++) {
t += s[i];
t += '#';
}
int m = t.length();
t += '+';
int mid = 0, r = 0;
vector<int> p(m);
for (int i = 1; i < m; i++) {
p[i] = i < r ? min(p[2 * mid - i], r - i) : 1;
while (t[i - p[i]] == t[i + p[i]]) p[i]++;
if (i + p[i] > r) {
r = i + p[i];
mid = i;
}
}
return p;
}
int getMax(){
int maxn=-INF;
auto res=work();
for(auto &v:res){
maxn=max(maxn,v-1);
}
return maxn;
}
};
标签：常用,
return,
int,
res,
ll,
ACM,
vector,
const,
模板
From： https://www.cnblogs.com/KrowFeather/p/18005737