算法模板集合

[toc]

编译

shell

1	g++ name.cpp -Wall -Wextra --std=c++17 -o name; .\name.out

对拍

python

import os
from random import *


my = 'm.exe'
std = 'std.exe'



class DSU:
    def __init__(self,n=0) -> None:
        self.fa = [-1]*(n+1)

    def find(self, x: int)->int:
        if self.fa[x] == -1:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]
    def join(self, x, y):
        fax = self.find(x)
        fay = self.find(y)
        if fax == fay:
            return False 
        else:
            self.fa[fax] = y
            return True

def generateComplete(n):
    all_edges = []
    for i in range(1, n+1):
        for j in range(i+1,n+1):
            all_edges.append((i,j))
    return all_edges

def generateTree(n):
    all_edges = generateComplete(n)
    shuffle(all_edges)
    edges = []
    dsu = DSU(n)
    for (a,b) in all_edges:
        if dsu.join(a,b):
            edges.append((a,b))
    return edges
    
def generate_connected_Graph(n,m):
    all_edges = generateComplete(n)
    edges = []
    dsu = DSU(n)
    for (a,b) in all_edges:
        if len(edges) < n-1:
            if dsu.join(a,b):
                edges.append((a,b))
        elif len(edges) == m:
            break
        else:
            edges.append((a,b))
    return edges

def genTests(i):
    f = open('input.txt', 'w')
    N = randint(5,15)
    edges = generateTree(N)
    f.writelines(str(N))
    f.writelines('\n')
    for (a,b) in edges:
        f.writelines(str(a)+" " + str(b)+"\n")


def duipai():
    for i in range(1010, 1000000):
        genTests(i)
        os.system(std + ' < input.txt > std.out')
        os.system(my + ' < input.txt > my.out')
        if os.system('fc std.out my.out'):
            print("WA")
            exit()

duipai()
print('AC_all')

测时间

cpp

#include <chrono>
using namespace chrono;

auto start = system_clock::now();
    //Dij(mn); Code
auto finish = system_clock::now();
auto duration = duration_cast<microseconds>(finish - start);
auto cost = double(duration.count()) * microseconds::period::num / microseconds::period::den;

cout << "cost: " << cost << "s" << endl;

DEBUG

数组最大范围
long long 溢出
语句逻辑顺序，定义顺序
初始化
非法的转移 (从f[i-1]没判断边界)
特殊值，n=1，0
阅读题意
for变量正确

VSCODE 代码片段

json

{
	// Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
	// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
	// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
	// same ids are connected.
	// Example:
	"Print to console": {
		"prefix": "log",
		"body": [
			"console.log('$1');",
			"$2"
		],
		"description": "Log output to console"
	},

	"C++oimoretestcases": {
		"prefix": "tbits",
		"body": [
			"#include <bits/stdc++.h>",
			"using namespace std;",
			"#define _ <<\" \"<<",
			"#define sz(x) ((int) (x).size())",
			"typedef long long ll;",
			"typedef pair<int, int> pii;",
			"typedef vector<vector<int>> Graph;",
			"typedef vector<vector<pair<int,ll>>> Graphl;",
			"const int maxn = 5e5 + 5;",
			"\n",
			"int n, m, T;\n",
			"void run_case() {",
			"\t",
			"}\n",
			"int main() {",
			"\tios_base::sync_with_stdio(0);",
			"\tcin.tie(0);",
			"\tcin >> T;",
			"\twhile (T--) run_case();",
			"\treturn 0;",
			"}"
		],
		"description": "c++snippets more testcases"
	},

	"C++oistandard": {
		"prefix": "bits",
		"body": [
			"#include <bits/stdc++.h>",
			"using namespace std;",
			"#define _ <<\" \"<<",
			"#define sz(x) ((int) (x).size())",
			"typedef long long ll;",
			"typedef pair<int, int> pii;",
			"typedef vector<vector<int>> Graph;",
			"typedef vector<vector<pair<int,ll>>> Graphl;",
			"const int maxn = 5e5 + 5;",
			"\n",
			"int n, m;\n",
			"int main() {",
			"\tios_base::sync_with_stdio(0);",
			"\tcin.tie(0);",
			"\t$1",
			"\treturn 0;",
			"}"
		],
		"description": "c++snippts"
	},
	
	"filereadin": {
		"prefix": "fre",
		"body": [
			"freopen(\"d.txt\",\"r\",stdin);",
			"$1"
		],
		"description": "filereadin"
	},

	"deltearray": {
		"prefix": "delarr",
		"body": [
			"if (${1:name}) { delete [] ${1:name}; ${1:name} = NULL; }"
		],
		"description": "delte an array"
	},

	"forloopi": {
		"prefix": "fori",
		"body": [
			"for (int i = 1;i <= ${1:n}; ++i) {",
			"\t$2",
			"}"
		],
		"description": "fori"
	},

	"forloopj": {
		"prefix": "forj",
		"body": [
			"for (int j = 1;j <= ${1:m}; ++j) {",
			"\t$2",
			"}"
		]
	},

	"forloopk": {
		"prefix": "fork",
		"body": [
			"for (int k = 1;k <= ${1:m}; ++k) {",
			"\t$2",
			"}"
		]
	},
	"vector1": {
		"prefix": "vec1",
		"body": [
			"vector<int> ${1:A}(n+1);\n"
		]
	},
	"vector2": {
		"prefix": "vec2",
		"body": [
			"vector<vector<int>> ${1:G}(n+1, vector<int>($2));\n"
		]
	}
	,
	"vector3": {
		"prefix": "vec3",
		"body": [
			"vector<vector<vector<int>>> ${1:f}(n+1, vector<vector<int>>(m+1, vector<int>(${2:p+1}, ${3:oo})));\n"
		]
	},

	"print arr": {
		"prefix": "parr",
		"body": [
			"for (int i = 1;i <= ${1:n}; ++i) {\n\tcout << ${2:A[i]} << \" \";\n}cout << endl;"
		]
	}
}

计算几何

cpp

const double eps = 1e-13;
struct Point {
    double x, y;
    Point(double x=0, double y=0) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Vector a, double p) { return Vector(a.x*p, a.y*p); }
Vector operator / (Vector a, double p) { return Vector(a.x/p, a.y/p); }
bool operator < (const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x) {
    if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}
bool operator == (const Point& a, const Point& b) {
    return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}
double Dot(Vector a, Vector b) { return a.x*b.x + a.y*b.y; }
double Length(Vector a) { return sqrt(Dot(a, a)); }
double Angle(Vector a, Vector b) { return acos(Dot(a,b) / Length(a) / Length(b)); }
double Cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; }
double Area2(Point a, Point b, Point c) { return Cross(b-a, c-a); }
Vector Rotate(Vector a, double rad) { return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad)+a.y*cos(rad)); }
Vector Normal(Vector a) { double L = Length(a); return Vector(-a.y/L, a.x/L); }

vector<Point> convexhull(vector<Point> &P) {
    vector<Point> h;
    sort(P.begin(), P.end()); P.erase(unique(P.begin(), P.end()), P.end());
    for (int i = 0;i < sz(P); ++i) {
        while (sz(h) > 1 && Cross(h.back()-h[sz(h)-2],P[i]-h[sz(h)-2]) +eps < 0) h.pop_back();
        h.push_back(P[i]);
    }
    int k = sz(h);
    for (int i = sz(P)-2;i >= 0; --i) {
        while (sz(h) > k && Cross(h.back()-h[sz(h)-2],P[i]-h[sz(h)-2]) +eps < 0) h.pop_back();
        h.push_back(P[i]);
    }
    if (!h.empty()) h.pop_back();
    return h;
}

Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {
    return p + v*(Cross(w, p-q) / Cross(v, w));
}

double DistanceToLine(Point p, Point a, Point b) {
    Vector v1 = b-a, v2 = p-a;
    return fabs(Cross(v1, v2)) / Length(v1); // 不取绝对值是有向距离
}

double DistanceToSegment(Point p, Point a, Point b) {
    if (a == b) return Length(p-a);
    Vector v1 = b-a, v2 = p-a, v3 = p-b;
    if (dcmp(Dot(v1, v2)) < 0) return Length(v2);
    else if (dcmp(Dot(v1, v3)) > 0) return Length(v3);
    else return fabs(Cross(v1,v2)) / Length(v1);
}

Point GetLineProjection(Point p, Point a, Point b) {
    Vector v = b-a;
    return a+v*(Dot(v, p-a) / Dot(v, v));
}

bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) { // 不包括端点,重合
    double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1),
           c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
    return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}

bool OnSegment(Point p, Point a1, Point a2) { // 不包括端点
    return dcmp(Cross(a1-p, a2-p)) == 0 && dcmp(Dot(a1-p, a2-p)) < 0;
}

 
double PolygonArea(vector<Point> &P) { // following untest
    double area = 0;
    for (int i = 1;i < sz(P); ++i) {
        area += Cross(P[i]-P[0], P[(i+1)%sz(P)]-P[0]);
    }
    return abs(area/2); // directed without abs
}
 
int isPointInPolygon(Point p, vector<Point> &P) {
    int wn = 0;
    int n = sz(P);
    for (int i = 0;i < n; ++i) {
        if (OnSegment(p, P[i], P[(i+1)%n])) return -1; // on border
        int k = dcmp(Cross(P[(i+1)%n]-P[i], p-P[i]));
        int d1 = dcmp(P[i].y-p.y);
        int d2 = dcmp(P[(i+1)%n].y-p.y);
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    if (wn != 0) return 1; // inside
    return 0; // outside
}
 
// ball
double torad(double deg) {
    return deg/180 * acos(-1); 
}
 
// change latitude,langtitude(degree) to (x,y,z) 
void get_coord(double R, double lat, double lng, double &x, double &y, double &z) {
    lat = torad(lat);
    lng = torad(lng);
    x = R*cos(lat)*cos(lng);
    y = R*cos(lat)*sin(lng);
    z = R*sin(lat);
}

圆

cpp

struct Circle {
    Point c; double r;
    Circle(Point c, double r) : c(c), r(r) {}
    Point point(double a) {
        return Point(c.x + cos(a)*r, c.y + sin(a)*r);
    }
};

struct Line {
    Point p; Vector v;
    Line(Point p, Vector v) : p(p), v(v) {}
    Point point(double a) {
        return Point(p.x + a*v.x, p.y + a*v.y);
    } 
};

int getLineCircleIntersection(Line L, Circle C, double& t1, double& t2, vector<Point>& sol) {
    double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
    double e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
    double delta = f*f - 4*e*g;
    if (dcmp(delta) < 0) return 0; // 相离
    if (dcmp(delta) == 0) {
        t1 = t2 = -f / (2*e); sol.push_back(L.point(t1));
        return 1; // 相切
    } 
    t1 = (-f - sqrt(delta)) / (2*e); sol.push_back(L.point(t1));
    t2 = (-f + sqrt(delta)) / (2*e); sol.push_back(L.point(t2));
    return 2; // 相交
}

double angle(Vector v) { return atan2(v.y, v.x); }

int getCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol) {
    double d = Length(C1.c - C2.c);
    if (dcmp(d) == 0) {
        if (dcmp(C1.r - C2.r) == 0) return -1; // 重合
        return 0;
    }
    if (dcmp(C1.r + C2.r - d) < 0) return 0;
    if (dcmp(fabs(C1.r-C2.r) - d) > 0) return 0;
    double a = angle(C2.c - C1.c);
    double da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (2*C1.r*d));
    Point p1 = C1.point(a - da), p2 = C1.point(a + da);
    sol.push_back(p1);
    if (p1 == p2) return 1;
    sol.push_back(p2);
    return 2; 
}


int getTangents(Point p, Circle C, vector<Vector>& v) {
    Vector u = C.c - p;
    double dist = Length(u);
    if (dist < C.r) return 0;
    else if (dcmp(dist - C.r) == 0 ) {
        v.push_back(Rotate(u, PI/2));
        return 1;
    } else {
        double ang = asin(C.r / dist);
        v.push_back(Rotate(u, -ang));
        v.push_back(Rotate(u, +ang));
        return 2;
    }
}
Point midpoint(Point a, Point b) { return Point((a.x+b.x)/2, (a.y+b.y)/2); }

排序极角

cpp

ll Cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; }
int n, m, T;
vector<Point> P;
bool up(Point a){
    return a.y > 0 || (a.y == 0 && a.x >= 0);
}
sort(P.begin(), P.end(), [&](auto a,auto b) {
    if (up(a) != up(b)) return up(a) > up(b);
        return Cross(a, b) > 0;
});

读入优化

编译优化

cpp

1 2	#pragma GCC optimize("O3", "unroll-loops") #pragma GCC target("avx2")

cin优化

cpp

1	ios_base::sync_with_stdio(0); cin.tie(0);

快读快写

cpp

