算法模板集合

[toc]

编译

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

对拍

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')

测时间

#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 代码片段

{
	// 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;"
		]
	}
}

计算几何

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);
}

圆

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); }

排序极角

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;
});

读入优化

编译优化

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

cin优化

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

快读快写

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结尾

while (cin >> n) {
    
}

以0结尾

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

给定数据组数

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

}

STL

struct

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

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

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

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

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

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

#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;

模拟

初始化

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

蛇形矩阵遍历

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]\)

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

离散化去重

离散化去重

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();

离散化

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;
}

去重（堆在一起）

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++;

字符串转换

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;
}

离散前缀和

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;
}

数学

向上/向下取整

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;
}

随机数

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);
}

取模结构体

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];
}

取模

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

快速幂/龟速乘

#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;
}

特殊余数

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;
}

费尔马小定理求逆元

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个逆元

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

阶乘与阶乘的逆元

// 逆元数组大小开够
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]);
}

求组合数

// 需要逆元数组，费马尔小定理求逆元
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)\)

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\) 的数的个数

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

扩展欧几里得exgcd

解决 \(ax+by=gcd(a,b)\) 定义好d,x,y 最后 d 是gcd , x,y 是解

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); }
}

同余方程

解决 \(ax+by=c\) 的最小正整数解， 若无解返回 false

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;
}

非负情况

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)\)

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氏筛法

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

线性筛/分解质因数

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;
    }
};

低常数

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;
            }
        }
    }
};

所有因子

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)\)

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;
}

数论分块

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

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

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

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

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

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;
}

线性代数

矩阵快速幂

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;

矩阵求逆(取模)

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;
}

线性基

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];
    }
}

高斯消元（老）

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(nlogn)\)

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(nlogn)\)

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最长路

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

// 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];
    }
}

树形背包（简单版）

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)\)）

#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序）

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]);
    }
}

状态压缩位运算

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\) 的个数

__builtin_popcount(x)

数位dp

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);
}

双边界

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

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

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

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}});
    }
}

数据结构

差分数组

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];
    }
};

单调队列求区间最值

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});
}   

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

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

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

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();
    }
};

单栈队列

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);
	}
};

双指针

小的可以那么大的也可以

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();
}

大的可以那么小的也可以

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表

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

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;
    }
};

并查集

普通并查集

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;
    }
};

树状数组

简单版, 单点修改

#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);

结构体版，单点修改

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;
    }
};

结构体版，区间修改

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记录前面可插入的位置，往前面插入即可。

分块

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;
}

逆序对

归并排序：

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;
}

树状数组：

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;
}

线段树

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); 
    }
};

动态开点

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); 
    }
};

扫描线

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;
}

权值线段树

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

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压行

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