inline int read() {
    int x = 0; char ch = 0, w = 0;
    while(!isdigit(ch)) {w |= ch == '-'; ch=getchar();}
    while(isdigit(ch)) x = (x<<3) + (x<<1) + (ch^48), ch=getchar();
    return w ? -x : x;
}
inline void write(int x) { // long long 请勿使用
    if(x < 0) { putchar('-'); x=-x; }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
#define nl putchar('\n')

多个测试数据

以EOF结尾

cpp

1
2
3

while (cin >> n) {
    
}

以0结尾

cpp

1
2
3

while ((cin >> n) && n) {
    
}

给定数据组数

cpp

int T; cin >> T;
while(T--) {

}

STL

struct

cpp

struct Node {
    int val, x, y;
    Node(int val, int x, int y) : val(val), x(x), y(y) {} // init values
    bool operator<(const Node& other) const { // define <
        if (val == other.val) return x < other.x;
        return val < other.val;
    }
} na, nb;  // == Node na,nb;
vector<Node> A;
A.push_back({3, 4, 5}); // fast init

#define pii pair<int, int>  
pii a = {1, 3};
auto [x, y] = a;

sort

cpp

sort(A+1, A+n+1);  // sort for array in [1,n] from small to big
sort(A.begin()+1, A.end()); // for vector
sort(A.begin(), A.end(), greater<>()); // from big to small

bool cmp(int a, int b) { return a > b; } 
sort(A.begin(), A.end(), cmp); // use cmp

sort(A.begin(), A.end()); // for struct if < is defined

vector

cpp

vector<int> A(n+1); // set a vector of index [0,n], init with 0
vector<int> A(n+1, INT_MAX); // set a vector of index [0, n], init with 2e31 - 1
vector<vector<int>> G(n+1); // set a 2d vector
vector<vector<int>> M(n+1, vector<int>(m+1, 1)); // n*m array
A.push_back(i); // insert i to the back
A.pop_back(i); // remove the last element
A.assign(n, 1); // resize the vector to [0, n), init with 1
A.back(); // get the last element
int pos = lower_bound(A.begin(), A.end(), 3) - A.begin(); // get index of the position: A[i] >= 3
int pos = upper_bound(A.begin()+1, A.end(), 4) - A.begin(); // search for [1, end) get positon: A[i] > 3 

vector<int> B;
vector<pii> A; 
for (int i = 0;i <= sz(B); ++i) { // remove multiples
    if (A.empty() || A[A.size()-1].first != x) A.push_back({B[i], 1});
    else A[A.size()-1].second++;
}
count(a.begin(), a.end(), a[0]) == n // 判断是否都相等

map

cpp

map<pair<int,int>, int> M; // O(logn)
unordered_map<string, int> hash_map; // O(1)
M[{1, 3}] = 4; // set key and value 
for (auto [key, val] : M) {
    // iterate over the map
}

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
unordered_map<int, int, custom_hash> safe_map;

set

cpp

set<int> s;
set<int, greater<>> s; // form big to small
multiset<int> ms; // support for multiple values
*s.begin() // first elem
*s.rbegin() // last elem
*(--s.end()) // last elem
s.erase(v); // erase all v
s.erase(s.find(v)); // erase one of v
auto iter = s.upper_bound(v);
if (iter != end()) {
    cout << (*++iter); // successor
    cout << (next(iter));
}
auto iter = s.lower_bound(v);
if (iter != s.begin()) {
    cout << (*(--iter)); // predecessor
    cout << (*prev(iter));
}
if (s.find(v) != s.end()) {
    cout << *(s.find(v)); // successful find 
}
for (auto v : s) {
    cout << v; // output in sorted order
}

bitset

cpp

bitset<maxn> s;
s[1];
cout << s << endl;
s.set(3);
s[1] & s[2];
s.count(); 
s.any(); // 是否有1
s.none(); // whether none set bit

pbds

cpp

#include <bits/extc++.h>
using namespace __gnu_pbds;

tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;
pii //type to store
null_type //no map
less<pii> //form small to big
rb_tree_tag //red black tree
tree_order_statistics_node_update // update method
tr.insert({x,y}); // insert
tr.erase({x,y}); // erase
tr.order_of_key({x,y}); // get rank
tr.find_by_order(x); // kth smallest value
tr.join(b); // merge b to r
tr.split(v,b); // split for tr: <= v b: > v 
tr.lower_bound(x); 
tr.upper_bound(x); 

// support for multiple value
tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> bbt;
int sz;
#define ins(k) (bbt.insert((k<<20)+(++sz)))
#define del(k) (bbt.erase(bbt.lower_bound(k<<20)))
#define rk(k) (bbt.order_of_key(k<<20)+1)
#define kth(k) ((*bbt.find_by_order(k-1))>>20)
#define lower(k) ((*--bbt.lower_bound(k<<20))>>20)
#define upper(k) ((*bbt.upper_bound((k<<20)+n))>>20)

// hash table
gp_hash_table<int,bool> h;

模拟

初始化

cpp

memset(A, 0, sizeof(A)); // 初始化成0
memset(A, 127, sizeof(A)); // 初始化成最大值 2139062143, ll: 9187201950435737471
memset(A, 128, sizeof(A)); // 初始化成最小值 -2139062144
memset(A, -1, sizeof(A)); // 初始化成-1
memset(A, 0x3f, sizeof(A)); // 初始化成 1061109567, ll: 4557430888798830399

蛇形矩阵遍历

cpp

for (int i = 1;i <= n; ++i) {
    for (int ind = 1;ind <= m; ++ind) {
        int j = i % 2 == 0 ? m-ind+1 : ind;  // A[i][j]
    }

二分

$[L, M - 1], [M, R]$

cpp

L = 1; R = n-1;
while (L < R) {
    M = (L + R)/2 + 1;
    if (check()) L = M;
    else R = M-1;
}

离散化去重

cpp

sort(B+1, B+n+1); // 所有数据堆在B里
int nm = unique(B+1, B+n+1) - B-1; // 去重
for (int i = 1;i <= n; ++i) 
    int pos = lower_bound(B+1, B+nm+1, A[i].second) - B; // 原数组对应的值
sort(B.begin(), B.end());
int nm = unique(B.begin(), B.end()) - B.begin(); 
while (sz(B) != nm) B.pop_back();

离散化

cpp

typedef int Tl; 
vector<int> discretize(vector<Tl> A,int l,int r) {
    vector<Tl> B;
    for (int i = l; i <= r; ++i) {
        B.push_back(A[i]);
    }
    vector<int> ret(sz(A));
    sort(B.begin(), B.end()); // 所有数据堆在B里
    int nm = unique(B.begin(), B.end()) - B.begin(); // 去重
    for (int i = l;i <= r; ++i) 
        ret[i] = lower_bound(B.begin(), B.begin()+nm, A[i]) - B.begin() + 1;
    return ret;
}

去重（堆在一起）

cpp

1
2
3

sort(A.begin(), A.end());
if (A.empty() || A[A.size()-1].first != x) A.push_back({x, 1});
else A[A.size()-1].second++;

字符串转换

cpp

string tostr(ll x) {
    if (x == 0) return "0";
    string ret = "";
    while (x) {
        ret += '0' + (x % 10);
        x /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

ll toint(string x) {
    ll ret = 0;
    for (int i = 0;i < sz(x); ++i) {
        ret = ret*10 + x[i] - '0';
    }
    return ret;
}

离散前缀和

cpp

vector<pair<int,ll>> A, B;
map<int,ll> sum;
// insert values in A
sort(A.begin(), A.end());
for (auto [a, b] : A) {
    if (B.empty() || B.back().first != a) B.push_back({a, b});
    else B.back().second += b;
}
int last = INT_MIN;
ll a = 0, d = 0;
for (auto [xi, ai] : B) {
    a += d*(xi - last) + ai; // 2d
    d += ai; // 1d
    last = xi;
    sum[xi] = a;
}

数学

向上/向下取整

cpp

ll up(ll a, ll b) {
    if (a % b == 0) return a/b;
    if ((a^b) < 0) return a/b;
    else return a/b+1;
}

ll down(ll a, ll b) {
    if (a % b == 0) return a/b;
    if ((a^b) < 0) return a/b-1;
    else return a/b;
}

随机数

cpp

template <class T>
T randint(T l, T r = 0) {
    static mt19937 eng(chrono::steady_clock::now().time_since_epoch().count());
    if (l > r)
        swap(l, r);
    uniform_int_distribution<T> dis(l, r);
    return dis(eng);
}

取模结构体

cpp

const int MOD = 1e9 + 7;
// assume -MOD <= x < 2MOD
int getabs(int x) {
    if (x < 0) x += MOD;
    if (x >= MOD) x -= MOD;
    return x;
}
template<class T>
T fpow(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

struct Z {
    int x;
    Z(int x = 0) : x(getabs(x)) {}
    Z(ll x) : x(getabs(x % MOD)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(getabs(MOD - x));
    }
    Z inv() const {
        assert(x != 0);
        return fpow(*this, MOD - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = ll(x) * rhs.x % MOD;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = getabs(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = getabs(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

const int maxinv = 5e5 + 5;
Z inv[maxinv], fac[maxinv], invfac[maxinv];

void init() {
    inv[1] = 1;
    for(int i = 2; i < maxinv; ++ i) {
        inv[i] = Z(MOD-MOD/i) * inv[MOD%i];
    }
    fac[0] = invfac[0] = 1;
    for (int i = 1;i < maxinv; ++i) {
        fac[i] = fac[i-1]*i;
        invfac[i] = invfac[i-1]*inv[i];
    }
}

Z c(int n, int k) {
    return (k < 0 || k > n) ? 0 : fac[n] * invfac[n-k] * invfac[k];
}

取模

cpp

inline ll add(ll a, ll b) { // 带减法
    return ((a + b) % MOD + MOD) % MOD;
}
inline ll mul(ll a, ll b) {
    return (a * b) % MOD;
}

快速幂/龟速乘

cpp

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int MOD = 998244353;

inline ll add(ll a, ll b) { // 带减法
    return ((a + b) % MOD + MOD) % MOD;
}
ll mul(ll a, ll b) {
    return (a * b) % MOD;
}

ll fmul(ll a, ll b, ll& Mod)  {
	ll rt (0) ;
	for (; b; b >>= 1, ( a <<= 1 ) %= Mod)
		if (b & 1) {
			(rt += a) %= Mod ;
		}
	return rt;
}

ll fpow(ll a, ll n) {
    a %= MOD; ll ret = 1;
    for (; n; n >>= 1, a = mul(a, a))
    	if (n & 1) ret = mul(ret, a);
    return ret;
}


int main() {
	cout << fpow(2,10) << endl;
	return 0;
}

特殊余数

cpp

ll mul(ll a, ll b, ll mod = MOD) {
    return (a * b) % mod;
}

ll fpow(ll a, ll n, ll mod) {
    if (a % mod == 0) return 0;
    a %= mod; ll ret = 1;
    for (; n; n >>= 1, a = mul(a, a, mod))
    	if (n & 1) ret = mul(ret, a, mod);
    return ret;
}

费尔马小定理求逆元

cpp

ll fpow(ll a, ll n) {
    a %= MOD;
    ll ret = 1;
    for (; n; n >>= 1, a = mul(a, a) )
    	if (n & 1) ret = mul(ret, a);
    return ret;
}

ll inv(ll a) {
    return fpow(a, MOD-2);
}

O(n)求n个逆元

cpp

inv[1] = 1;
for(int i = 2; i <= n; ++ i) {
    inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
}

阶乘与阶乘的逆元

cpp

// 逆元数组大小开够
inv[1] = 1;
for(int i = 2; i <= n; ++ i) {
    inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
}
f[0] = rf[0] = 1;
for (int i = 1;i <= n; ++i) {
    f[i] = mul(f[i-1], i);
    rf[i] = mul(rf[i-1], inv[i]);
}

求组合数

cpp

// 需要逆元数组，费马尔小定理求逆元
inline ll mul(ll a, ll b) {
    return (a * b) % MOD;
}
ll c(int n, int k) {
    return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));
}
int main() {
    // 预处理
    inv[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
    f[0] = rf[0] = 1;
    for (int i = 1;i <= n; ++i) {
        f[i] = mul(f[i-1], i);
        rf[i] = mul(rf[i-1], inv[i]);
    }
}

求大组合数 $O (K)$

cpp

ll c(int n, int k) {
    if (k < 0 || k > n) return 0;
    ll ret = 1;
    for (int i = n;i >= n-k+1; --i) {
        ret = mul(ret, i);
    }
    ret = mul(ret, rf[k]);
    return ret;
}

周期计数

求 $[0, R]$ 区间里从 $x$ 开始周期为 $t$ 的数的个数

cpp

1
2
3

ll numofperiod(ll R, ll x, ll t) {
    return (R+t-x)/t ; 
}

扩展欧几里得exgcd

解决 $a x + b y = g c d (a, b)$ 定义好d,x,y 最后 d 是gcd , x,y 是解

cpp

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

同余方程

解决 $a x + b y = c$ 的最小正整数解，若无解返回 false

cpp

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

ll up(ll a, ll b) {
    if (a % b == 0) return a/b;
    if ((a^b) < 0) return a/b;
    else return a/b+1;
}

ll down(ll a, ll b) {
    if (a % b == 0) return a/b;
    if ((a^b) < 0) return a/b-1;
    else return a/b;
}

bool equiv(ll a, ll b, ll c, ll& x, ll& y) {
    // x 是最小正整数解
    ll d;
    exgcd(a, b, d, x, y);
    if (c % d != 0) return false;
    x *= c/d; y *= c/d;
    ll k;
    ll m = b/d;
    if (m < 0) k = up(-x,m)-1;
    else k = down(-x,m)+1;
    x += k*(b/d);
    y -= k*(a/d);
    return true;
}

非负情况

cpp

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

ll dx, dy; // x, y 的步长

bool equiv(ll a, ll b, ll c, ll& x, ll& y) {
    // x, y 都是非负解
    ll d;
    exgcd(a, b, d, x, y);
    if (c % d != 0) return false;
    x *= c/d; y *= c/d;

    ll k;
    dx = max(-b/d,b/d);
    dy = max(-a/d,a/d);

    x = ((x % dx) + dx) % dx;
    y = (c-a*x)/b;

    if (y < 0) {
        y = ((y % dy) + dy) % dy;
        x = (c-b*y)/a;
    }
    if ((a ^ b) >= 0) dy = -dy;
    return true;
}

欧拉函数 $\sqrt{(} n)$

cpp

int phi(int n){   
     int res=n,a=n;  
     for(int i=2;i*i<=a;i++){  
         if(a%i==0){  
             res=res/i*(i-1);  
             while(a%i==0) a/=i;  
         }  
     }  
     if(a>1) res=res/a*(a-1);  
     return res;  
}

E氏筛法

cpp

1 2	for (int i = 2;i < maxn; ++i) if (!cnt[i]) for (int j = i;j < maxn; j += i) cnt[j]++;

线性筛/分解质因数

cpp

struct Prime {
    int n;
    vector<int> prime, nxt, mu;
    vector<bool> isp;
    
    Prime(int n) : n(n), prime(1), nxt(n+1), mu(n+1), isp(n+1,1) { calc(); }

    void calc() {
        isp[1] = 0; mu[1] = 1;
        for (int i = 2;i <= n; ++i) {
            if (isp[i]) prime.push_back(i), nxt[i] = i, mu[i] = -1;
            for (int j = 1;j < sz(prime) && i*prime[j] <= n; ++j) {
                isp[i*prime[j]] = 0;
                nxt[i*prime[j]] = prime[j];
                if (i % prime[j] == 0) {
                    mu[prime[j] * i] = 0;
                    break;
                } else mu[prime[j]*i] = mu[prime[j]] * mu[i];
            }
        }
        for (int i = 1;i <= n; ++i) mu[i] += mu[i-1];
    }
    
    vector<pair<int,int>> factorize(int x) { 
        vector<pair<int,int>> ret;
        while (x != 1) {
            int p = nxt[x];
            if (ret.empty() || ret.back().first != p) ret.push_back({p, 1});
            else ret.back().second++;
            x /= p;
        }
        return ret;
    }
};

低常数

cpp

struct Prime {
    const int n = 2e7 + 5;
    vector<int> primes;
    vector<bool> np; // not prime
    
    Prime() : np(n+1) { calc(); }

    void calc() {
        np[1] = 1; 
        for (int i = 2;i <= n; ++i) {
            if (!np[i]) primes.push_back(i);
            for (auto p : primes) {
                if (p * i > n) break;
                np[p * i] = 1;
                if (i % p == 0) break;
            }
        }
    }
};

所有因子

cpp

vector<int> factors(int x) {
    vector<int> ret;
    for (int i = 1;i*i <= x; ++i) if (x % i == 0) {
        ret.push_back(i);
        if (i != x/i) ret.push_back(x/i);
    }
    return ret;
}

单个质因数分解 $O (\sqrt{x})$

cpp

vector<pair<ll,int>> factorize(ll x) {
    vector<pair<ll,int>> ret;
    for (int i = 2; (ll)i*i <= x; ++i) if (x % i == 0) {
        ret.push_back({i, 0});
        while (x % i == 0) x /= i, ret.back().second++;
    }
    if (x > 1) ret.push_back({x, 1});
    return ret;
}

数论分块

cpp

for (ll l = 1, r = 0; l <= n; l = r+1) {
    r = n/(n/l);
    ans = add(ans, mul(add(sum(r),MOD-sum(l-1)), n/l%MOD));
}

素数测试Miller-Rabin

cpp

ll fpow(ll a, ll n, ll p) {
    ll ans = 1;
    while (n) {
        if (n & 1)
            ans = (__int128)ans * a % p; 
        a = (__int128)a * a % p;
        n >>= 1;
    }
    return ans;
}


bool is_prime(ll x) {
    if (x < 3) 
        return x == 2;
    if (x % 2 == 0) 
        return false;
    ll A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0;
    while (d % 2 == 0)  d /= 2, ++r;
  
    for (auto a : A) {
        ll v = fpow(a, d, x); // a^d
        if (v <= 1 || v == x - 1) 
            continue;
        for (int i = 0; i < r; ++i) {
            v = (__int128)v * v % x; 
            if (v == x - 1 && i != r - 1) {
                v = 1;
                break;
            }
            if (v == 1)  
                return false;
        }
        if (v != 1) 
            return false;
    }
    return true;
}

Pollard Rho找一个因子, 分解质因数

需要 Miller-Rabin

cpp

template <class T>
T randint(T l, T r = 0) {
    static mt19937 eng(time(0));
    if (l > r)
        swap(l, r);
    uniform_int_distribution<T> dis(l, r);
    return dis(eng);
}

ll Pollard_Rho(ll N) {
    if (N == 4)
        return 2;
    if (is_prime(N))
        return N;
    while (1) {
        ll c = randint(1ll, N - 1);
        auto f = [=](ll x) { return ((__int128)x * x + c) % N; };
        ll t = 0, r = 0, p = 1, q;
        do {
            for (int i = 0; i < 128; ++i) {
                t = f(t), r = f(f(r));
                if (t == r || (q = (__int128)p * abs(t - r) % N) == 0)
                    break;
                p = q;
            }
            ll d = gcd(p, N);
            if (d > 1)
                return d;
        } while (t != r);
    }
}


set<ll> prim_factors(ll n) {
    if (is_prime(n)) {
        return {n};
    }
    if (n <= 1) return {}; // n != 0
    
    ll p = Pollard_Rho(n);
    while (n % p == 0) n /= p;

    auto v1 = prim_factors(p);
    auto v2 = prim_factors(n);
    for (auto x : v2) v1.insert(x);

    return v1;
}

vector<pair<ll,int>> factorize(ll n) {
    auto v = prim_factors(n);
    vector<pair<ll,int>> ret;
    for (auto p : v) {
        ret.push_back({p, 0});
        while (n % p == 0) { 
            n /= p;
            ret.back().second++;
        }
    }
    return ret;
}

扩展中国剩余定理EXCRT

cpp

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

bool equiv(ll a, ll b, ll c, ll& x, ll& y) {
    // x 是最小正整数解
    ll d;
    exgcd(a, b, d, x, y);
    if (c % d != 0) return false;
    x *= c/d;
    ll k = b/d;
    x = (x % k + k) % k;
    y = (c - a*x)/b;
    return true;
}
struct Excrt {
    // x === ai mod ni
    ll a = 0, n = 0; // answer in a
    Excrt() {}
    bool add(ll ta, ll tn) {
        if (n == 0) {
            a = ta; n = tn;
        } else {
            ll g = __gcd(n, tn);
            ll x, y;
            if (!equiv(n, tn, (ta-a%tn+tn)%tn, x, y)) return false; // no solution
            a += n*x;
            n = n/g*tn;
            a = (a % n + n) % n;
        }
        return true;
    }
};

快速傅里叶变换FFT

cpp

typedef double ld;
const ld PI = acos((ld)-1);

struct cp {
    ld x, y;
    cp(ld x=0, ld y=0) : x(x),y(y) {}
    cp operator + (const cp &c) const {
        return cp(x+c.x, y+c.y);
    }  
    cp operator - (const cp &c) const {
        return cp(x-c.x, y-c.y);
    }
    cp operator * (const cp &c) const {
        return cp(x*c.x - y*c.y, x*c.y + y*c.x);
    }
    cp conj() const {
        return cp(x, -y);
    }
};


void fft(vector<cp> &a, int len, int op) {
    while (sz(a) < len) a.push_back(cp(0,0));
    vector<int> R(len);
    R[0] = 0;
    for (int i = 1;i < len; ++i) {
        R[i] = (R[i>>1]>>1) + (i&1)*(len>>1);
        if (i < R[i]) swap(a[i], a[R[i]]);
    }
    vector<cp> w(len/2); w[0] = cp(1,0);
    for (int n = 2; n <= len; n <<= 1) {
        cp wt = cp(cos(2*PI*op/n), sin(2*PI*op/n));
        for (int k = 1;k < n/2; ++k) {
            if (k % 2) w[k] = w[k>>1] * w[k>>1] * wt;
            else w[k] = w[k>>1] * w[k>>1];
        }
        for (int i = 0; i < len; i += n) {
            int po = i + (n>>1);
            for (int k = 0; k < n/2; ++k) {
                auto t = a[i+k];
                a[i + k] = t + w[k] * a[po + k];
                a[po + k] = t - w[k] * a[po + k]; 
            }
        }
    }
    if (!~op) 
        for (int i = 0;i < len; ++i) a[i].x /= len;
}

vector<cp> convolution(vector<cp>& a, vector<cp>& b) {
    int len = 1;
    int lans = sz(a) + sz(b) - 1;
    while (len < lans) len <<= 1;
    fft(a, len, 1);
    fft(b, len, 1);
    vector<cp> ret(lans);
    for (int i = 0;i < len; ++i) a[i] = a[i] * b[i];
    fft(a, len, -1);
    for (int i = 0;i < lans; ++i) ret[i] = a[i];
    return ret;
}

快速数论变换NTT

cpp

const ll MOD = 4179340454199820289;
const ll G = 3, Gi = 1393113484733273430;
// const ll MOD = 998244353;
// const ll G = 3, Gi = 332748118;
ll mul(ll a, ll b) {
    return ((__int128)a * b) % MOD;
}

ll fpow(ll a, ll n) {
    a %= MOD; ll ret = 1;
    for (; n; n >>= 1, a = mul(a, a) )
    	if (n & 1) ret = mul(ret, a);
    return ret;
}

void ntt(vector<ll> &a, int len, int op) {
    while (sz(a) < len) a.push_back(0);
    vector<int> R(len);
    R[0] = 0;
    for (int i = 1;i < len; ++i) {
        R[i] = (R[i>>1]>>1) + (i&1)*(len>>1);
        if (i < R[i]) swap(a[i], a[R[i]]);
    }
    for(int mid = 1; mid < len; mid <<= 1) {	
		ll Wn = fpow( op == 1 ? G : Gi , (MOD - 1) / (mid << 1));
		for(int j = 0; j < len; j += (mid << 1)) {
			ll w = 1;
			for(int k = 0; k < mid; k++, w = mul(w, Wn)) {
                ll x = a[j + k], y = mul(w, a[j + k + mid]);
                a[j + k] = (x + y) % MOD,
                a[j + k + mid] = (x - y + MOD) % MOD;
			}
		}
	}
    ll iv = fpow(len, MOD - 2);
    if (op == -1) for(int i = 0; i < len; i++) a[i] = mul(a[i], iv);
}

vector<ll> convolution(vector<ll>& a, vector<ll>& b) {
    int len = 1;
    int lans = sz(a) + sz(b) - 1;
    while (len < lans) len <<= 1;
    ntt(a, len, 1);
    ntt(b, len, 1);
    vector<ll> ret(lans);
    for (int i = 0;i < len; ++i) a[i] = mul(a[i], b[i]);
    ntt(a, len, -1);
    for (int i = 0;i < lans; ++i) ret[i] = a[i];
    return ret;
}

线性代数

矩阵快速幂

cpp

const ll MOD = 1e9 + 7;


struct Mat {
    int n, m;
    vector<vector<ll>> A;
    Mat(int n, int m, ll v=0) : n(n), m(m), A(n, vector<ll>(m, v)) {}
    Mat(int n=0) : n(n), m(n), A(n, vector<ll>(n)) {
        for (int i = 0;i < n; ++i) A[i][i] = 1;
    } 
    vector<ll>& operator[](const int k) {
        return A[k];
    }
    Mat T() {
        Mat ret(m, n);
        for (int i = 0;i < n; ++i) {
            for (int j = 0;j < m; ++j) {
                ret[j][i] = A[i][j];
            }
        }
        return ret;
    }
};

ostream& operator<<(ostream &os, Mat &x) {
    for (int i = 0;i < x.n; ++i) {
        for (int j = 0;j < x.m; ++j) {
            os << x.A[i][j] << " ";
        }
        if (i < x.n-1) os << endl;
    }
    return os;
}

istream& operator>>(istream &is, Mat &x) {
    for (int i = 0;i < x.n; ++i) 
        for (int j = 0;j < x.m; ++j) 
            is >> x.A[i][j];
    return is;
}


ll add(ll a, ll b) {
    if (b < 0) b = MOD + b%MOD;
    return (a + b) % MOD;
}

ll mul(ll a, ll b) {
    return (a * b) % MOD;
}

Mat Add(Mat& a, Mat& b) {
    Mat ret(a.n, b.m, 0);
    for (int i = 0;i < ret.n; ++i) 
        for (int j = 0;j < ret.m; ++j) 
                ret.A[i][j] = add(ret.A[i][j], add(a.A[i][j], b.A[i][j]));
    return ret;
}

Mat Mul(Mat& a, Mat& b) {
    Mat ret(a.n, b.m, 0);
    for (int i = 0;i < ret.n; ++i) 
        for (int j = 0;j < ret.m; ++j) 
            for (int k = 0;k < a.m; ++k) 
                ret.A[i][j] = add(ret.A[i][j], mul(a.A[i][k], b.A[k][j]));
    return ret;
}

Mat& Mul(Mat& a, ll v) {
    for (int i = 0;i < a.n; ++i) 
        for (int j = 0;j < a.m; ++j) 
            a.A[i][j] = mul(a.A[i][j], v);
    return a;
}

Mat& Add(Mat& a, ll v) {
    for (int i = 0;i < a.n; ++i) 
        for (int j = 0;j < a.m; ++j) 
            a.A[i][j] = add(a.A[i][j], v);
    return a;
}

Mat Mfpow(Mat a, ll n) {
    Mat ret = Mat(a.n);
    for (; n; n >>= 1, a = Mul(a, a) )
    	if (n & 1) ret = Mul(ret, a);
    return ret;
}

// 使用
cin >> n >> m;
Mat a(n, n);
cin >> a;
Mat r = Mfpow(a, m); 
cout << r << endl;

矩阵求逆(取模)

cpp

ll fpow(ll a, ll n) {
    a %= MOD;
    ll ret = 1;
    for (; n; n >>= 1, a = mul(a, a) )
    	if (n & 1) ret = mul(ret, a);
    return ret;
}

ll inv(ll x) {
    return fpow(x, MOD-2);
}

Mat Inv(Mat& a) { // 需要费尔马求逆元，求和支持减法
    if (a.n != a.m) return Mat(0); // 无效
    Mat B(a.n,a.n*2);
    for (int i = 0;i < a.n; ++i) {
        for (int j = 0;j < a.n; ++j) {
            B.A[i][j] = a.A[i][j];
        }
        B.A[i][i+a.n] = 1;
    }
    for (int k = 0;k < a.n; ++k) {
        int row = k;
        while (row < a.n && !B.A[row][k]) row++;
        if (row >= a.n) return Mat(0);
        swap(B.A[row], B.A[k]);
        ll iv = inv(B.A[k][k]);
        for (int j = 0;j < a.n*2; ++j) {
            B.A[k][j] = mul(B.A[k][j], iv);
        }
        for (int i = 0;i < a.n; ++i) if (k != i) {
            ll v = B.A[i][k];
            for (int j = 0;j < a.n*2; ++j) {
                B.A[i][j] = add(B.A[i][j], -mul(v,B.A[k][j]));
            }
        }
    }
    Mat ret(a.n,a.n);
    for (int i = 0;i < a.n; ++i) {
        for (int j = 0;j < a.n; ++j) {
            ret.A[i][j] = B.A[i][j+a.n];
        }
    }
    return ret;
}

线性基

cpp

for (int i = 1;i <= n; ++i) {
    ll x = A[i];
    for (int k = 50;k >= 0; --k) if (x>>k & 1) {
        if (!B[k]) B[k] = x;
        x ^= B[k];
    }
}

高斯消元（老）

cpp

namespace PG { // projective geometry

	struct Vector {
		int n;
		double data[maxn];
		
		Vector(int x=13) {
			n = x;
			for (int i = 1;i <= n; ++i) {
				data[i] = 0;
			}
		}
		
	};

	struct Matrix {
		int n, m;
		double data[maxn][maxn];
		Matrix(int x, int y) {
			n = x; m = y;
		}

		void multline(int line, double value) {
			for (int i = 1;i <= m; ++i) data[line][i] *= value;
		}

		void addwith(int line, int other) {
			for (int i = 1;i <= m; ++i) data[line][i] += data[other][i];
		}

		void appendline(Vector v) {
			for (int i = 1;i <= v.n; ++i) {
				data[n+1][i] = v.data[i];
			}
			n++;
		}

		void mul(double val) {
			for (int i = 1;i <= n; ++i) {
				for (int j = 1;j <= m; ++j) {
					data[i][j] *= val;
				}
			}
		}

		void add(Vector v) {
			int cnt = 1;
			for (int i = 1;i <= n; ++i) {
				for (int j = 1;j <= m; ++j) {
					data[i][j] = v.data[cnt++];
				}
			}
		}

		Matrix& operator = (const Matrix& other) {
			n = other.n; m = other.m;
			for (int i = 1;i <= n; ++i) {
				for (int j = 1;j <= m; ++j) {
					data[i][j] = other.data[i][j];
				}
			}
			return *this;
		}

		Vector gauss() {
			int vis[n+1], used[n+1];
			memset(vis,0,sizeof(vis)); memset(used,0,sizeof(used));

			for (int i = 1;i <= n; ++i) { // 选择主元
				int flag = 0;
				for (int j = 1;j <= n; ++j) { // 选择方程
					if (data[j][i] != 0 && !used[j]) {
						flag = 1;
						vis[i] = j;
						used[j] = 1;
						multline(j, 1.0/data[j][i]);
						for (int k = 1;k <= n; ++k) {
							if (used[k] || abs(data[k][i]) < ZERO) continue; // 不选择j
							multline(k, -1.0/data[k][i]);
							addwith(k, j); //消元i
						}
						break;
					}
				}
				if (!flag) return Vector(-1);
			}

			Vector ret(n);

			for (int i = n; i >= 1; --i) {
				int now = vis[i];
				double v = data[now][m];
				for (int j = 1;j <= n; ++j) {
					if (j == now) continue;
					data[j][m] -= data[j][i] * v;
					data[j][i] = 0;
				}
				ret.data[i] = v;
			}

			return ret;
		}

		void gauss_jordan() {
			for(int i = 1,r;i <= n; ++i){	
				r = i;
				for(int j=i+1;j<=n;++j) 
					if(abs(data[j][i]) > abs(data[r][i])) r = j;
				if(abs(data[r][i]) < ZERO) {
					n = -1; return; // no solution
				}
				if(i != r) swap(data[i],data[r]);
				
				for(int k = 1;k <= n; ++k){
					if(k == i || abs(data[k][i]) < ZERO) continue;
				
					multline(k, -data[i][i]/data[k][i]);
					addwith(k, i);
				
				} 
			}	
			for(int i = 1;i <= n; ++i) multline(i, 1.0/data[i][i]);
		}

		Matrix getI(int size) {
			Matrix ret(size, size);
			memset(ret.data,0,sizeof(ret.data));
			for (int i = 1;i <= size; ++i) ret.data[i][i] = 1;
			return ret;
		}

		void concat(Matrix other) {
			for (int i = 1;i <= other.n; ++i) {
				for (int j = 1;j <= other.m; ++j) {
					data[i][j+m] = other.data[i][j];
				}
			}
			m = m + other.m;
		}

		void spilt(int a, int b) { //分割位a-b列
			for (int i = 1;i <= n; ++i) {
				for (int j = 1;j <= b-a+1; ++j) {
					data[i][j] = data[i][a+j-1];
				}
			}
			m = b-a+1;
		}

		void print() {
			for (int i = 1;i <= n; ++i) {
				for (int j = 1;j <= m; ++j) {
					cout << data[i][j] << " ";
				}
				cout << endl;
			}
			cout << endl;
		}

		Matrix inverse() {
			Matrix now(n,m); now = *this;
			now.concat(getI(n));
			now.gauss_jordan();
			now.spilt(now.n+1,now.m);
			return now;
		}

		Matrix operator *(Matrix other) {
			Matrix ret(n, other.m);
			for (int i = 1;i <= n; ++i) {
				for (int j = 1;j <= other.m; ++j) {
					ret.data[i][j] = 0;
					for (int k = 1;k <= m; ++k) ret.data[i][j] += data[i][k]*other.data[k][j];
				}
			}
			return ret;
		}
	};
}

动态规划

最长不下降子序列 $O (n l o g n)$

cpp

int low[maxn];
int LIS(int *A, int n) { // 最长不下降子序列
    int ans = 0;
    fill(low+1, low+n+1, 1e9);
    for (int i = 1;i <= n; ++i) {
        if (ans == 0 || A[i] >= low[ans]) low[++ans] = A[i];
        else low[upper_bound(low+1, low+ans+1, A[i]) - low] = A[i];
    }
    return ans;
}

int LIS(int *A, int n) { // 最长严格上升子序列
    int ans = 0;
    fill(low+1, low+n+1, 1e9);
    for (int i = 1;i <= n; ++i) {
        if (ans == 0 || A[i] > low[ans]) low[++ans] = A[i];
        else low[lower_bound(low+1, low+ans+1, A[i]) - low] = A[i];
    }
    return ans;
}

int LDS(int *A, int n) { // 最长不下降子序列
    int ans = 0;
    fill(low+1, low+n+1, 1e9);
    for (int i = 1;i <= n; ++i) {
        if (ans == 0 || -A[i] >= low[ans]) low[++ans] = -A[i];
        else low[upper_bound(low+1, low+ans+1, -A[i]) - low] = -A[i];
    }
    return ans;
}

最长公共子序列 $O (n l o g n)$

cpp

int M[maxn], low[maxn];
int LIS(int *A, int n) {
    int ans = 0;
    fill(low+1, low+n+1, 1e9);
    for (int i = 1;i <= n; ++i) {
        if (ans == 0 || A[i] >= low[ans]) low[++ans] = A[i];
        else low[upper_bound(low+1, low+ans+1, A[i]) - low] = A[i];
    }
    return ans;
}

int LCS(int *A, int *B, int n) {
    fill(M, M+n+1, 1e9);
    for (int i = 1;i <= n; ++i) M[A[i]] = i;
    for (int i = 1;i <= n; ++i) B[i] = M[B[i]];
    return LIS(B, n);
}

DAG最长路

cpp

ll n, m, dp[maxn], book[maxn];
vector<pair<int, ll>> G[maxn];
ll dfs(int x, int t) {
    if (book[x]) return dp[x];
    if (x == t) return 0;
    dp[x] = -oo;
    for (auto v : G[x]) {
        dp[x] = max(dp[x], dfs(v.first, t) + v.second);
    }
    book[x] = 1;
    return dp[x];
}
ll DAG(vector<pair<int, ll>>* G, int s, int t) {
    fill(book+1, book+n+1, 0); 
    ll ret = dfs(s, t);
    return ret >= 0 ? ret : -1;
}
//    cout << DAG(G, 1, n) << endl;

树形dp

cpp

// 01状态dp：没有上司的舞会
void dfs(int x) {
    dp[x][0] = 0; dp[x][1] = r[x];
    for (auto v : G[x]) if (v != fa[x]) {
        dfs(v);
        dp[x][0] += max(dp[v][0],dp[v][1]);
        dp[x][1] += dp[v][0];
    }
}

树形背包（简单版）

cpp

void dfs(int x) {
    dp[x][1][1] = s[x]; // 第一个点是自己
    // x: x  前 i个儿子(自己是1)选 j 个   f[x][i][j] = max(f[x][i-1][j-k] + g[son][all][k]) // 这个节点选k个  f[1][1] = s[x] 
    for (int i = 2;i <= sz(G[x])+1; ++i) {
        int v = G[x][i-2];
        dfs(v);
        for (int j = 1;j <= m; ++j) {
            for (int k = 0;k < j; ++k) {
                dp[x][i][j] = max(dp[x][i][j], dp[x][i-1][j-k] + dp[v][sz(G[v]) + 1][k]);
            }
        }
    }
}

树形背包（ $O (n^{2})$ ）

cpp

#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 2e3 + 5;
const ll oo = 1e18;
inline int read() {
    int x = 0; char ch = 0, w = 0;
    while(!isdigit(ch)) {w |= ch == '-'; ch=getchar();}
    while(isdigit(ch)) x = (x<<3) + (x<<1) + (ch^48), ch=getchar();
    return w ? -x : x;
}
int n, m;
vector<int> G[maxn];
ll dp[maxn][maxn][2], cnt[maxn], val[maxn];

void dfs(int x) {
    dp[x][1][0] = 0;
    dp[x][0][1] = val[x];
    cnt[x] = 1;
    for (int i = 1;i <= sz(G[x]); ++i) {
        int v = G[x][i-1];
        dfs(v);
        vector<ll> ans0(cnt[x]+cnt[v]+1, oo),ans1(cnt[x]+cnt[v]+1, oo);
        for (int j = 0;j <= cnt[x]; ++j) {
            for (int k = 0;k <= cnt[v]; ++k) {
                ans0[j+k] = min(ans0[j+k], dp[x][j][0] + min(dp[v][k][0], dp[v][k][1]));
                ans1[j+k] = min(ans1[j+k], dp[x][j][1] + min(dp[v][k][0], dp[v][k][1] + val[v]));
            }
        }
        cnt[x] += cnt[v]; // important
        for (int j = 0;j <= cnt[x]; ++j)
            dp[x][j][0] = ans0[j], dp[x][j][1] = ans1[j];
    }
}

int T;

int main() {
    T = read();
    while (T--) {
        n = read();
        for (int i = 1;i <= n; ++i) {
            G[i].clear();
        }

        
        for (int i = 2, x;i <= n; ++i) {
            x = read();
            G[x].push_back(i);
        }
        for (int i = 1;i <= n; ++i) {
            val[i] = read();
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                dp[i][j][0]=dp[i][j][1]=oo;
            }
        }
        dfs(1);
        // cout << dp[4][0][1] << endl;
        // cout << dp[5][0][1] << endl;
        for (int i = 0;i <= n; ++i) {
           printf("%lld ", min(dp[1][i][1],dp[1][i][0]));
        }
        putchar('\n');
    }
    return 0;
}

树形背包（DFS序）

cpp

void dfs(int i) {
    cnt[i] = 1;
    for (auto v : G[i]) {
        dfs(v);
        cnt[i] += cnt[v];
    } 
    num[i] = ++tot;
  //  cout << i _ num[i] << endl;
    dp[num[i]][0] = dp[num[i] - cnt[i]][0];
    for (int j = 1;j <= m; ++j) {
        dp[num[i]][j] = max(dp[num[i]-1][j-1] + s[i], dp[num[i] - cnt[i]][j]);
    }
}

状态压缩位运算

cpp

int seti(int mask, int i) {
    return mask | (1<<(i-1));
}
int deli(int mask, int i) {
    return mask & (~(1<<(i-1)));
}
int hasi(int mask, int i) {
    return mask & (1<<(i-1));
}

int toint(string s) {
    int k = 1; int ret = 0;
    for (int i = (int)s.length()-1;i >= 0; --i) {
        ret += (s[i] - '0') * k;
        k *= 2;
    }
    return ret;
}

计算二进制中 $1$ 的个数

cpp

1	__builtin_popcount(x)

数位dp

cpp

int A[20];
int dp[11][91][91]; // sum <= 90 优化

int dfs(int pos, int sum, int r, int limit) {
    if (pos == 0) {
        if (sum % k == 0 && r == 0) return 1;
        else return 0; 
    }
    
    auto cur = dp[pos][sum][r];
    if (!limit && cur != -1) return cur; 
    cur = 0;

    int mxnum = limit ? A[pos] : 9;
    for (int i = 0;i <= mxnum; ++i) {
        cur += dfs(pos-1, sum + i, (r*10 + i) % k, limit && (i == A[pos]));
    }
    
    if (!limit) dp[pos][sum][r] = cur;
    return cur;
}

int solve(int num) { // A 数组倒着存，数字大用string
    int tot = 0;
    while (num) {
        A[++tot] = (num % 10);
        num /= 10;
    }
    memset(dp, -1, sizeof(dp)); // 初始化成0会炸
    return dfs(tot, 0, 0, 1);
}

双边界

cpp

ll tl = l;
int tota = 0;
while (tl) {
    A[++tota] = tl % 10;
    tl /= 10;
}
ll tr = r;
int totb = 0;
while (tr) {
    B[++totb] = tr % 10;
    tr /= 10;
}
int tot = max(tota, totb);

pair<ll,ll> dfs(int pos, int l1, int l2) {
    if (pos == 0 || (l1 == 0 && l2 == 0)) {
        // 边界
    }

    auto &cur = dp[pos][l1][l2];
    if (cur.first != -1) return dp[pos][l1][l2];
    cur = {-1,0};

    int down = l1 ? A[pos] : 0;
    int up = l2 ? B[pos] : 9;
    for (int i = down;i <= up; ++i) {
        // ...
    }

    return cur;
}

SOS DP

cpp

for(int i = 0; i<(1<<N); ++i)
	F[i] = A[i];
for(int i = 0;i < N; ++i) for(int mask = 0; mask < (1<<N); ++mask){
	if(mask & (1<<i))
		F[mask] += F[mask^(1<<i)];
}

Convexhull Trick

cpp

struct ConvexHullTrick {
    // find minimun,  k decreases
    // find maximum,  k increases
    typedef ll T;
    typedef pair<T,T> line;
    vector<long double> x;
    vector<line> q;
    
    long double intersect(line l1, line l2) {
        return (long double)(l2.second-l1.second)/(l1.first-l2.first);;
    }
    void addline(T k, T b) {
        while (!q.empty() && intersect(q.back(), {k,b}) <= x.back()) q.pop_back(), x.pop_back();
        x.push_back(q.empty()?-(1e18):intersect(q.back(), {k,b})), q.push_back({k,b});
    }
    T query(int pos) {
        int k = upper_bound(x.begin(), x.end(), pos) - x.begin()-1;
        return q[k].first * pos + q[k].second;
    }
};

Changeroot

cpp

struct Node {
    ll h, d, p;
};
 
vector<pair<int,ll>> G[maxn];
 
typedef Node T;
static T zero = {0, 0, 0};
 
T f[maxn], g[maxn];
 
// f(x) = ti(x, addt(fi(x,v1), fi(x,v2)...))
T calc(int x, T gx) {
    return {gx.h, gx.d, gx.p};
}
 
T addt(T a, int x, pair<int,ll> e) {
    auto [v, len] = e;
    return {max(a.h, f[v].h + len), 
      max(a.d, max(f[v].d, a.h + f[v].h + len)),
      max(a.p, a.h + f[v].h + len)};
}
 
struct dsqueue {
	struct operation { int x; pair<int,ll> v; };
	struct dat {
		vector<T> a = {zero};
		T query() { return a.back(); }
		void undo() { a.pop_back(); }
		void apply(operation o) { a.push_back(addt(a.back(), o.x, o.v)); }
	};
	dat ds;
	vector<pair<int, operation>> a;
	int cnt = 0;
	dsqueue() {}
	void pop() {
		if (!cnt) {
			cnt = (int)a.size();
			reverse(a.begin(), a.end());
			for (auto& [t, o]: a)
			ds.undo(), t = 0;
			for (auto& [t, o]: a)
			ds.apply(o);
		}
		deque<operation> b[2];
		for (int t : {1, 0}) {
			for (int i = 0; !t ? i < (cnt & -cnt) : a.back().first; i++) {
			b[t].push_front(a.back().second);
			a.pop_back();
			ds.undo();
			}
		}
		for (int t : {1, 0}) {
			for (auto& o: b[t]) {
			ds.apply(o);
			a.emplace_back(t, o);
			}
		}
		cnt--;
		ds.undo();
		a.pop_back();
	}
	void push(operation o) {
		a.emplace_back(1, o);
		ds.apply(o);
	}
};
 
void dfs1(int x, int fa) {
    g[x] = zero;
    for (auto [v,len] : G[x]) if (v != fa) {
        dfs1(v, x);
        g[x] = addt(g[x], x, {v,len});
    }
    f[x] = calc(x, g[x]);
}
 
void dfs(int x, int fa, ll lf) {
    vector<ll> vec;
    for (auto [v, len] : G[x]) {
        if(v != fa) vec.push_back(f[v].h + len);
        else vec.push_back(f[fa].h + lf);
    }
    sort(vec.begin(), vec.end(), greater<>());
    if (sz(vec) >= 4) {
        ans = max(ans, vec[0] + vec[1] + vec[2] + vec[3]);
    }
    if (sz(vec) >= 3) {
        ans = max(ans, vec[0] + vec[1] + vec[2]);
    }
    ans = max(ans, f[x].d);
    dsqueue q;
    for (auto [v, len] : G[x]) if (v != fa) q.push({x, {v,len}});
    if (fa) q.push({x, {fa, lf}});
    for (auto [v, len] : G[x]) if (v != fa) {
        q.pop();
        T tfv = f[v], tgv = g[v];
        g[x] = q.ds.query();
        f[x] = calc(x, g[x]);
		ans = max(ans, f[x].p + len*2 + f[v].p);
        ans = max(ans, f[x].d + f[v].d + len*2);
        g[v] = addt(g[v], v, {x,len});
        f[v] = calc(v, g[v]);
        dfs(v, x, len);
        f[v] = tfv; g[v] = tgv;
        q.push({x, {v, len}});
    }
}

数据结构

差分数组

cpp

template<typename T>
struct Darray {
    int n;
    vector<T> A;
    Darray(int n=0) : n(n), A(n+2) {}

    void add(int l,int r, T v=1) {
        if (l > r) return;
        A[l] += v;
        A[r+1] -= v;
    } 

    void calc() {
        for (int i = 1;i <= n; ++i) {
            A[i] += A[i-1];
        }
    }

    T& operator[] (int i) {
        return A[i];
    }
};

单调队列求区间最值

cpp

n = read(); m = read();
deque<pair<int, int>> q;
write(0); nl;
for (int i = 1;i <= n; ++i) {
    int x; x = read();
    if (!q.empty() && q.front().second < i-m) q.pop_front();
    if (!q.empty()) write(q.front().first),nl;
    while (!q.empty() && x < q.back().first) q.pop_back();
    q.push_back({x, i});
}

单调栈求右边下一个比自己大的位置

cpp

stack<pii> s; // type <int,int>  arr: A[i]
for (int i = 1;i <= n; ++i) { // for n .. 1 (on the left)
    if (s.empty() || A[i] <= s.top().first) s.push({A[i], i});
    else { //  greater elem: <= ,smaller elem: >= 
        // greater elem: < , smaller elem >
        while (!s.empty() && s.top().first < A[i]) {
            bigr[s.top().second] = i;
            s.pop();
        } 
        s.push({A[i], i});
    }
}

MinMaxQueue

cpp

struct MinMaxStack {
    vector<ll> s, maxs, mins;
    MinMaxStack() {}

    ll min() {
        if (mins.empty()) return 1e18;
        return mins.back();
    }

    ll max() {
        if (maxs.empty()) return -(1e18);
        return maxs.back();
    }

    void push(ll x) {
        s.push_back(x);
        maxs.push_back(std::max(max(), x));
        mins.push_back(std::min(min(), x));
    }

    ll pop() {
        ll ret = s.back();
        s.pop_back();
        maxs.pop_back();
        mins.pop_back();
        return ret;
    }

    bool empty() {
        return s.empty();
    }
};

struct MinMaxQueue {
    MinMaxStack s1, s2;

    MinMaxQueue() {}
    
    void push(ll x) {
        s2.push(x);
    }
    
    ll max() {
        return std::max(s1.max(), s2.max());
    }

    ll min() {
        return std::min(s1.min(), s2.min());
    }

    void pop() {
        if (s1.empty()) {
            while (!s2.empty()) s1.push(s2.pop());
        }
        s1.pop();
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
};

PropertyQueue

cpp

struct PropertyQueue {

    typedef ll T;

    static T zero() {
        return 0;
    }

    static T calc(T x, T y) {
        return x + y;
    }

    struct PropertyStack {
        vector<T> maxs;   
        vector<T> s;

        T get() {
            if (maxs.empty()) return zero();
            return maxs.back();
        }

        void push(T x) {
            s.push_back(x);
            maxs.push_back(calc(get(), x));
        }     

        T pop() {
            T ret = s.back();
            s.pop_back();
            maxs.pop_back();
            return ret;
        }

        bool empty() {
            return s.empty();
        }
    };

    PropertyStack s1, s2;
    
    void push(T x) {
        s2.push(x);
    }

    void pop() {
        if (s1.empty()) {
            while (!s2.empty()) s1.push(s2.pop());
        }
        s1.pop();
    }

    T get() {
        return calc(s1.get(), s2.get());
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
};

单栈队列

cpp

struct dsqueue {
	struct operation { int x; pair<int,ll> v; };
	struct dat {
		vector<T> a = {zero};
		T query() { return a.back(); }
		void undo() { a.pop_back(); }
		void apply(operation o) { a.push_back(addt(a.back(), o.x, o.v)); }
	};
	dat ds;
	vector<pair<int, operation>> a;
	int cnt = 0;
	dsqueue() {}
	void pop() {
		if (!cnt) {
			cnt = (int)a.size();
			reverse(a.begin(), a.end());
			for (auto& [t, o]: a)
			ds.undo(), t = 0;
			for (auto& [t, o]: a)
			ds.apply(o);
		}
		deque<operation> b[2];
		for (int t : {1, 0}) {
			for (int i = 0; !t ? i < (cnt & -cnt) : a.back().first; i++) {
			b[t].push_front(a.back().second);
			a.pop_back();
			ds.undo();
			}
		}
		for (int t : {1, 0}) {
			for (auto& o: b[t]) {
			ds.apply(o);
			a.emplace_back(t, o);
			}
		}
		cnt--;
		ds.undo();
		a.pop_back();
	}
	void push(operation o) {
		a.emplace_back(1, o);
		ds.apply(o);
	}
};

双指针

小的可以那么大的也可以

cpp

int r = 0;
ll ans = 0;  
for (int l = 1;l <= n; ++l) {
    while (r <= n && !good()) {
        r++;
        q.push(A[r]);
    }
    if (r <= n)
        ans += n-r+1;  // [l,r] good
    q.pop();
}

大的可以那么小的也可以

cpp

int r = 0;
ll ans = 0;  
for (int l = 1;l <= n; ++l) {
    while (r <= n && good()) {
        r++;
        q.push(A[r]);
    }
    ans += r - l;  // [l,r-1] good
    q.pop();
}

RMQ/ST表

cpp

template<class It,class Func,class T=typename iterator_traits<It>::value_type>
struct ST {
    vector<vector<T>> M; Func f; // f=lambda
    ST() {}
    #define log2_floor(i) (bit_width((unsigned long)i) - 1)
    ST(It l, It r, Func f) :
         M(log2_floor(distance(l,r)) + 1, vector<T>(distance(l,r))), f(f) {
        for (auto i = 0;i < sz(M[0]); ++i) M[0][i] = *(l+i); 
        for (int j = 1;j < sz(M); ++j) for (int i = 0;i+(1<<j)-1 < sz(M[0]); ++i) 
            M[j][i] = f(M[j-1][i], M[j-1][i+(1<<(j-1))]);
    }
    inline T get(int l, int r) {
        if (l > r) return T{}; // index from 0
        int k = log2_floor(r - l + 1);
        return f(M[k][l],M[k][r-(1<<k)+1]);
    }
    // ST st(A.begin(), A.end(),[](auto a,auto b) { return max(a,b); });
    // get(x,y) = max(A[x,y])
};

01Trie

cpp

struct Trie01 {
    int ch[maxn*33][2];
    int val[maxn*33], sum[maxn*33];
    int tot;

    Trie01() {
        tot = 0;
        memset(ch, 0, sizeof(ch));
        memset(val, 0, sizeof(val));
        memset(sum, 0, sizeof(sum));
    }

    int hasi(int mask, int i) {
        return (mask & (1<<(i-1))) != 0;
    }
    int seti(int mask, int i) {
        return mask | (1<<(i-1));
    }
    void insert(int x, int cnt) {
        int u = 0;
        for (int i = 32; i >= 1; --i) {
            int nxt = hasi(x, i);
            if (!ch[u][nxt]) ch[u][nxt] = ++tot;
            u = ch[u][nxt];
            sum[u] += cnt;
        }
        val[u] += cnt;
    }

    int find(int x) {
        int u = 0;
        for (int i = 32; i >= 1; --i) {
            int nxt = hasi(x, i);
            u = ch[u][nxt];
        }
        return val[u];
    }

    void del(int x, int cnt) {
        int u = 0;
        for (int i = 32; i >= 1; --i) {
            int nxt = hasi(x, i);
            u = ch[u][nxt];
            sum[u] -= cnt;
        }
        val[u] = 0; // val[u] -= cnt
        return;
    }

    int maxxor(int x) {
        int u = 0;
        int ans = 0;
        for (int i = 32; i >= 1; --i) {
            int nxt = hasi(x, i);
            if (sum[ch[u][!nxt]] > 0) { u = ch[u][!nxt]; ans = seti(ans, i); }
            else u = ch[u][nxt];
        }
        return ans;
    }
};

并查集

普通并查集

cpp

struct DSU {
    vector<int> fa, s;
    int cnt; // connect area number
    DSU(int n=1) : fa(n+1,-1), s(n+1,1), cnt(n) {}
    int size(int x) { return s[find(x)]; }
    int find(int x) { return -1 == fa[x] ? x : fa[x] = find(fa[x]); }
    bool connect(int x, int y) {
        x = find(x), y = find(y);  
        if (x == y) return false;
        if (s[x] > s[y]) swap(x, y);
        cnt--; s[y] += s[x]; 
        fa[x] = y;
        return true;
    }
};

树状数组

简单版, 单点修改

cpp

#define lowbit(x) (x&-x)
#define add(x,k)  while(x<=n) sumv[x]+=k,x+=lowbit(x)
#define query(x,a) while(x) a+=sumv[x],x-=lowbit(x)

int sumv[maxn];
// 要定义好k
add(k,y);
// 查询: 要定义好l,r
l--; ansl = 0; ansr = 0;
query(l,ansl); query(r,ansr);
printf("%d\n", ansr-ansl);

结构体版，单点修改

cpp

struct fenwick_tree {
    int n; vector<ll> sumv;
    fenwick_tree(int n = 0) : n(n), sumv(n+1) {}
    #define lowbit(x) (x&-x) 
    void add(int x, ll k) { while(x<=n) sumv[x]+=k,x+=lowbit(x); }
    ll query(int x) { ll a = 0;while(x) a+=sumv[x],x-=lowbit(x); return a; }
    template<typename F> 
  	int lower_bound(F f, int limit) {
        ll sum = 0; int cur = 0;
        for (int i = log2(limit); i >= 0; --i) {
            if (cur + (1<<i) <= limit && f(sum + sumv[cur + (1<<i)])) {
                sum += sumv[cur + (1<<i)];
                cur += 1<<i;
            }
        }
        return cur;
    }
};

结构体版，区间修改

cpp

struct fenwick_tree {
    int n; vector<ll> c, b;
    fenwick_tree(int n = 0) : n(n), c(n+2), b(n+2) {}
    #define lowbit(x) (x&-x) 
    void add(int x, ll k) { int t = x-1; while(x <= n) c[x] += k, b[x] += k*t, x += lowbit(x); }
    void add(int x, int y, ll k) { add(x, k); add(y+1, -k); }
    // 点查询： query(x, c);
    ll query(int x, vector<ll>& cur) { ll a = 0; while(x) a += cur[x],x -= lowbit(x); return a; }
    ll querySum(int x) { return query(x, c)*x - query(x, b); }
    ll query(int x, int y) { return querySum(y) - querySum(x-1); }
};

删除一个点，在前面/后面插入一个点

若n个点，m次删除。建立大小为n+m的树状数组，然后维护pos[i]表示i当前插在树状数组的哪个位置上。如果在前面插入，就把原来的数的初始位置插入在m+i的位置上，然后用cur记录前面可插入的位置，往前面插入即可。

分块

cpp

int bl;
int bi[maxn], bv[maxn], tag[maxn], ans[maxn];

void update(int l, int r) {
    for(int i = l;i <= min(bi[l]*bl, r); ++i) { // 边角料
        if (tag[bi[i]]^bv[i]) ans[bi[i]]--;
        else ans[bi[i]]++;
        bv[i] ^= 1;
    }
    if(bi[l] != bi[r])
        for(int i = (bi[r]-1)*bl + 1;i <= r; ++i) {
           if (tag[bi[i]]^bv[i]) ans[bi[i]]--;
            else ans[bi[i]]++;
            bv[i] ^= 1;
        }

    for(int i = bi[l]+1;i <= bi[r]-1; ++i) { // 分块修改
        tag[i] ^= 1;
        ans[i] = bl - ans[i];
    }
}

int query(int l, int r) {
    int ret = 0;
    for (int i = l; i <= min(bi[l]*bl, r); ++i) ret += tag[bi[i]] ^ bv[i];
    if(bi[l] != bi[r])
        for(int i = (bi[r]-1)*bl + 1;i <= r; ++i) ret +=  tag[bi[i]] ^ bv[i];
    for(int i = bi[l]+1;i <= bi[r]-1; ++i)
        ret += ans[i];
    return ret;
}

bl = sqrt(n);
for (int i = 1;i <= n; ++i) {
    bi[i] = (i-1) / bl + 1;
}

逆序对

归并排序：

cpp

template<class It>
ll cnt_inv(It l, It r) {
	if (r-l <= 1) return 0;
	auto m = l + (r-l)/2;
	ll ans = cnt_inv(l,m) + cnt_inv(m,r);
	auto p = l, q = m; int i = 0;
    vector<typename iterator_traits<It>::value_type> buf(r-l);
	while (p < m || q < r){
		if (q >= r || (p < m && *p <= *q)) buf[i++] = *p++;
		else buf[i++] = *q++, ans += m-p;
	}
	for(int i = 0; i < sz(buf); ++i) *l++ = buf[i]; 
	return ans;
}

树状数组：

cpp

struct fenwick_tree {
    int n; vector<ll> sumv;
    fenwick_tree(int n = 0) : n(n), sumv(n +1) {}
    #define lowbit(x) (x&-x) 
    void add(int x, ll k) { while(x<=n) sumv[x]+=k,x+=lowbit(x); }
    ll query(int x) { ll a = 0;while(x) a+=sumv[x],x-=lowbit(x); return a; }
};
typedef int Ti;
ll inversions(vector<Ti> A,int l,int r) {
    vector<Ti> B;
    for (int i = l; i <= r; ++i) {
        B.push_back(A[i]);
    }
    sort(B.begin(), B.end()); // 所有数据堆在B里
    int nm = unique(B.begin(), B.end()) - B.begin(); // 去重
    fenwick_tree tree(nm+1);
    for (int i = l;i <= r; ++i) 
        A[i] = lower_bound(B.begin(), B.begin()+nm, A[i]) - B.begin() + 1; // 原数组对应的值
    ll ans = 0;
    for (int i = l;i <= r; ++i) {
        ans += tree.query(nm+1) - tree.query(A[i]);
        tree.add(A[i], 1);
    }
    return ans;
}

线段树

cpp

struct SegTree {

    struct data {
        int v;
    };  
    struct lztag {
        int v;
    };

    typedef ll T;
    typedef ll Lz;

    #define M ((L+R)>>1)
    #define lson (o<<1)
    #define rson (o<<1|1)

    int LEFT, RIGHT;  // 维护的区间范围
    vector<T> sumv; // 维护的值
    vector<Lz> tag; // 懒标记
    vector<bool> islazy;
    
    // 四种操作
    T add(T a, T b) {   // merge data with data
        return min(a,b);
    } 
    T addt(T a, Lz b, int l, int r) { // merge data with tag
        return a + b;
    }
    Lz addtt (Lz a, Lz b) { // merge tag with tag
        return a + b;
    }
    
    SegTree(vector<T> &arr, int left, int right) 
        : LEFT(left), RIGHT(right), sumv(right<<2), tag(right<<2), islazy(right<<2) { 
        build(arr, 1, LEFT, RIGHT);
    }

    inline void build(vector<T> &A, int o=1, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT;}
        if (L == R) sumv[o] = A[L];
        else {
            build(A, lson, L, M);
            build(A, rson, M+1, R);
            sumv[o] = add(sumv[lson], sumv[rson]);
        }
    }

    inline void mergetag(int o, Lz val) {
        if (!islazy[o]) tag[o] = val, islazy[o] = 1;
        else tag[o] = addtt(tag[o], val);
    }
    
    inline void pushdown(int o, int L, int R) {
        if (L == R || !islazy[o]) return;
        sumv[lson] = addt(sumv[lson], tag[o], L, M);
        sumv[rson] = addt(sumv[rson], tag[o], M+1, R);
        mergetag(lson, tag[o]);
        mergetag(rson, tag[o]);
        islazy[o] = 0;
    }
	// max positon in [L,R] that fullfills function v, else return -1
    template<typename valid>
    int lowerbound(int x, valid v , int o=1, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT;}
        if (L >= x && v(sumv[o])) return R;
        if (L == R) return -1;
        else {
            pushdown(o, L, R);
            int lr = -1, rr = -1;
            if (x <= M) lr = lowerbound(x, v, lson, L, M);
            if (x > M || lr == M) rr = lowerbound(x, v, rson, M+1, R);
            return max(lr, rr);
        }
    }
    
    inline void update(int x, int y, Lz val, int o=1, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT;}
        if (x <= L && R <= y) sumv[o] = addt(sumv[o], val, L, R), mergetag(o, val);
        else {
            pushdown(o, L, R);
            if (x <= M) update(x, y, val, lson, L, M);
            if (y > M) update(x, y, val, rson, M+1, R);
            sumv[o] = add(sumv[lson], sumv[rson]); 
        }
    }

    inline T query(int x, int y, int o=1, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT;}
        pushdown(o, L, R);
        if (x <= L && R <= y) return sumv[o];
        else if (x <= M && y > M) return add(query(x, M, lson, L, M), query(M+1, y, rson, M+1, R));
        else if (x <= M)  return query(x, y, lson, L, M);
        else return query(x, y, rson, M+1, R); 
    }
};

动态开点

cpp

struct SegTree {
    struct data {
        ll minv, cnt;
    };  
    struct lztag {
        int v;
    };
    typedef data T;
    typedef int Lz;

    #define M ((L+R)>>1)

    int LEFT, RIGHT;  // 维护的区间范围
    vector<T> sumv; // 维护的值 ,=

    vector<Lz> tag; // 懒标记
    vector<int> ls, rs;
    vector<int> raw; // 离散化数组
    // 四种操作
    T add(T a, T b,int L, int R) {   // merge data with data
        if (a.minv == b.minv) return {a.minv, a.cnt + b.cnt};
        if (a.minv < b.minv) return {a.minv, a.cnt + raw[R]-raw[M]};
        return {b.minv, b.cnt + raw[M]-raw[L-1]};
    } 
    T addt(T a, Lz b, int o, int l, int r) { // merge data with tag
        a.minv += b; 
        return a;
    }
    Lz addtt (Lz a, Lz b) { // merge tag with tag
        return a + b;
    }

    T zeroT = {0,0};
    Lz zeroLz = 0; // 懒标记的零状态
    
    SegTree(int left, int right) : LEFT(left), RIGHT(right), sumv(1), tag(1), ls(1), rs(1) {}
    SegTree(vector<int>& raw) : LEFT(1), RIGHT(sz(raw)-1), sumv(1), tag(1), ls(1), rs(1), raw(raw) {}

    inline int getpos(int x) {
        return lower_bound(raw.begin(), raw.end(), x) - raw.begin();
    }

    inline void pushdown(int o, int L, int R) {
        if (L != R && !ls[o]) newnode(o); 
        if (L == R || tag[o] == zeroLz) return;
        sumv[ls[o]] = addt(sumv[ls[o]], tag[o],o, L, M);
        sumv[rs[o]] = addt(sumv[rs[o]], tag[o],o, M+1, R);
        tag[ls[o]] = addtt(tag[ls[o]], tag[o]);
        tag[rs[o]] = addtt(tag[rs[o]], tag[o]);
        tag[o] = zeroLz; 
    }

    void newnode(int o) {
        sumv.push_back(zeroT); sumv.push_back(zeroT);
        tag.push_back(zeroLz); tag.push_back(zeroLz);
        ls.push_back(0); ls.push_back(0);
        rs.push_back(0); rs.push_back(0);
        ls[o] = sz(sumv)-2; rs[o] = sz(sumv)-1;
    }

    inline void insert(int x, Lz val, int o=0, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT; x = getpos(x); }
        if (L == R) sumv[o] = addt(sumv[o], val,o, L, R);
        else {
            pushdown(o, L, R);
            if (x <= M) insert(x, val, ls[o], L, M);
            else insert(x, val, rs[o], M+1, R);
            sumv[o] = add(sumv[ls[o]], sumv[rs[o]],L,R);
        }
    }

    inline void update(int x, int y, Lz val, int o=0, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT; if (!raw.empty()) x = getpos(x)+1, y = getpos(y); }
        if (x <= L && R <= y) sumv[o] = addt(sumv[o], val,o, L, R), tag[o] = addtt(tag[o], val);
        else {
            pushdown(o, L, R);
            if (x <= M) update(x, y, val, ls[o], L, M);
            if (y > M) update(x, y, val, rs[o], M+1, R);
            sumv[o] = add(sumv[ls[o]], sumv[rs[o]],L,R); 
        }
    }

    inline T query(int x=-1, int y=-1, int o=0, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT; if (x==-1) x=LEFT,y=RIGHT; else if (!raw.empty()) x = getpos(x)+1, y = getpos(y); }
        pushdown(o, L, R);
        if (x <= L && R <= y) return sumv[o];
        else if (x <= M && y > M) return add(query(x, M, ls[o], L, M), query(M+1, y, rs[o], M+1, R),L,R);
        else if (x <= M)  return query(x, y, ls[o], L, M);
        else return query(x, y, rs[o], M+1, R); 
    }
};

扫描线

cpp

struct SegTree {
    struct data {
        ll minv, cnt;
    };  
    struct lztag {
        int v;
    };
    typedef data T;
    typedef int Lz;

    #define M ((L+R)>>1)

    int LEFT, RIGHT;  // 维护的区间范围
    vector<T> sumv; // 维护的值 ,=

    vector<Lz> tag; // 懒标记
    vector<int> ls, rs;
    vector<int> raw; // 离散化数组
    // 四种操作
    T add(T a, T b,int L, int R) {   // merge data with data
        if (a.minv == b.minv) return {a.minv, a.cnt + b.cnt};
        if (a.minv < b.minv) return {a.minv, a.cnt + raw[R]-raw[M]};
        return {b.minv, b.cnt + raw[M]-raw[L-1]};
    } 
    T addt(T a, Lz b, int o, int l, int r) { // merge data with tag
        a.minv += b; 
        return a;
    }
    Lz addtt (Lz a, Lz b) { // merge tag with tag
        return a + b;
    }

    T zeroT = {0,0};
    Lz zeroLz = 0; // 懒标记的零状态
    
    SegTree(int left, int right) : LEFT(left), RIGHT(right), sumv(1), tag(1), ls(1), rs(1) {}
    SegTree(vector<int>& raw) : LEFT(1), RIGHT(sz(raw)-1), sumv(1), tag(1), ls(1), rs(1), raw(raw) {}

    inline int getpos(int x) {
        return lower_bound(raw.begin(), raw.end(), x) - raw.begin();
    }

    inline void pushdown(int o, int L, int R) {
        if (L != R && !ls[o]) newnode(o); 
        if (L == R || tag[o] == zeroLz) return;
        sumv[ls[o]] = addt(sumv[ls[o]], tag[o],o, L, M);
        sumv[rs[o]] = addt(sumv[rs[o]], tag[o],o, M+1, R);
        tag[ls[o]] = addtt(tag[ls[o]], tag[o]);
        tag[rs[o]] = addtt(tag[rs[o]], tag[o]);
        tag[o] = zeroLz; 
    }

    void newnode(int o) {
        sumv.push_back(zeroT); sumv.push_back(zeroT);
        tag.push_back(zeroLz); tag.push_back(zeroLz);
        ls.push_back(0); ls.push_back(0);
        rs.push_back(0); rs.push_back(0);
        ls[o] = sz(sumv)-2; rs[o] = sz(sumv)-1;
    }

    inline void insert(int x, Lz val, int o=0, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT; x = getpos(x); }
        if (L == R) sumv[o] = addt(sumv[o], val,o, L, R);
        else {
            pushdown(o, L, R);
            if (x <= M) insert(x, val, ls[o], L, M);
            else insert(x, val, rs[o], M+1, R);
            sumv[o] = add(sumv[ls[o]], sumv[rs[o]],L,R);
        }
    }

    inline void update(int x, int y, Lz val, int o=0, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT; if (!raw.empty()) x = getpos(x)+1, y = getpos(y); }
        if (x <= L && R <= y) sumv[o] = addt(sumv[o], val,o, L, R), tag[o] = addtt(tag[o], val);
        else {
            pushdown(o, L, R);
            if (x <= M) update(x, y, val, ls[o], L, M);
            if (y > M) update(x, y, val, rs[o], M+1, R);
            sumv[o] = add(sumv[ls[o]], sumv[rs[o]],L,R); 
        }
    }

    inline T query(int x=-1, int y=-1, int o=0, int L=1, int R=-1) {
        if (R == -1) {L = LEFT; R = RIGHT; if (x==-1) x=LEFT,y=RIGHT; else if (!raw.empty()) x = getpos(x)+1, y = getpos(y); }
        pushdown(o, L, R);
        if (x <= L && R <= y) return sumv[o];
        else if (x <= M && y > M) return add(query(x, M, ls[o], L, M), query(M+1, y, rs[o], M+1, R),L,R);
        else if (x <= M)  return query(x, y, ls[o], L, M);
        else return query(x, y, rs[o], M+1, R); 
    }
};

ll sweepline(vector<tuple<int,int,int,int>>& A) {
    struct Line {
        ll y1, y2, x, k;
        bool operator<(const Line& l) const {
            if (x == l.x) return k > l.k;
            return x < l.x; 
        }
    };
    vector<Line> v; 
    vector<int> B; 
    for (auto [x1,y1,x2,y2] : A) {
        v.push_back({y1,y2,x1,1});
        v.push_back({y1,y2,x2,-1});
        B.push_back(y1);
        B.push_back(y2);
    }
    sort(v.begin(), v.end());
    sort(B.begin(), B.end());
    int nm = unique(B.begin(), B.end()) - B.begin(); 
    while (sz(B) != nm) B.pop_back();
    SegTree seg(B);
    ll prex = 0;
    ll ans = 0;
    for (auto [y1,y2,x,k] : v) {
        auto [minv, cnt] = seg.query();
        cnt = minv ? B.back()-B[0] : cnt;
        ans += (x - prex)*cnt;
        seg.update(y1,y2, k);
        prex = x;
    }
    return ans;
}

权值线段树

cpp

ll sumv[maxn*4];

#define mid ((l+r)>>1)
#define ls (o<<1)
#define rs (o<<1|1)

void insert(int o, int l, int r, int x) {
    if (l == r) sumv[o]++;
    else {
        if (x <= mid) insert(ls, l, mid, x);
        else insert(rs, mid+1, r, x);
        sumv[o] = sumv[ls] + sumv[rs];
    } 
}

ll query(int o, int l, int r, int ql, int qr) {
    if (l > r) return 0;
    if (ql <= l && r <= qr) return sumv[o];
    else {
        ll ret = 0;
        if (ql <= mid) ret += query(ls, l, mid, ql, qr);
        if (qr > mid) ret += query(rs, mid+1, r, ql, qr); 
        return ret;
    }
}

Splay

cpp

typedef int T;

struct SplayTree {
    struct node {
        T v; // key;
        node* f=nullptr;
        node* c[2] = {nullptr, nullptr};
        int siz=0;
        node() {}
        node(node* f,int k, int x) : v(x),f(f),siz(1) {
            if (f) f->c[k] = this;
        }
        void pushup() {
            if (!c[0] && !c[1]) {
                siz = 1;
            }
            else if (!c[0]) {
                siz = c[1]->siz + 1;
            }
            else if (!c[1]) {
                siz = c[0]->siz + 1;
            }
            else {
                siz = c[0]->siz + c[1]->siz + 1;
            }
        }
    } *root = nullptr;
    SplayTree() {}

    void rotate(node* n) { // assume this is not root
        int v = n->f->c[0] == n;
        auto p = n->f, m = n->c[v];
        if (p->f) p->f->c[p->f->c[1] == p] = n;
        n->f = p->f, n->c[v] = p;
        p->f = n, p->c[v^1] = m;
        if (m) m->f = p;
        p->pushup(), n->pushup();
    }

    void splay(node*n, node *s=nullptr) {
        while (n->f != s) {
            auto m = n->f, l = m->f;
            if (l == s) rotate(n);
            else if ((l->c[0] == m) == (m->c[0] == n)) rotate(m), rotate(n);
            else rotate(n), rotate(n);
        }
        if (!s) root = n;
    }

    void insert(T v) {
        if (!root) { root = new node(nullptr,0,v); return;}
        for (node* x = root;;) 
            if (v <= x->v && x->c[0]) x = x->c[0];
            else if (v > x->v && x->c[1]) x = x->c[1];
            else { int k = v > x->v; x->c[k] = new node(x,k,v),splay(x->c[k]);return;}  
    }
    node* getelement(node* x,int k) { for (node* v = x; ; v = v->c[k]) if (!v->c[k]) return v; }
    node* gethelper(node* x,int k) {
        if (x == nullptr) x = getelement(root,k);
        else {
            splay(x);
            if (!x->c[k^1]) return nullptr;
            x = getelement(x->c[k^1],k);
        }
        splay(x);  return x;
    }
    node* getprev(node* x) { return gethelper(x, 1); }
    node* getnext(node* x) { return gethelper(x, 0); }

    void erase(node* x) {
        if (!root) return; 
        splay(x);
        node* l = x->c[0] ? getelement(x->c[0],1) : nullptr; 
        node* rs = x->c[1];
        if (!l && !rs) root = nullptr;
        else if (!l) root = rs, root->f = nullptr;
        else if (!rs) root = x->c[0], root->f = nullptr;
        else {
            // print(root); 
            l->c[1] = x->c[1]; if (rs) rs->f = l;
            x->c[0]->f = nullptr; root = x->c[0];
            splay(rs);
        }
    }
    node* lower_bound(T v) {
        if (!root) return nullptr;
        for (node* x = root, *ret = nullptr; ; ) {
            assert(x); 
            if (x->v >= v && (!ret || x->v <= ret->v)) ret = x;
            if (x->v >= v && x->c[0]) x = x->c[0];
            else if (x->v < v && x->c[1]) x = x->c[1];
            else {  splay(x); return ret;}
        }
    }
    node* upper_bound(T v) {
        if (!root) return nullptr;
        for (node* x = root, *ret = nullptr; ; ) {
            if (x->v > v && (!ret || x->v <= ret->v)) ret = x;
            if (x->v > v && x->c[0]) x = x->c[0];
            else if (x->v <= v && x->c[1]) x = x->c[1];
            else { splay(x); return ret;}
        }
    }
    node* kth(int k) {
        for (node* x = root; ; ) {
            int l = x->c[0] ? x->c[0]->siz + 1 : 1;
            if (l == k) { splay(x); return x; }
            else if (l < k) x = x->c[1], k -= l;
            else x = x->c[0];
        }
    }
    int getrank(T v) {
        if (!root || !getprev(lower_bound(v))) return 1;
        return root->c[0] ? root->c[0]->siz + 2 : 2;
    }
};

Splay压行

cpp

template<class data_t=int, class Comp=std::less<data_t>> 
struct Splay {
    struct node {
        int p=0, c[2]={}, siz=0;
        data_t v;
        node() {}
        node(int fa,data_t v) : p(fa), siz(1), v(v) {}
        operator data_t() const { return v; }
    };
    vector<node> t;
    int root = 0;
    Splay() : t(1) {}

    inline int newnode(int fa,int k,data_t v) {
        t.push_back(node(fa, v));
        if (fa) t[fa].c[k] = sz(t)-1;
        return sz(t)-1;
    }
    inline void pushup(int x) {
        t[x].siz = t[t[x].c[0]].siz + t[t[x].c[1]].siz + 1;
    }
    inline void connect(int p, int x, int k=0) {
        t[x].p = p;
        if (p) t[p].c[k] = x;
    }
    inline void rotate(int n) { // assume this is not root
        int p = t[n].p,pp = t[p].p,k = t[p].c[1] == n;
        connect(p, t[n].c[k^1], k),connect(pp, n, t[pp].c[1]==p),connect(n,p,k^1);
        pushup(p), pushup(n);
    }
    inline node* gethelper(int x,int k) {
        x = x ? t[x].c[k^1] : root;
        while (t[x].c[k]) x = t[x].c[k];
        return &t[splay(x)];
    }
    inline node* getprev(node* x) { return gethelper(splay(x - &t[0]),1); }
    inline node* getnext(node* x) { return gethelper(splay(x - &t[0]),0); }

    inline bool empty() { return size() == 0; }
    inline int size() { return t[root].siz; }
    inline node* end() { return &t[0]; }
    inline node* begin() { return kth(1); }
    inline node* find(data_t v) { auto it =  lower_bound(v); return it->v==v ? it : end(); }

    int splay(int n, int s=0) {
        if (!n) return 0; 
        for (int m=t[n].p,l=t[m].p; t[n].p != s; rotate(n),m=t[n].p,l=t[m].p) 
            if (l != s) (t[l].c[0] == m) == (t[m].c[0] == n) ? rotate(m) : rotate(n);
        return s ? n : root=n;
    }
    
    void insert(data_t v) {
        int x=root, fa=0;
        while (x) fa=x, x=t[x].c[Comp{}(t[x].v,v)];
        splay(newnode(fa,Comp{}(t[fa].v,v),v));
    }

    inline void erase(node* x) { erase(x - &t[0]); }
    void erase(int x) { 
        splay(x);
        int l = t[x].c[0],ls=l, rs = t[x].c[1]; while (t[l].c[1]) l = t[l].c[1]; 
        if (!l || !rs) root = t[x].c[l==0], t[root].p = 0,splay(l);
        else connect(l,rs,1), connect(0,ls,0),splay(rs);
    }

    node* lower_bound(data_t v) {
        int x=root, ret=0, fa=0;
        while (x) ret = !Comp{}(t[x].v, v) && (!ret || !Comp{}(t[ret].v, t[x].v)) ? 
            x : ret, fa=x, x = t[x].c[Comp{}(t[x].v, v)];
        splay(fa); return &t[ret]; 
    }

    inline node* upper_bound(data_t v) {
        int x=root, ret=0, fa=0;
        while (x) ret =  Comp{}(v,t[x].v)  && (!ret || !Comp{}(t[ret].v, t[x].v)) ? 
            x : ret,fa=x, x = t[x].c[!Comp{}(v,t[x].v)];
        splay(fa); return &t[ret]; 
    }
    inline node* kth(int k) {
        if (k <= 0 || k > size()) return end();
        for (int x=root,l;;x = t[x].c[l<k], k -= (l<k?l:0)) 
            if ((l=t[x].c[0] ? t[t[x].c[0]].siz + 1 : 1)==k) return &t[splay(x)];
    }
    inline int getrank(int v) {
        if (!root || getprev(lower_bound(v)) == end()) return 1;
        return t[root].c[0] ? t[t[root].c[0]].siz + 2 : 2;
    }
};

文艺Splay

cpp

template<class data_t=int,class meta_t=int, class lazy_t=meta_t, class Comp=std::less<data_t>> 
struct Splay {
    struct node {
        int p=0, c[2]={}, siz=0;
        data_t v; meta_t mv, sum; lazy_t lz;
        bool islazy=0;
        node() {}
        node(int fa,data_t v) : p(fa), siz(1), v(v) {}
        node(int fa,data_t v,meta_t mv) : p(fa), siz(1), v(v), mv(mv),sum(mv) {}
        operator meta_t() const { return sum; }
        node& operator=(const meta_t v) {
            mv = sum = v;
            return *this;
        }

        static meta_t combine(meta_t a,meta_t b) {
            return a + b;
        }
        void apply(lazy_t op) {
            // update mv, sum, lz
            mv += op; sum += op * siz;
            if (islazy) {
                lz += op;
            } else {
                lz = op;
            }
        }
    };
    vector<node> t;
    int root = 0;
    Splay() : t(1) {}
    
    inline int newnode(int fa,int k,data_t v, meta_t mv) {
        t.push_back(node(fa, v, mv));
        if (fa) t[fa].c[k] = sz(t)-1;
        return sz(t)-1;
    }
    inline void pushdown(int x) {
        if (!t[x].islazy) return;
        if (t[x].c[0]) t[t[x].c[0]].apply(t[x].lz), t[t[x].c[0]].islazy = 1;
        if (t[x].c[1]) t[t[x].c[1]].apply(t[x].lz), t[t[x].c[1]].islazy = 1;
        t[x].islazy = false;
    }
    inline void pushup(int x) {
        t[x].siz = t[t[x].c[0]].siz + t[t[x].c[1]].siz + 1;
        if (t[x].c[0]) t[x].sum = node::combine(t[t[x].c[0]].sum, t[x].mv);
        else t[x].sum = t[x].mv;
        if (t[x].c[1]) t[x].sum = node::combine(t[x].sum, t[t[x].c[1]].sum);
    }
    inline void connect(int p, int x, int k=0) {
        t[x].p = p;
        if (p) t[p].c[k] = x;
    }
    inline void rotate(int n) { // assume this is not root
        int p = t[n].p,pp = t[p].p,k = t[p].c[1] == n;
        connect(p, t[n].c[k^1], k),connect(pp, n, t[pp].c[1]==p),connect(n,p,k^1);
        pushup(p), pushup(n);
    }
    inline node* gethelper(int x,int k) {
        x = x ? t[x].c[k^1] : root;
        while (t[x].c[k]) x = t[x].c[k];
        return &t[splay(x)];
    }
    inline node* getprev(node* x) { return gethelper(splay(x - &t[0]),1); }
    inline node* getnext(node* x) { return gethelper(splay(x - &t[0]),0); }

    inline bool empty() { return size() == 0; }
    inline int size() { return t[root].siz; }
    inline node* end() { return &t[0]; }
    inline node* begin() { return kth(1); }
    inline node* find(data_t v) { auto it =  lower_bound(v); return it->v==v ? it : end(); }
    node& operator[](data_t i) { 
        auto it = find(i); 
        if (it == end()) insert(i);
        return *find(i);
    }

    int splay(int n, int s=0) {
        if (!n) return 0; 
        for (int m=t[n].p,l=t[m].p; t[n].p != s; rotate(n),m=t[n].p,l=t[m].p) 
            if (l != s) (t[l].c[0] == m) == (t[m].c[0] == n) ? rotate(m) : rotate(n);
        return s ? n : root=n;
    }
    void insert(data_t v, meta_t mv=meta_t{}) {
        int x=root, fa=0;
        while (x) pushdown(x),fa=x, x=t[x].c[Comp{}(t[x].v,v)];
        splay(newnode(fa,Comp{}(t[fa].v,v),v,mv));
    }
    inline void erase(node* x) { erase(x - &t[0]); }
    void erase(int x) { 
        splay(x);
        int l = t[x].c[0],ls=l, rs = t[x].c[1]; while (t[l].c[1]) pushdown(l),l = t[l].c[1]; 
        if (!l || !rs) root = t[x].c[l==0], t[root].p = 0,splay(l);
        else connect(l,rs,1), connect(0,ls,0),splay(rs);
    }

    node* lower_bound(data_t v) {
        int x=root, ret=0, fa=0;
        while (x) pushdown(x),ret = !Comp{}(t[x].v, v) && (!ret || !Comp{}(t[ret].v, t[x].v)) ? 
            x : ret, fa=x, x = t[x].c[Comp{}(t[x].v, v)];
        splay(fa); return &t[ret]; 
    }

    inline node* upper_bound(data_t v) {
        int x=root, ret=0, fa=0;
        while (x) pushdown(x),ret =  Comp{}(v,t[x].v)  && (!ret || !Comp{}(t[ret].v, t[x].v)) ? 
            x : ret,fa=x, x = t[x].c[!Comp{}(v,t[x].v)];
        splay(fa); return &t[ret]; 
    }
    inline node* kth(int k) {
        if (k <= 0 || k > size()) return end();
        for (int x=root,l;;pushdown(x),x = t[x].c[l<k], k -= (l<k?l:0)) 
            if ((l=t[x].c[0] ? t[t[x].c[0]].siz + 1 : 1)==k) return &t[splay(x)];
    }
    inline int getrank(int v) {
        if (!root || getprev(lower_bound(v)) == end()) return 1;
        return t[root].c[0] ? t[t[root].c[0]].siz + 2 : 2;
    }

    node* query(data_t l,data_t r) {
        int pre = getprev(lower_bound(l)) - end();
        int nxt = upper_bound(r) - end();
        if (!nxt && !pre) return &t[root];
        if (!nxt) return &t[t[splay(pre)].c[1]];
        if (!pre) return &t[t[splay(nxt)].c[0]];
        splay(pre); splay(nxt,pre);
        return &t[t[nxt].c[0]];
    }

    void update(data_t l, data_t r, lazy_t op) {
        auto it = query(l,r);
        it->apply(op); it->islazy = 1;
    }

};

文艺指针Splay

cpp

template<typename T, typename Lz>
struct Splay {
    Lz ZERO;

    struct Node {
        Node **ch, *fa; 
        int sz, rep;
        T v; Lz tag;
        Node() {
            ch = new Node*[2];
            ch[0] = NULL;
            ch[1] = NULL;
            fa = NULL;
            sz = 1; rep = 1;
        }
        Node(T tv, Node* tfa = NULL) {
            ch = new Node*[2];
            ch[0] = NULL;
            ch[1] = NULL;
            fa = tfa;
            sz = 1; rep = 1;
            v = tv;
        }
        ~Node() {
            if (ch != NULL) {
                delete ch;
            } 
        }
    };

    Node* root0;

    void (*add)(Node*);
    void (*addt)(Node*, Lz, int, int);
    Lz (*addtt)(Lz, Lz);
    int LEFT, RIGHT;

    #define child x->ch[nxt]
    #define ls(x) x->ch[0]
    #define rs(x) x->ch[1]
    #define fa(x) x->fa
    #define root rs(root0)
    inline int size(Node* x) { return x? x->sz : 0; }

    
    #define ident(x) (x == rs(fa(x)))
    inline void connect(Node* x, Node* f, int k) { f->ch[k] = x; if(x) fa(x) = f; }
    #define update(x)  x->sz = size(ls(x)) + size(rs(x)) + x->rep, add(x)
    inline int size() { return size(root);}
    inline Node* newnode(T v, Node* fa) { Node *ret = new Node(v, fa); ret->tag = ZERO; return ret; }


    Splay(vector<T> &A, int left = 1, int right = -1,
          void (*fadd)(Node*) = [](Node *a) { if (!a) return; if (ls(a)) a->v += ls(a)->v; if (rs(a)) a->v += rs(a)->v; }, 
          void (*faddt)(Node*, Lz,int,int) = [](Node *a, Lz t, int l=0, int r=0)  { if (!a) return; a->v += t * (r-l+1); },
          Lz (*faddtt)(Lz, Lz) = [](Lz a, Lz b) { return a + b; },
          Lz zero = 0, T maxv = INT_MAX, T minv = INT_MIN) {
        if (right == -1) right = A.size()-1;
        else RIGHT = right;
        LEFT = left; 
        add = fadd; addt = faddt; addtt = faddtt; ZERO = zero;

        T mxv = maxv; T mnv = minv; 

        root0 = new Node;
        root0->ch[1] = newnode(mnv, root0); 
        root->ch[1] = newnode(mxv, root); 
        ls(root->ch[1]) = build(A, LEFT, RIGHT, root->ch[1]); 
        update(root->ch[1]);
        update(root);
    }
    
    void delAll(Node *x) {
        if (x == NULL) return;
        if (ls(x) != NULL) delAll(ls(x));
        if (rs(x) != NULL) delAll(rs(x));
        delete x;
        return;
    }
    
    ~Splay() {
        if (root != NULL) delAll(root); 
        if (root0 != NULL) {
            delete root0;
        }
    }

    Node* build(vector<T> &A, int l, int r, Node* fa) {
        if (l > r) return NULL;
        int m = (l + r) >> 1;
        Node* x = newnode(A[m], fa);
        x->tag = ZERO;
        ls(x) = build(A, l, m-1, x);
        rs(x) = build(A, m+1, r, x);
        update(x);
        return x;
    }

    void pushdown(Node* x) {
        if (!x || x == root0) return;
        if (ls(x)) addt(ls(x), x->tag, 1, size(ls(x))), ls(x)->tag = addtt(ls(x)->tag, x->tag);
        if (rs(x)) addt(rs(x), x->tag, 1, size(rs(x))), rs(x)->tag = addtt(rs(x)->tag, x->tag);
        x->tag = ZERO;
    }

    void rotate(Node* x) {
        Node *f = fa(x), *ff = fa(f); int k = ident(x);
        if (x->ch[k^1]) connect(x->ch[k^1], f, k); 
        else f->ch[k] = NULL;
        connect(x, ff, ident(f)); 
        connect(f, x, k^1);       
        update(f); update(x);
    }

    void splay(Node* x, Node* top) {
        Node* to = fa(top); 
        while (fa(x) != to) { 
            if (fa(fa(x)) == to) rotate(x); 
            else if (ident(x) == ident(fa(x))) { rotate(fa(x)); rotate(x); } 
            else rotate(x), rotate(x);
        }
    }

    Node* kth(int k) { 
        Node* x = root; int ret = 0;
        while (true) {
            pushdown(x);
            int used = x->sz - size(rs(x));
            if (size(ls(x)) < k && k <= used) { splay(x, root); return x; }
            if (k < used) x = ls(x);
            else x = rs(x), k -= used;
        }
    }
 
    inline void operate(int l, int r, Lz lz) {
        Node *lx = kth(l); Node *rx = kth(r+2);
        splay(lx, root); splay(rx, rs(lx)); Node* rt = ls(rx);
        if (!rt) return;
        addt(rt, lz, l, r);
        rt->tag = addtt(rt->tag, lz);
        update(rx); update(lx);
    }

    void print(Node* x, void (*myprint)(Node*)) {
        pushdown(x);
        if (!x) return;
        if (x->ch[0]) print(x->ch[0], myprint);
        myprint(x);
        if (x->ch[1]) print(x->ch[1], myprint);
    }

    void print(void (*myprint)(Node*) = 
        [](Node* x) { if (x->v != INT_MAX && x->v != INT_MIN) cout << x->v << " "; }) {
        Node *lx = kth(1);
        Node *rx = kth(RIGHT+2);
        splay(lx, root); 
        splay(rx, rs(lx)); Node* rt = ls(rx);
        if (!rt) return;
        print(rt, myprint); cout << endl;
    }

    void insert(int pos, vector<T> &A) {
       Node *lx = kth(pos+1); Node *rx = kth(pos+2); 
       splay(lx, root); splay(rx, rs(lx));
       ls(rx) = build(A, 1, A.size()-1, rx);
       Node* rt = ls(rx);
        update(rx); update(lx);
    }

    void del(int l, int r) {
        Node *lx = kth(l); Node *rx = kth(r+2);
        splay(lx, root); splay(rx, rs(lx)); 
        delAll(ls(rx)); ls(rx) = NULL;
        Node* rt = ls(rx);
        update(rx); update(lx);
    }

    T query(int l, int r) {
        Node *lx = kth(l); Node *rx = kth(r+2);
        splay(lx, root); splay(rx, rs(lx));
        Node* rt = ls(rx);
        update(rx); update(lx);
        return ls(rx)->v;
    }
};

主席树

cpp

struct Persistable_SegTree {
    struct data {
        ll minv, cnt;
    };  
    struct lztag {
        int v;
    };
    typedef int T;
    typedef int Lz;

    #define M ((L+R)>>1)

    int LEFT, RIGHT;  // 维护的区间范围
    vector<T> sumv; // 维护的值 ,=

    vector<Lz> tag; // 懒标记
    vector<int> ls, rs;
    vector<int> raw; // 离散化数组
    // 四种操作
    T add(T a, T b,int L, int R) {   // merge data with data
        return a + b;
    } 
    T addt(T a, Lz b, int o, int l, int r) { // merge data with tag
        if (!raw.empty()) l = raw[l], r = raw[r];
        if (b == INT_MAX) return a;
        return (r-l+1) *1ll * b;
    }
    Lz addtt (Lz a, Lz b) { // merge tag with tag
        if (b == INT_MAX) return a;
        return b;
    }

    T zeroT = 0;
    Lz zeroLz = INT_MAX; // 懒标记的零状态
    vector<int> his, ver;
    
    Persistable_SegTree(int left, int right) : LEFT(left), RIGHT(right), sumv(1), tag(1), ls(1), rs(1), his(1), ver(1) {}
    Persistable_SegTree(vector<int>& raw) : LEFT(1), RIGHT(sz(raw)-1), sumv(1), tag(1), ls(1), rs(1), raw(raw), his(1), ver(1) {}

    inline int getpos(int x) {
        return lower_bound(raw.begin(), raw.end(), x) - raw.begin();
    }

    inline void pushdown(int o, int L, int R) {
        if (L != R) newnode(o);
        if (L == R || tag[o] == zeroLz) return;
        sumv[ls[o]] = addt(sumv[ls[o]], tag[o],o, L, M);
        sumv[rs[o]] = addt(sumv[rs[o]], tag[o],o, M+1, R);
        tag[ls[o]] = addtt(tag[ls[o]], tag[o]);
        tag[rs[o]] = addtt(tag[rs[o]], tag[o]);
        tag[o] = zeroLz; 
    }

    inline void newnode(int o) {
        if (!ls[o]){
            ls[o] = addnode(ver[o]); rs[o] = addnode(ver[o]);
        } else if (ver[ls[o]] != ver[o]) {
            ls[o] = addnode(ver[o], ls[o]);
            rs[o] = addnode(ver[o], rs[o]);
        }
    }

    inline int addnode(int v, int o=-1) {
        sumv.push_back(zeroT);
        tag.push_back(zeroLz);
        ls.push_back(0);
        rs.push_back(0);
        ver.push_back(v);
        if (o != -1) {
            sumv.back() = sumv[o];
            tag.back() = tag[o];
            ls.back() = ls[o];
            rs.back() = rs[o];
        }
        return sz(sumv)-1;
    }
	// tim version based on, c: create new version
    inline void update(int x, int y, Lz val,int tim=-1,bool c = true, int o=0, int L=1, int R=-1) {
        if (R == -1) {
            L = LEFT; R = RIGHT; 
            if (!raw.empty()) x = getpos(x)+1, y = getpos(y); 
        }
        if (x <= L && R <= y) sumv[o] = addt(sumv[o], val,o, L, R), tag[o] = addtt(tag[o], val);
        else {
            if (L == LEFT && R == RIGHT) {
                if (tim == -1) tim = sz(his)-1;
                if (c) {
                    o = addnode(sz(his), his[tim]);
                    his.push_back(o);    
                } else o = his[tim];
            }
            pushdown(o, L, R);
            if (x <= M) update(x, y, val,tim,c, ls[o], L, M);
            if (y > M) update(x, y, val,tim,c, rs[o], M+1, R);
            sumv[o] = add(sumv[ls[o]], sumv[rs[o]],L,R); 
        }
    }

    inline T query(int x=-1, int y=-1,int tim=-1,bool c=true,  int o=0, int L=1, int R=-1) {
        if (R == -1) {
            L = LEFT; R = RIGHT; 
            if (x==-1) x=LEFT,y=RIGHT; 
            else if (!raw.empty()) x = getpos(x)+1, y = getpos(y); 
        }
         if (L == LEFT && R == RIGHT) {
            if (tim == -1) tim = sz(his)-1;
            if (c) {
                o = addnode(sz(his), his[tim]);
                his.push_back(o);    
            } else o = his[tim];
        }
        pushdown(o, L, R);
        if (x <= L && R <= y) return sumv[o];
        else if (x <= M && y > M) return add(query(x, M, ls[o], L, M), query(M+1, y, rs[o], M+1, R),L,R);
        else if (x <= M)  return query(x, y, tim,c, ls[o], L, M);
        else return query(x, y, tim,c, rs[o], M+1, R); 
    }
};

红黑树PBDS

cpp

/by shenben
#include<cstdio>
#include<iostream>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> bbt;
int n;ll k,ans;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
} 
int main(){
    n=read();
    for(int i=1,opt;i<=n;i++){
        opt=read();k=read();
        if(opt==1) bbt.insert((k<<20)+i);
        if(opt==2) bbt.erase(bbt.lower_bound(k<<20));
        if(opt==3) printf("%d\n",bbt.order_of_key(k<<20)+1);
        if(opt==4) ans=*bbt.find_by_order(k-1),printf("%lld\n",ans>>20);
        if(opt==5) ans=*--bbt.lower_bound(k<<20),printf("%lld\n",ans>>20);
        if(opt==6) ans=*bbt.upper_bound((k<<20)+n),printf("%lld\n",ans>>20);
    }
    return 0;
}

哈希表pbds

cpp

1	gp_hash_table<int,bool> h;

莫队

cpp

struct Mo {
    typedef int T; // 答案的类型
 
    int l = 1, r = 0; 
    T cur; // 当前答案
 
    inline void init() { // 计算初始情况
        cur = 0;
    }
 
    inline void Add(int x) { // 增加一个元素,位置为x
        cnt[A[x]]++;
        if (cnt[A[x]] == 1) cur++;
    }
 
    inline void Sub(int x) { // 减少一个元素
        cnt[A[x]]--;
        if (cnt[A[x]] == 0) cur--;
    }
 
    inline void getanswer(int l, int r, int k, int id) {
        ans[id] = cur;
    }
 
    struct Q {
        int l, r, k, id;
    };
 
    vector<Q> qes;
    int m = 0, siz = 0;
 
    Mo() {}
    
    inline void addquery(int l,int r,int id) {
        qes.push_back({l, r, m++,id});
    }
 
    void calc() {
        siz = sqrt(m); 
        sort(qes.begin(), qes.end(), [&](Q a, Q b) {
            return a.l/siz == b.l/siz ? a.r < b.r : a.l/siz < b.l/siz;
        });
        init();
        for (auto& [ql, qr, ind, id] : qes) {
            while (ql < l) Add(--l);
            while (qr > r) Add(++r);
            while (ql > l) Sub(l++);
            while (qr < r) Sub(r--);
            getanswer(l, r, ind, id);
        }
    }
};