template<class data_t=int,class meta_t=int, class lazy_t=meta_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,meta_t mv) : p(fa), siz(1), v(v), mv(mv),sum(mv) {}
        operator meta_t() const { return mv; }

        static meta_t combine(meta_t a,meta_t b) { // change pushup
            return meta_t{}; // pass
        }
        void apply(lazy_t op, node* ls, node* rs) {
            // update mv, sum, lz
            auto [ai, bi] = op;
            v.f += ai * ls->siz + bi;
            v.rf += ai * (siz-1) + bi; 
            if (islazy) {
                lz.first += ai;
                lz.second += bi;
            } else {
                lz = op;
            }
        }
    };
    #define lson t[t[x].c[0]]
    #define rson t[t[x].c[1]]
    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) { // tochange
        if (!t[x].islazy) return;
        if (t[x].c[0]) t[t[x].c[0]].apply(t[x].lz, &t[t[t[x].c[0]].c[0]], &t[t[t[x].c[0]].c[1]]), t[t[x].c[0]].islazy = 1;
        if (t[x].c[1]) t[t[x].c[1]].apply({t[x].lz.first, t[x].lz.second + t[x].lz.first * (t[t[x].c[0]].siz+1)}, &t[t[t[x].c[1]].c[0]], &t[t[t[x].c[1]].c[1]]), 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;
        t[x].v.rf = t[x].v.f;
        if (t[x].c[1]) t[x].sum = node::combine(t[x].sum, t[t[x].c[1]].sum), t[x].v.rf = t[t[x].c[1]].v.rf;
    }
    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);
    }
    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;
    }

    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); }
    node& operator[](int i) { return *kth(i); }

    void push_back(data_t v, meta_t mv) {
        if (!root) {
            root = newnode(0, 1, v, mv);
            return;
        }
        int x = root, p = 0;
        while (x) {
            pushdown(x);
            p = x;
            x = t[x].c[1];
        }
        t[p].c[1] = newnode(p, 1, v, mv);
        splay(t[p].c[1]);
    }

    void push_front(data_t v, meta_t mv) {
        if (!root) {
            root = newnode(0, 1, v, mv);
            return;
        }
        int x = root, p = 0;
        while (x) {
            pushdown(x);
            p = x;
            x = t[x].c[0];
        }
        t[p].c[0] = newnode(p, 0, v, mv);
        splay(t[p].c[0]);
    }

    node* kth(int k) {
        if (k <= 0 || k > size()) return end();
        int x = root;
        while (true) {
            pushdown(x);
            int rank = lson.siz + 1;
            if (rank == k) return &t[splay(x)];

            if (rank > k) x = t[x].c[0];
            else x = t[x].c[1], k -= rank;  
        }
        assert(false);
        return end();
    }

    node* query(int l,int r) {
        // assert(!(l <= 0 || r > size() || l > r)); 
        int pre = kth(l-1) - &t[0];
        int nxt = kth(r+1) - &t[0];
        if (!pre && !nxt) return &t[root];
        if (!pre) return &t[t[nxt].c[0]];
        if (!nxt) return &t[t[pre].c[1]];
        splay(pre, nxt);
        return &t[t[pre].c[1]];
    }

    void update(int l,int r,lazy_t lz) {
        int x = query(l, r) - &t[0];
        t[x].apply(lz, &lson, &rson); t[x].islazy = true;
        pushdown(x); splay(x);
    }

    void insert(int i, data_t v, meta_t mv) {
        // insert after index i
        if (i == 0) push_front(v, mv);
        else if (i == size()) push_back(v, mv);
        else {
            int p1 = kth(i+1) - &t[0];
            int p0 = kth(i) - &t[0];
            splay(p1, p0);
            t[p1].c[0] = newnode(p1, 0, v, mv);
            splay(t[p1].c[0]);
        }
    }

    void erase(int l, int r) {
        auto x = query(l, r) - &t[0];
        int fa = t[x].p;
        if (!fa) {
            root = 0;
            return;
        }
        int k = t[fa].c[1] == x;
        t[fa].c[k] = 0;
        pushup(fa); splay(fa);
    }


};

文艺指针Splay

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;
    }
};

主席树

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

/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

gp_hash_table<int,bool> h;

莫队

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);
        }
    }
};

图论

拓扑排序

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;
    }
};

二分图染色

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;
    }
}

搜简单环

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求负环

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

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短路

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

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

// 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全源最短路

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;
    }
};

最小生成树

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 缩点,割点,桥

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染色

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;
}

基环树

无向图基环树

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\le 50\)

// 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

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)

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

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};
}

直径，重心

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

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});
    }
}

点分治

#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

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

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

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

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

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

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

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

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]);
    }
};

AC Automaton

// Advanced: Build Suffix Tree
// maxn = sum of |s|
int ch[maxn][26]; // next state
int lnk[maxn]; // suffix link
int fin[maxn]; // if fin state
int tot; // init=0
int cnt[maxn];
vector<int> ids[maxn];
vector<int> sG[maxn]; // suffix tree graph
int ans[maxn];

void acbuild(vector<string> &vs) {
    for (int i = 0;i < sz(vs); ++i) {
        int cur = 0;
        for (auto c : vs[i]) { // a is alphabet
            if (!ch[cur][c-'a']) ch[cur][c-'a'] = ++tot;
            cur = ch[cur][c-'a'];
        }
        ids[cur].push_back(i+1);
    }
    queue<int> q;
    for (int i = 0;i < 26; ++i) 
        if (ch[0][i]) q.push(ch[0][i]);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0;i < 26; ++i) {
            int v = ch[u][i];
            if (v) lnk[v] = ch[lnk[u]][i], q.push(v);
            else ch[u][i] = ch[lnk[u]][i];
        }
    }
    for (int i = 1;i <= tot; ++i) {
        sG[lnk[i]].push_back(i);
    }
}

void dfs(int x,int fa) {
    for (auto v : sG[x]) {
        dfs(v, x);
        cnt[x] += cnt[v];
    }
    for (auto id : ids[x]) {
        ans[id] = cnt[x];
    }
}

void query(string &s) {
    int i = 0;
    for (auto c : s) {
        i = ch[i][c-'a'];
        cnt[i]++;
    }
    dfs(0, -1);
}

SuffixArray

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

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;
            }
            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++;
    }
};

广义后缀自动机

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);
    }

};

网络流/二分图

匈牙利算法

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;
    }
};

二分图最大权完美匹配

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)

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;
  }
};

最小费用流

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

输入

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)