图论

拓扑排序

cpp

struct Topo { // index from 1
    int t, ok=1; // ok is whether there is a cycle
    vector<int> topo, c; // sorted in topo(1..n)
    vector<int> s, cycle; // give cycle if false
    Topo(int n) : t(n+1),topo(n+1),c(n+1)  {
        for (int i = 1;i <= n; ++i,s.clear()) 
            if (ok && !c[i] && !dfs(i)) ok = 0;
    }
    bool dfs(int x) {
        c[x] = -1; s.push_back(x);
        for (auto v : G[x]) {
            if (c[v] < 0) {
                s.erase(s.begin(), find(s.begin(), s.end(),v)), cycle = s; 
                return false;
            }
            else if (!c[v] && !dfs(v)) return false;
        }
        c[x] = 1; topo[--t] = x; s.pop_back();
        return true;
    }
};

二分图染色

cpp

vector<int> G[maxn];
int col[maxn];
bool dfs(int x,int c) {
    col[x] = c;
    for (auto v : G[x]) {
        if (col[v] && col[v] != 3 - c) return false;
        if (!col[v] && !dfs(v, 3 - c)) return false;
    }
    return true;
}
// main
int ok = 1;
for (int i = 1;i <= n; ++i) {
    if (!col[i] && !dfs(i, 1)) {
        ok = 0;
        break;
    }
}

搜简单环

cpp

vector<int> ring;
vector<int> st = {0};
int vis[maxn];
vector<int> G[maxn];
 
bool dfs(int x) {
    vis[x] = -1;
    st.push_back(x);
    for (auto v : G[x]) {
        if (vis[v] == -1 && v != st[sz(st)-2]) {
            while (st.back() != v) {
                ring.push_back(st.back());
                st.pop_back();
            }
            ring.push_back(v);
            return true;
        }
        else if (!vis[v] && dfs(v)) return true;
    }
    st.pop_back();
    vis[x] = 1;
    return false;
}
// main
for (int i = 1;i <= n; ++i) {
    st = {0};
    if (ring.empty()) dfs(i);
}
if (ring.empty()) {
    cout << "IMPOSSIBLE\n";
    return 0;
}

SPFA,Bellman求负环

cpp

vector<int> negCycle(int n) {
    vector<ll> d(n+1, 1e18), p(n+1);
    d[1] = 0; int y = -1;
    for (int i = 1;i <= n; ++i) {
        y = -1;
        for (int x = 1;x <= n; ++x) for (auto [v, len] : G[x]) 
            if (d[v] > d[x] + len) 
                d[v] = d[x] + len, p[v] = x, y = v;
    }
    if (y == -1) return {};
    for (int i = 1;i <= n; ++i) y = p[y];
    vector<int> ret;
    for (int v = y; v != y || ret.empty(); v = p[v]) ret.push_back(v);
    reverse(ret.begin(),ret.end());
    return ret;
}

struct SPFA {
    int n, m; 
    struct Node {
        int v; ll len;
    };
    vector<vector<Node>> G;
    vector<ll> d;

    SPFA(int n, int m) : n(n), m(m), G(n+1) {}

    void addedge(int x, int y, ll val) {
        G[x].push_back({y, val});
    }

    bool calc(int s) {
        queue<int> Q;
        vector<bool> inq(n+1);
        vector<int> cnt(n+1);
        d = vector<ll>(n+1, 1e18);
        Q.push(s); inq[s] = true; d[s] = 0;

        while(!Q.empty()) {
            int x = Q.front(); Q.pop();
            inq[x] = false;
            for (auto [v, len] : G[x]) {
                if (d[v] > d[x] + len) {
                    d[v] = d[x] + len;
                    if (!inq[v]) { 
                        cnt[v]++; 
                        if (cnt[v] >= n) return false;
                        Q.push(v); inq[v] = true; 
                    }
                }
            }
        }
        return true;
    }
};

Dijkstra

cpp

struct Dijkstra {
    vector<vector<pair<int, ll>>> G;
    vector<ll> d;
    void addedge(int x, int y, ll val) { 
        if (sz(G) <= max(x,y)) {
            G.resize(max(x,y)+1);
            d.resize(max(x,y)+1);
        }
        G[x].push_back({y, val}); 
    }

    void calc(int s) {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
        int n = sz(G)-1;
        vector<bool> done(n+1);
        d.assign(n+1, 1e18); d[s] = 0;
        Q.push({d[s], s});
        while(!Q.empty()) {
            int x = Q.top().second; Q.pop();
            if (done[x]) continue; else done[x] = true;
            for (auto [v, len] : G[x]) if (d[v] > d[x] + len) {
                d[v] = d[x] + len;
                Q.push({d[v], v});
            }
        }
    }
};

k短路

cpp

vector<pair<int,ll>> G[maxn];
vector<ll> kShortestPath(int n, int s,int t, int k) {
    vector<ll> d(n+1, 1e18), ans; d[s] = 0;
    vector<int> done(n+1), cnt(n+1);
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
    q.push({d[s],s});
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (done[x]) continue; else done[x] = 1;
        for (auto [v,len] : G[x]) if (d[v] > d[x] + len) 
            d[v] = d[x] + len, q.push({d[v],v});
    }
    q.push({d[s],s});
    while (!q.empty()) {
        auto [pl,x] = q.top(); q.pop();
        if (++cnt[x] > k) continue;
        if (x == t) ans.push_back(pl);
        for (auto [v,len] : G[x]) q.push({pl+len, v});
    }
    sort(ans.begin(),ans.end());
    return ans;
}

势能Dijkstra

cpp

struct Dijkstra {    
    inline static ll phi(int i) {
        return H[i];
    }
    int n; 
    vector<vector<pair<int, ll>>> G;
    vector<ll> d;
    Dijkstra(int n) : n(n+1), G(n+1) {}
    void addedge(int x, int y, ll val) { G[x].push_back({y, val + phi(x) - phi(y)}); }

    void calc(int s) {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
        vector<bool> done(n+1);
        d.assign(n+1, 1e18); d[s] = 0;
        Q.push({d[s], s});
        while(!Q.empty()) {
            int x = Q.top().second; Q.pop();
            if (done[x]) continue; else done[x] = true;
            for (auto [v, len] : G[x]) if (d[v] > d[x] + len) {
                d[v] = d[x] + len;
                Q.push({d[v], v});
            }
        }
        for (int i = 0;i <= n; ++i) {
            d[i] -= phi(s) - phi(i);
        }
    }
};

Floyd

cpp

// init: d[i][j] = len(i, j); d[i][i] = 0; else = INF
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]);

Johnson全源最短路

cpp

struct Johnson {
    int tot, n; 
    struct Node {
        int nxt, v; ll len;
    };
    vector<Node> edges;
    vector<int> head;
    vector<ll> h;
    vector<vector<ll>> d;

    Johnson(int tn) {
        n = tn, tot = 0;
        head = vector<int>(tn+2, -1);
        h = vector<ll>(tn+2);
        d = vector<vector<ll>>(n+2, vector<ll>(n+2, 1e18));
    }

    void addedge(int x, int y, ll val) {
        edges.push_back({head[x], y, val});
        head[x] = sz(edges)-1;
    }

    bool neg() {
        for (int i = 1;i <= n; ++i) {
            addedge(n+1, i, 0);
        }
        queue<int> Q;
        vector<bool> inq(n+2);
        vector<int> cnt(n+2); int s = n+1;
        Q.push(s); inq[s] = true; d[s][s] = 0;

        while(!Q.empty()) {
            int x = Q.front(); Q.pop();
            inq[x] = false;
            for (int i = head[x]; ~i; i = edges[i].nxt) {
                int v = edges[i].v; ll len = edges[i].len;
                if (d[s][v] > d[s][x] + len) {
                    d[s][v] = d[s][x] + len;
                    if (!inq[v]) { 
                        cnt[v]++; 
                        if (cnt[v] >= n+1) return true;
                        Q.push(v); inq[v] = true; 
                    }
                }
            }
        }
        for (int i = 1;i <= n; ++i) h[i] = d[s][i];
        return false;
    }

    bool calc() {
        if (neg()) return false;
        for (int i = 1;i <= n; ++i) 
            for (int j = head[i]; ~j ; j = edges[j].nxt) 
                edges[j].len += h[i] - h[edges[j].v];
    
        for (int s = 1;s <= n; ++s) {
            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
            vector<bool> done(n+1);
            d[s][s] = 0;
            Q.push({d[s][s], s});
            while(!Q.empty()) {
                int x = Q.top().second; Q.pop();
                if (done[x]) continue; else done[x] = true;
                for (int i = head[x]; ~i; i = edges[i].nxt) {
                    int v = edges[i].v; ll len = edges[i].len;
                    if (d[s][v] > d[s][x] + len) {
                        d[s][v] = d[s][x] + len;
                        Q.push({d[s][v], v});
                    }
                }
            }
        }
        for (int i = 1;i <= n; ++i) 
            for (int j = 1;j <= n; ++j) {
                d[i][j] += h[j] - h[i];
            }
        return true;
    }
};

最小生成树

cpp

struct DSU {
    vector<int> fa, sz;
    int cnum; // connect area number
    DSU(int n) {
        fa = vector<int>(n+1, -1);
        sz = vector<int>(n+1, 1);
        cnum = n;
    }
    inline int num() { return cnum; }
    inline int size(int x) { return sz[find(x)]; }
    int find(int x) {
        if (-1 == fa[x]) return x;
        int k = find(fa[x]);
        fa[x] = k;
        return fa[x];
    }
    inline void connect(int x, int y) {
        int fax = find(x), fay = find(y);  
        if (fax == fay) return;
        cnum--; sz[fay] += sz[fax]; 
        fa[fax] = fay;
    }
};

struct MST {

    struct Node {
        int fr, to;
        ll len;
        bool operator<(const Node &x) const {
            return len < x.len;
        }
    };
    int n, mxn;

    vector<Node> edges;
    MST(int tn) {
        n = tn;
        mxn = 0;
    }

    inline void addedge(int a, int b, ll c) {
        edges.push_back({a, b, c});
        mxn = max(mxn, max(a, b));
    }

    ll calc() {
        int cnt = n - 1, i = 0;
        ll ans = 0;
        sort(edges.begin(), edges.end());
        DSU dsu(mxn);
        while (cnt > 0 && i < (int) edges.size()) {
            int a = dsu.find(edges[i].fr);
            int b = dsu.find(edges[i].to);
            if (a != b) {
                dsu.connect(a, b);
                cnt--; 
                ans += edges[i].len;
            }
            i++;
        }
        return cnt == 0 ? ans : -1; // -1: not connected
    }
};

Tarjan 缩点,割点,桥

cpp

struct Tarjan {
    // G 编号从1开始 , no multiple edges
    int n, m, timer, cnt;
    vector<vector<int>> oG, bcc, G; // original graph, G: out graph, bcc[i] 第i个强连通分量所有的点
    vector<int> dfn, low, low2,belong, cutv, iscut; // belong: 原图的点缩点后的编号, cutv: cut vertex
    vector<pii> cute; 
    vector<bool> ins;
    stack<int> s;
    
    Tarjan(int n=0) : n(n), m(0), timer(0), cnt(0), oG(n+1), 
        bcc(1),G(1),dfn(n+1,-1),low(n+1),low2(n+1),belong(n+1),iscut(n+1),ins(n+1) {}
    
    void addedge(int a, int b) {
        oG[a].push_back(b);
    }

    void dfs(int x, int fa) {
        dfn[x] = low[x] = low2[x] = ++timer;
        s.push(x); ins[x] = 1;
        int tot = 0;
        for (auto v : oG[x]) {
            if (!~dfn[v]) {
                dfs(v, x);
                if (x == fa) tot++;
                low[x] = min(low[x], low[v]);
                low2[x] = min(low2[x], low2[v]);
                if (low[v] >= dfn[x] && x != fa) {
                    iscut[x] = 1;
                }
                if (low2[v] > dfn[x]) cute.push_back({x, v});
            } else if (ins[v]) low[x] = min(low[x], dfn[v]);
            if (v != fa) low2[x] = min(low2[x], dfn[v]);
        }
        if (tot > 1) iscut[x] = 1;
        if (low[x] == dfn[x]) {
            int now; bcc.push_back(vector<int>()); G.push_back(vector<int>());
            int cur = ++cnt;
            do {
                now = s.top(); s.pop(); ins[now] = 0;
                belong[now] = cur;
                bcc.back().push_back(now);
            } while (now != x);
        }
    }

    void calc() {
        for (int i = 1;i <= n; ++i) if (!~dfn[i]) dfs(i, i);  
        for (int i = 1;i <= n; ++i) {
            if (iscut[i]) cutv.push_back(i);
            int u = belong[i];
            for (auto j : oG[i]) { 
                int v = belong[j];
                if (v != u) G[u].push_back(v);
            }
        } 
    }
};

2染色

cpp

vector<int> col[3];
int vis[maxn];
bool color2(int x, int c) {
    col[c].push_back(x);
    vis[x] = c;
    for (auto v : G[x]) {
        if (!vis[v] && !color2(v, 3 - c)) return false;
        else if (vis[v] == c) return false;
    }
    return true;
}

基环树

无向图基环树

cpp

struct RingTree {
    int n;
    vector<vector<int>> G;
    vector<bool> isr;
    vector<int> in, ring;

    RingTree(int n) : n(n), G(n+1), isr(n+1, 1), in(n+1) {}

    void addedge(int a, int b) { // 无向边
        G[a].push_back(b);
        G[b].push_back(a);
        in[a]++; in[b]++;
    }

    void calc() {
        queue<int> q;
        for (int i = 1;i <= n; ++i) if (in[i] == 1) q.push(i);
        while (!q.empty()) {
            int hd = q.front(); q.pop();
            isr[hd] = 0;
            for (auto v : G[hd]) if (in[v] > 1) {
                in[v]--;
                if (in[v] == 1) q.push(v);
            }
        }
        for (int i = 1;i <= n; ++i) if (isr[i]) {
            ring.push_back(i);
        }
    }
};

最大团

$n \leq 50$

cpp

// n = |V| d = adj matrix
int maxClique(int n, auto d) {
    vector<ll> G(n+1);
    for (int i = 1;i <= n; ++i) {
        for (int j = 1;j <= n; ++j) {
            if (d[i][j]) G[i] |= 1ll<<(j-1);
        }
    }
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    unordered_map<ll,int,custom_hash> f;
    function<int(ll)> solve = [&](ll mask) {
        if (f.find(mask) != f.end()) return f[mask];
        for (int i = n-1;i >= 0; --i) if (mask>>i & 1){
            return f[mask] = max(solve(mask ^ (1ll<<i)), 1 + solve(mask & G[i+1]));
        }
        return 0;
    };
    return solve((1ll<<n)-1);
}

树

LCA

cpp

struct LCA {
    typedef int T;
    int n;
    int logsize;
    vector<vector<pair<int, T>>> G;
    vector<int> dep;
    vector<vector<int>> p;
    vector<vector<T>> l;

    T addt(T a, T b) {
        return max(a, b);
    }
    T zero = 0;

    LCA(vector<vector<pair<int, T>>>& tG, int s) {
        G = tG;  logsize = 1 + (int)log2(G.size()+1);
        n = sz(tG)-1;
        p = vector<vector<int>>(G.size(), vector<int>(logsize));
        l = vector<vector<T>>(G.size(), vector<T>(logsize));
        dep = vector<int>(G.size());
        dep[s] = 1; dfs(s);
        for (int j = 1;j < logsize; ++j) {
            for (int i = 1;i <= n; ++i) if (p[i][j-1]) {
                p[i][j] = p[p[i][j-1]][j-1];
                if (p[i][j]) l[i][j] = addt(l[i][j-1], l[p[i][j-1]][j-1]);
            }
        }
    }

    void dfs(int x) {
        for (auto [v, len] : G[x]) {
            if (v != p[x][0]) { 
                dep[v] = dep[x] + 1;
                p[v][0] = x; l[v][0] = len;
                dfs(v); 
            }
        }
    }

    pair<int, T> query(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y); // let depx >= depy 
        T ret = zero;
        for (int j = logsize-1; j >= 0; --j) {
            if (dep[p[x][j]] >= dep[y]) { ret = addt(ret, l[x][j]); x = p[x][j]; }
        }
        if (x == y) return {x, ret};
        for (int j = logsize-1; j >= 0; --j){
            if (p[x][j] != p[y][j]) { 
                ret = addt(ret, addt(l[x][j], l[y][j]));
                x = p[x][j]; y = p[y][j];
            }
        }
        return {p[x][0], addt(ret, addt(l[x][0], l[y][0]))};
    }
};

LCA(only node)

cpp

struct LCA {
    int n;
    int logsize;
    vector<vector<int>> G;
    vector<int> dep;
    vector<vector<int>> p;

    LCA(vector<vector<int>>& tG, int s) : G(tG) {
        logsize = 1 + (int)log2(G.size()+1);
        n = sz(tG)-1;
        p = vector<vector<int>>(G.size(), vector<int>(logsize));
        dep = vector<int>(G.size());
        dep[s] = 1; dfs(s);
        for (int j = 1;j < logsize; ++j) 
            for (int i = 1;i <= n; ++i) if (p[i][j-1]) 
                p[i][j] = p[p[i][j-1]][j-1];
    }

    void dfs(int x) {
        for (auto v : G[x]) if (v != p[x][0]) {
            dep[v] = dep[x] + 1;
            p[v][0] = x;
            dfs(v); 
        }
    }

    int query(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y); // let depx >= depy 
        for (int j = logsize-1; j >= 0; --j) 
            if (dep[p[x][j]] >= dep[y]) x = p[x][j]; 
        if (x == y) return x;
        for (int j = logsize-1; j >= 0; --j) if (p[x][j] != p[y][j]) 
            x = p[x][j], y = p[y][j];
        return p[x][0];
    }
};

树剖LCA

cpp

int dep[maxn], fa[maxn], num[maxn], top[maxn], ind[maxn], son[maxn], way[maxn], lfa[maxn];
struct Data {
    int len, x, y, lca;
    bool operator<(const Data& x) const {
        return len > x.len;
    }
}A[maxn];

inline void dfs1(int x) {
    num[x] = 1;
    for (int e = head[x]; e; e = nxt[e]) if (to[e] != fa[x]) {
        int v = to[e];
        fa[v] = x; lfa[v] = lto[e];
        dep[v] = dep[x] + 1;
        dfs1(v);
        num[x] += num[v];
        if (num[v] > num[son[x]]) son[x] = v;
    }
}

inline void dfs2(int x, int topf) {
    top[x] = topf;
    if (x != topf) way[x] = way[fa[x]] + lfa[x];
    if (!son[x]) return;
    dfs2(son[x], topf);
    for (int e = head[x]; e; e = nxt[e]) if (to[e] != fa[x] && to[e] != son[x]) {
        dfs2(to[e], to[e]);
    }
}

inline pii lca(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret += way[x] + lfa[top[x]];
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return {ret + way[y] - way[x], x};
}

直径，重心

cpp

struct Diameter {
    typedef ll T;

    vector<vector<pair<int, T>>> G;
    vector<T> d;
    vector<int> nxt;
    vector<int> path;
    
    int ans1, ans2;
    T ans, dep1, dep2;

    Diameter(vector<vector<pair<int,T>>> &tG) {
        G = tG;
        nxt = vector<int>(G.size());
        d = vector<T>(G.size());
        ans1 = 0; dep1 = -1; dfs1(1, 0, 0);
        ans2 = 0; dep2 = 0; ans = dfs2(ans1, 0);
        for (int u = ans1; u != 0; u = nxt[u]) path.push_back(u);
    }
    
    T length() {
        return ans;
    }

    vector<int>& getPath() {
        return path;
    }

    int getNode() {
        return path[ans/2];
    }

    void dfs1(int x, int fa, T dep) {
        if (dep1 < dep) { ans1 = x; dep1 = dep; }
        for (auto [v, len] : G[x]) if (v != fa) dfs1(v, x, dep + len);
    }

    T dfs2(int x, int fa) {
        d[x] = 0;
        for (auto [v, len] : G[x]) if (v != fa) {
            T td = dfs2(v, x);s
            if (td + len > d[x]) {
                d[x] = td + len;
                nxt[x] = v;
            }
        }
        return d[x];
    }
};

求点到直径的距离

把直径求出来，然后从直径bfs

换根dp

cpp

typedef int T;
static T zero = 0;

T f[maxn], g[maxn];

// f(x) = calc(x, addt(fi(x,v1), fi(x,v2)...))
T calc(int x, T gx) {
    return max(1, gx);
}

T addt(T a, int x, int v) {
    return max(a, 1 + f[v]);
}
 
struct dsqueue {
	struct operation { int x, v; };
	struct dat {
		vector<T> a = {zero};
		T query() { return a.back(); }
		void undo() { a.pop_back(); }
		void apply(operation o) { a.push_back(addt(a.back(), o.x, o.v)); }
	};
	dat ds;
	vector<pair<int, operation>> a;
	int cnt = 0;
	dsqueue() {}
	void pop() {
		if (!cnt) {
			cnt = (int)a.size();
			reverse(a.begin(), a.end());
			for (auto& [t, o]: a)
			ds.undo(), t = 0;
			for (auto& [t, o]: a)
			ds.apply(o);
		}
		deque<operation> b[2];
		for (int t : {1, 0}) {
			for (int i = 0; !t ? i < (cnt & -cnt) : a.back().first; i++) {
			b[t].push_front(a.back().second);
			a.pop_back();
			ds.undo();
			}
		}
		for (int t : {1, 0}) {
			for (auto& o: b[t]) {
			ds.apply(o);
			a.emplace_back(t, o);
			}
		}
		cnt--;
		ds.undo();
		a.pop_back();
	}
	void push(operation o) {
		a.emplace_back(1, o);
		ds.apply(o);
	}
};

void dfs1(int x, int fa) {
    g[x] = zero;
    for (auto v : G[x]) if (v != fa) {
        dfs1(v, x);
        g[x] = addt(g[x], x, v);
    }
    f[x] = calc(x, g[x]);
}

void dfs(int x, int fa) {
    ans[x] = f[x];
    dsqueue q;
    for (auto v : G[x]) if (v != fa) q.push({x, v});
    if (fa) q.push({x, fa});
    for (auto v : G[x]) if (v != fa) {
        q.pop();
        T tfv = f[v], tgv = g[v];
        g[x] = q.ds.query();
        f[x] = calc(x, g[x]);
        g[v] = addt(g[v], v, x);
        f[v] = calc(v, g[v]);
        dfs(v, x);
        f[v] = tfv, g[v] = tgv;
        q.push({x, v});
    }
}

点分治

cpp

#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 3e5 + 5;


int n, m, T;
ll h[maxn], ans;
int cnt[maxn], vis[maxn];
vector<pair<int,ll>> G[maxn];

void count(int x, int fa) {
    cnt[x] = 1;
    for (auto [v, len] : G[x]) if (v != fa && !vis[v]) {
        count(v, x);
        cnt[x] += cnt[v];
    }
}

int getCent(int x,int fa, int sum) {
    for (auto [v, len] : G[x]) if (v != fa && !vis[v]) {
        if (cnt[v] > sum/2) return getCent(v, x, sum);
    }
    return x;
}

void getval(vector<pair<ll,ll>> &A, int x, int fa, ll dis) {
    A.push_back({x, dis});
    for (auto [v, len] : G[x]) if (v != fa && !vis[v]) {
        getval(A, v, x, dis + len);
    }
}

void doit(int x) {
    vector<pair<ll,ll>> A;
    for (auto [v, len]: G[x]) if (!vis[v]) {
        getval(A, v, x, len);
    }
    vector<pair<ll,int>> B; // i, dis, b/c
    B.push_back({h[x], -x});
    B.push_back({h[x], x});
    for (auto [v, dis] : A) {
        B.push_back({h[v] - dis, -v});
        B.push_back({h[v] + dis, v});
    }
    sort(B.begin(), B.end(), [](auto a, auto b) {
        if (a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    });
   
    ll mn = INT_MAX;
    for (auto [a, b] : B) {
        int v = abs(b);
        if (b < 0) {
            ans = max(ans, h[v] - mn);
        } else {
            mn = min(mn, h[v]);
        }
    }
}

void solve(int x) {
    vis[x] = 1; doit(x);
    for (auto [v, len] : G[x]) if (!vis[v]) {
        count(v, x);
        int rt = getCent(v, x, cnt[x]);
        solve(rt);
    }
}

void run_case() {
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        cin >> h[i];
        G[i].clear();
        vis[i] = 0;
    }
    ans = 0;
    for (int i = 1;i < n; ++i) {
        int x,y; ll w;
        cin >> x >> y >> w;
        G[x].push_back({y, w});
        G[y].push_back({x, w});
    }
    count(1, 0);
    int rt = getCent(1, 0, cnt[1]);
    solve(rt);
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) run_case();
    return 0;
}

DSU on Tree

cpp

vector<int> G[maxn];
int num[maxn], son[maxn], hs;

void calc(int x, int fa, int op) { // op = -1: reverse
    // do sth.
    for (auto v : G[x]) if (v != fa && v != hs) {
        calc(v, x, op);
    }
}

void dsut(int x, int fa, int kp) {
    for (auto v : G[x]) if (v != fa && v != son[x]) {
        dsut(v, x, 0);
    }
    if (son[x]) dsut(son[x], x, 1), vis[son[x]] = true, hs = son[x];
    calc(x, fa, 1);
    ans[x] = res; // count answer
    hs = 0;
    if (!kp) calc(x, fa, -1); // init variables
}
void dfs1(int x, int fa) {
    num[x] = 1;
    for (auto v : G[x]) if (v != fa) {
        dfs1(v, x); num[x] += num[v];
        if (!son[x] || num[v] > num[son[x]]) son[x] = v;
    }
}

Path via LCA

cpp

void dsut(int x, int fa, int kp) {
    for (auto v : G[x]) if (v != fa && v != son[x]) dsut(v, x, 0);
    if (son[x]) dsut(son[x], x, 1), hs = son[x];
    lca = x;

    res = 0;
    for (auto v : G[x]) if (v != fa && v != hs && !vis[v]) {
        getres(v, x); // calculate answer
        calc(v, x); // add sum of children
    }
    if (cnt[sum[x] ^ A[lca]]) res = 1; // add lca sum
    cnt[sum[x]]++;

    if (res) ans++, vis[x] = 1;
    hs = 0;
    if (!kp || vis[x]) cnt.clear();
}

字符串

KMP

cpp

struct KMP {
    vector<int> f;
    string t; 

    KMP(string &t) : t(t), f(sz(t)+1) {
        for (int i = 1;i < sz(t); ++i) {
            int j = f[i];
            while (j && t[i] != t[j]) j = f[j];
            f[i+1] = t[i] == t[j] ? j+1 : 0;
        }
    }
    
    vector<int> match(string s) {
        vector<int> ans;
        for (int i = 0, j = 0;i < sz(s); ++i) {
            while (j && s[i] != t[j]) j = f[j];
            if (s[i] == t[j]) j++;
            if (j == sz(t)) ans.push_back(i+1-sz(t));
        }
        return ans;
    }
};

KMP Automaton

cpp

struct KMP {
  string t;
  vector<int> f;
  int s = 0; // #matches
  KMP(string &t) : t(t), f(sz(t)+1) {
    for (int i = 1, j = f[i];i < sz(t); ++i) {
      while (j && t[i] != t[j]) j = f[j];
      j = f[i+1] = t[i] == t[j] ? j + 1 : 0;
    }
  } 
  void add(char c) {
    while (s && c != t[s]) s = f[s];
    if (c == t[s]) s++;
  }
};

Z function

cpp

struct KMPZ {
    vector<int> z;
    KMPZ(string s) : z(sz(s)) {
        int l = 0;
        for (int i = 1;i < sz(s); ++i) {
            if (l+z[l] > i) z[i] = min(z[i-l], l+z[l]-i);
            while (i+z[i] < sz(s) && s[z[i]] == s[i+z[i]]) z[i]++;
            if (i+z[i] > l+z[l]) l = i;
        }
        z[0] = sz(s);
    }
};

Trie

cpp

struct Trie {
    #define a0 'a' // lowercase
    #define ind (c-a0)

    vector<vector<int>> ch;
    vector<int> cnt;
    int tot;
    Trie(int n) : ch(n+1,vector<int>(26)), cnt(n+1), tot(0) {}
   
    void insert(string s) {
        int u = 0; 
        for (auto c : s) {
            if (!ch[u][ind]) ch[u][ind] = ++tot;
            u = ch[u][ind];
        }
        cnt[u]++;
    }
    int find(string s) {
        int u = 0;
        for (auto c : s) {
            if (!ch[u][ind]) return -1; // fail
            u = ch[u][ind];
        }
        return cnt[u];
    }
};

Manacher

cpp

struct Manacher {
    vector<int> p; 
    string s = "~|";
    Manacher(string &t) : p(sz(t)*2+2) {
        for (auto c : t) s += c, s += '|';
        for (int i = 1,r = 0, mid = 0;i < sz(s); ++i) {
            if (i <= r) p[i] = min(p[mid*2-i],r-i+1);
            while (s[i-p[i]] == s[i+p[i]]) p[i]++;
            if (p[i]+i > r) r = p[i]+i-1, mid = i;
        }
    }
    int d1(int i) {
        return p[i*2+2]/2;
    }
 
    int d2(int i) {
        return p[i*2+3]/2;
    }
    
};

SAfast

cpp

struct SuffixArray {
    int n,p=0;
    vector<int>bu,rk,sa,id;
    inline void upd(int x,int y,int i){rk[y] = id[x] == id[y] && id[x+i] == id[y+i]?p:++p;}
    SuffixArray(string &s) : n(sz(s)), bu(256),rk(n+2),sa(n+2),id(n+2) {
        for(int i = 1;i <= n;++i) ++bu[s[i-1]];
        for(int i = 1;i < 256;++i) bu[i] += bu[i-1];
        for(int i = n;i;--i) sa[bu[s[i-1]]--] = i;
        for(int i = 1;i <= n;++i) rk[sa[i]] = s[sa[i-1]-1] == s[sa[i]-1]?p:++p;
        for(int i = 1;i < n && p < n;i <<= 1){
            bu.assign(p+1,0);
            for(int j = n-i+1;j <= n;++j) id[j-n+i] = j;
            for(int j = 1,k = i;j <= n;++j){++bu[rk[j]];if(sa[j] > i) id[++k] = sa[j]-i;}
            for(int j = 1;j <= p;++j) bu[j] += bu[j-1];
            for(int j = n;j;--j) sa[bu[rk[id[j]]]--] = id[j],id[j] = rk[j];
            p = 0;
            for(int j = 1;j <= n;++j) upd(sa[j-1],sa[j],i);
        }
        for(int i = 0;i < n;++i) sa[i] = sa[i+1]-1; //indexed with 0
    }
    void getheight(string &s) {
        rk.assign(n,0); height.assign(n,0);
        for (int i = 0;i < n; ++i) rk[sa[i]] = i;
        for (int i = 0, k = 0; i < n; ++i) {
            if (rk[i] == 0) continue;
            if (k) --k;
            while (s[i + k] == s[sa[rk[i] - 1] + k] && s[i+k] != '#') ++k;
            height[rk[i]] = k;
   		}
        st.assign(n,vector<int>(1+(int)log2(n)));
        for (int i = 0;i < n; ++i) st[i][0] = height[i];
        for (int j = 1;j < sz(st[0]); ++j) 
            for (int i = 0;i+(1<<j)-1 < n; ++i) 
                st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
    }
    int getlcp(int l, int r) {
        if(l == r) return n - sa[l];
        l++; int k = log2(r - l + 1);
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
};

SuffixArray

cpp

struct SA {
    int n, m;
    vector<int> sa, rk, height;
    vector<vector<int>> st;
    SA(string& s) : n(sz(s)), m(max(256, n)), sa(n) {
        vector<int> buc(m), x(n); // counting sort
        for (auto c : s) buc[c]++;
        for (int i = 1;i < m; ++i) buc[i] += buc[i-1];
        for (int i = n-1;i >= 0; --i) sa[--buc[x[i] = s[i]]] = i;
        vector<int> y;
        for (int k = 1; k <= n; k <<= 1) {
            y.clear();
            for (int i = n-k; i < n; ++i) y.push_back(i);
            for (int i = 0;i < n; ++i) if (sa[i] >= k) y.push_back(sa[i]-k);
            
            buc = vector<int>(m);
            for (int i = 0;i < n; ++i) buc[x[y[i]]]++;
            for (int i = 1;i < m; ++i) buc[i] += buc[i-1];
            for (int i = n-1;i >= 0; --i) sa[--buc[x[y[i]]]] = y[i];
    
            for (int i = 0;i < n; ++i) y[i] = x[i];
            int p = 1; x[sa[0]] = 0;
            for (int i = 1;i < n; ++i) 
                x[sa[i]] = (y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]) ? p-1 : p++;
            if (p >= n) break;
        }
    }
    void getheight(string &s) {
        rk.assign(n,0); height.assign(n,0);
        for (int i = 0;i < n; ++i) rk[sa[i]] = i;
        for (int i = 0, k = 0; i < n; ++i) {
            if (rk[i] == 0) continue;
            if (k) --k;
            while (s[i + k] == s[sa[rk[i] - 1] + k] && s[i+k] != '#') ++k;
            height[rk[i]] = k;
        }
        st.assign(n,vector<int>(1+(int)log2(n)));
        for (int i = 0;i < n; ++i) st[i][0] = height[i];
        for (int j = 1;j < sz(st[0]); ++j) 
            for (int i = 0;i+(1<<j)-1 < n; ++i) 
                st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
    }
    int getlcp(int l, int r) {
        if(l == r) return n - sa[l];
        l++; int k = log2(r - l + 1);
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
};

SuffixTree

cpp

struct SuffixTree {
    struct node {
        int l=0, r=0, par=-1, link=-1,isleaf=-1; // [l,r)
        map<char, int> next;
        node(int l=0, int r=0,int par=-1,int isleaf=-1) : l(l),r(r),par(par),isleaf(isleaf) {
            next.clear();
        }
    };
    int e=1,last=1,i=0,tot=1;
    string s="";
    vector<int> J;
    vector<node> t;
    SuffixTree() : J(2),t(2) {}

    inline int getr(int id) { return t[id].isleaf != -1 ? e : t[id].r; }
    inline int getlen(int id) { return getr(id) - t[id].l; }
    void addchar(char c) {
        J.push_back(0); s += c; 
        if (sz(s)==1) {
            t[0].next[s[0]] = 1;
            t[1] = node(0,1,0,0);
            J[1] = 0; tot = 1; e = 1; last = 1;
            return;
        }
        i++;
        int pre = last; 
        for (int j = J[i]+1; j <= i; ++j) { 
            int cur = pre; J[i+1] = j; int g = 0;
            if (t[cur].isleaf == -1 && t[cur].link != -1) { 
                cur = t[cur].link;
            } else {
                if (cur) g = getlen(cur), cur = t[cur].par; 
                if (cur) cur = t[cur].link; 
                if (!cur) g = i-j;
                while (g > 0) g -= getlen(cur = t[cur].next[s[i-g]]);            
            }
            if ((!g && t[cur].next[s[i]]) || (g && s[getr(cur)+g] == s[i])) {
                if (!g) t[pre].link = cur, pre = cur;
                J[i+1] = j-1; break;
            }s
            if (g) {
                int fa = t[cur].par;
                t.push_back(node(t[cur].l,getr(cur)+g,fa)); tot++;
                t[fa].next[s[t[tot].l]] = tot;
                t[tot].next[s[getr(cur)+g]] = cur;
                t[cur].l = getr(cur)+g;
                t[cur].par = tot;
                cur = tot;
            }
            t[pre].link = cur;
            pre = cur;
            t.push_back(node(i,i+1,cur,j)); tot++;
            last = tot;
            t[cur].next[s[i]] = tot; 
        }
        e++;
    }
};

广义后缀自动机

cpp

struct SAM {
    struct Node {
        vector<int> ch;
        int len=0,fa=0; // len=longest,minlen = len[fa]+1
        int leaf=-1; // leaf & endpos
        Node() : ch(26) {}
    };
    vector<Node> t;
    int las = 1,tot = 1,slen=0;
    SAM() : t(2) {} // root=1
    int newnode(int l=-1) { if (tot+1 == sz(t)) t.resize(sz(t)<<1);  t[tot+1].leaf = l; return ++tot;}
    void newstring() { las = 1; } // general
    void addchar(char c) {
        c -= 'a';
        int p = las; 
        if (t[p].ch[c]) { // general
            int x = t[p].ch[c];
            if (t[p].len + 1 == t[x].len) {
                las = x;
                return;
            } else {
                int y = newnode(); t[y].ch = t[x].ch; t[y].fa = t[x].fa;
                t[y].len = t[p].len+1;
                while (p && t[p].ch[c]==x) t[p].ch[c]=y,p=t[p].fa;
                t[x].fa = y;
                las = y;
                return;
            }
        } // general
        las = newnode(slen++); int np = las;
        t[np].len = t[p].len + 1;
        while (p && !t[p].ch[c]) t[p].ch[c] = np, p = t[p].fa;
        if (!p) t[np].fa = 1;
        else {
            int q = t[p].ch[c];
            if (t[p].len + 1 == t[q].len) t[np].fa = q;
            else {
                int nq = newnode(); t[nq].ch = t[q].ch; t[nq].fa = t[q].fa;
                t[nq].len = t[p].len + 1;
                t[q].fa = t[np].fa = nq;
                while (p && t[p].ch[c] == q) t[p].ch[c] = nq, p = t[p].fa;
            }
        }
    }
    vector<vector<int>> G;
    vector<int> cnt;
    inline void solve(){
        G.assign(tot+1,vector<int>());
        cnt.assign(tot+1,0);
        for (int i = 2;i <= tot; ++i) {
            G[t[i].fa].push_back(i);
        }
    }
    ll ans = 0;
    void dfs(int x,int fa) {
        if (t[x].leaf != -1) {
            cnt[x] = 1;
        }
        for (auto v : G[x]) {
            dfs(v, x);
            cnt[x] += cnt[v];
        }
        if (fa && cnt[x] > 1)
            ans = max(ans, 1ll * cnt[x] * t[x].len);
    }

};

网络流/二分图

匈牙利算法

cpp

struct Match {
    // matching in O(|V| * |E|)
    int n, m, cnt;
    vector<vector<int>> G;
    vector<int> matched, vis;
    Match(int n, int m) : n(n), m(m), G(n+1) {}

    void addedge(int x, int y) {
        G[x].push_back(y);
    }

    bool dfs(int x) {
        for (auto v : G[x]) if (!vis[v]) {
            vis[v] = 1;
            if (!matched[v] || dfs(matched[v])) { 
                matched[v] = x; 
                return true;
            }
        }
        return false;
    }

    int calc() {
        cnt = 0;
        matched.assign(m+1, 0);
        for (int i = 1;i <= n; ++i) {
            vis.assign(m+1, 0);
            if (dfs(i)) cnt++;
        }
        return cnt;
    }
};

二分图最大权完美匹配

cpp

struct KM {
    typedef long long T;
    const T oo = 1e18;

    int n;
    vector<vector<T>> G;
    vector<int> matched, pre;
    vector<T> slack, ex, ey;
    vector<bool> vis;
 
    KM(int n) : n(n), G(n+1,vector<T>(n+1, -oo)) {}

    void addedge(int x, int y, T z) { G[x][y] = z; }
    void match(int u) {	
        int x, y = 0, yy = 0; T delta = oo;
        pre.assign(n+1, 0); slack.assign(n+1, oo);
        matched[y] = u;

        while(matched[y] != -1) {	
            x = matched[y]; delta = oo; vis[y] = 1;
            for(int i = 1;i <= n; ++i) if (!vis[i]) {	
                
                if (slack[i] > ex[x] + ey[i] - G[x][i]) {	
                    slack[i] = ex[x] + ey[i] - G[x][i];
                    pre[i] = y;
                }
                if(slack[i] < delta) delta = slack[i], yy = i;
            }

            for(int i = 0;i <= n; ++i) {	
                if(vis[i]) ex[matched[i]] -= delta, ey[i] += delta;
                else slack[i] -= delta;
            }
            y = yy;
        }
        while(y) matched[y] = matched[pre[y]], y=pre[y];
    }

    T calc() {	
        matched.assign(n+1,-1);
        ex.assign(n+1, 0); ey.assign(n+1, 0);
        for(int i = 1;i <= n; ++i) vis.assign(n+1, 0), match(i);
        T res = 0;
        for(int i = 1;i <= n; ++i)
            if(matched[i] != -1) res += G[matched[i]][i];
        return res;
    }

};

Dinic(from Erik)

cpp

struct Dinic {
  struct edge {
    ll j, c, f;
  };
  vector<edge> e;
  vector<vector<int>> adj;
  vector<int> lvl, ptr;
  int n, m = 0;
  Dinic(int n) : n(n+1), adj(n+1), lvl(n+1), ptr(n+1) {}
  int addedge(int i, int j, ll c) {
    e.push_back({j, c, 0});
    e.push_back({i, 0, 0});
    adj[i].push_back(m++);
    adj[j].push_back(m++);
    return sz(e)-2;
  }
  bool bfs(int s, int t) {
    fill(lvl.begin(), lvl.end(), -1);
    lvl[s] = 0;
    queue<int> q; 
    q.push(s);
    for (; !q.empty();) {
      int v = q.front(); q.pop();
      for (int i : adj[v])
        if (e[i].c > e[i].f && lvl[e[i].j] < 0) {
          lvl[e[i].j] = lvl[v] + 1;
          q.push(e[i].j);
        }
    }
    return lvl[t] != -1;
  }
  ll dfs(int v, int t, ll push) {
    if (push == 0 || v == t)
      return push;
    for (; ptr[v] < (int)adj[v].size(); ptr[v]++) {
      int id = adj[v][ptr[v]];
      if (lvl[v] + 1 != lvl[e[id].j] || e[id].c == e[id].f)
        continue;
      ll f = dfs(e[id].j, t, min(push, e[id].c - e[id].f));
      if (f != 0) {
        e[id].f += f;
        e[id ^ 1].f -= f;
        return f;
      }
    }
    return 0;
  }
  ll maxflow(int s, int t) {
    ll ret = 0;
    while (bfs(s, t)) {
      fill(ptr.begin(), ptr.end(), 0);
      while (ll f = dfs(s, t, 1e18))
        ret += f;
    }
    return ret;
  }
};

最小费用流

cpp

typedef long long ll;
const ll inf = LLONG_MAX / 4;

struct min_cost_max_flow {
  typedef __gnu_pbds::priority_queue<pair<ll,int>> prio;
  struct edge {
    ll j, f, c, p, r;
  };
  int n;
  vector<int> p;
  vector<ll> d, pi;
  vector<vector<edge>> e;
  vector<prio::point_iterator> its;
  min_cost_max_flow(int n) : n(n), p(n), d(n), e(n), its(n) {}
  void addEdge(int i, int j, ll c, ll p) {
    e[i].push_back({j, 0, c, p, e[j].size() + (i == j)});
    e[j].push_back({i, 0, 0, -p, e[i].size() - 1});
  }
  void path(int s) {
    swap(d, pi);
    d.assign(n, inf);
    d[s] = 0;
    prio pq; its.assign(n, pq.end());
    its[s] = pq.push({0, s});
    while (!pq.empty()) {
      ll di = pq.top().first;
      int i = pq.top().second;
      pq.pop();
      if (-di != d[i] - pi[i])
        continue;
      for (edge & ed : e[i]) {
        ll v = d[i] + ed.p;
        if (ed.c > ed.f && v < d[ed.j]) {
          d[ed.j] = v; p[ed.j] = ed.r;
          if (its[ed.j] == pq.end())
            its[ed.j] = pq.push({-(d[ed.j] - pi[ed.j]), ed.j});
          else
            pq.modify(its[ed.j], {-(d[ed.j] - pi[ed.j]), ed.j});
        }
      }
    }
  }
  pair<ll, ll> minCostMaxFlow(int s, int t) {
    ll f = 0, c = 0;
    while (path(s), d[t] < inf) {
      ll w = inf;
      for (int i = t; i != s; i = e[i][p[i]].j) {
        edge & ed = e[e[i][p[i]].j][e[i][p[i]].r];
        w = min(w, ed.c - ed.f);
      }
      f += w;
      c += d[t] * w;
      for (int i = t; i != s; i = e[i][p[i]].j) {
        edge & ed = e[e[i][p[i]].j][e[i][p[i]].r];
        e[i][p[i]].f -= w;
        ed.f += w;
      }
    }
    return {f, c};
  }
  // for negative costs, call this function before min cost max flow
  void setPi(int s) {
    d.assign(n, inf);
    d[s] = 0;
    bool c = true;
    for (int i = 0; i < n && c; i++) {
      c = false;
      for (int j = 0; j < n; j++)
        for (edge & ed : e[j])
          if (ed.c > ed.f && d[j] + ed.p < d[ed.j])
            d[ed.j] = d[j] + ed.p, c = true;
    }
    assert(!c);
  }
};

Python

输入

python

calc = 1
nxt = [1, 0]

for _ in range(int(input())):
  n = int(input())
  a = sorted(list(map(int, input().split())))
  while calc <= n:
    for i in range(calc):
      nxt.append(calc - i - 1)
    calc *= 2
  left = []
  for i in range(n + 1):
    if i == 0 or i == n or a[i] != a[i - 1]:
      left.append(i)
    else:
      left.append(left[-1])
  mid = 1
  ans = n + 2
  while mid <= n:
    for len1 in range(n + 1):
      if left[len1] == len1:
        len2 = left[min(n, len1 + mid)] - len1
        len3 = n - len1 - len2
        ans = min(ans, nxt[len1] + (mid - len2) + nxt[len3])
    mid *= 2
  print(ans)

算法模板集合

编译

对拍

测时间

DEBUG

VSCODE 代码片段

计算几何

圆

排序极角

读入优化

编译优化

cin优化

快读快写

多个测试数据

以EOF结尾

以0结尾

给定数据组数

STL

struct

sort

vector

map

set

bitset

pbds

模拟

初始化

蛇形矩阵遍历

二分

离散化去重

离散化去重

离散化

去重（堆在一起）

字符串转换

离散前缀和

数学

向上/向下取整

随机数

取模结构体

取模

快速幂/龟速乘

费尔马小定理求逆元

O(n)求n个逆元

阶乘与阶乘的逆元

求组合数

求大组合数 O(K)

周期计数

扩展欧几里得exgcd

同余方程

欧拉函数(n)

E氏筛法

线性筛/分解质因数

低常数

所有因子

单个质因数分解O(x)

数论分块

素数测试Miller-Rabin

Pollard Rho找一个因子, 分解质因数

扩展中国剩余定理EXCRT

快速傅里叶变换FFT

快速数论变换NTT

线性代数

矩阵快速幂

矩阵求逆(取模)

线性基

高斯消元（老）

动态规划

最长不下降子序列 O(nlogn)

最长公共子序列 O(nlogn)

DAG最长路

树形dp

树形背包（简单版）

树形背包（O(n2)）

状态压缩位运算

数位dp

SOS DP

Convexhull Trick

Changeroot

数据结构

差分数组

求大组合数 $O (K)$

欧拉函数 $\sqrt{(} n)$

单个质因数分解 $O (\sqrt{x})$

最长不下降子序列 $O (n l o g n)$

最长公共子序列 $O (n l o g n)$

树形背包（ $O (n^{2})$ ）