首先声明！！！

  • 1、内容为本人常使用的算法竞赛模板；
  • 2、如有使用注明出处；
  • 3、如有改进地方欢迎批评指正；

* 常用竞赛模板

计算几何（常规）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
namespace Geometry
{
    const double pi = acos(-1);
    const double eps = 1e-8;
    // 点与向量
    struct Point
    {
        double x, y;
        Point(double x = 0, double y = 0) : x(x), y(y) {}
        bool operator==(const Point a) const
        {
            return (fabs(x - a.x) <= eps && fabs(y - a.y) <= eps);
        }
    };

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

    int sign(double x)
    { // 符号函数
        if (fabs(x) < eps)
            return 0;
        if (x < 0)
            return -1;
        return 1;
    }
    int cmp(double x, double y)
    { // 比较函数
        if (fabs(x - y) < eps)
            return 0;
        if (x < y)
            return -1;
        return 1;
    }

    double dot(Point a, Point b)
    { // 向量点积
        return a.x * b.x + a.y * b.y;
    }

    double cross(Point a, Point b)
    { // 向量叉积
        return a.x * b.y - b.x * a.y;
    }

    double get_length(Point a)
    { // 求向量模长
        return sqrt(dot(a, a));
    }

    double get_angle(Point a, Point b)
    { // 求A->B的有向角
        return acos(dot(a, b) / get_length(a) / get_length(b));
    }

    double area(Point a, Point b, Point c)
    { // A为顶点，向量AB与向量AC的叉积，即三角形ABC的面积的2倍（有向）
        return cross(b - a, c - a);
    }

    Point rotate(Point a, double angle)
    { // 将向量A顺时针旋转angle度
        return Point(a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle));
    }

    Point get_line_intersection(Point p, Vector v, Point q, Vector w)
    { // 两直线的交点
        // 使用前提，直线必须有交点
        // cross(v, w) == 0则两直线平行或者重合
        Vector u = p - q;
        double t = cross(w, u) / cross(v, w);
        return p + v * t;
    }

    double distance_to_line(Point p, Point a, Point b)
    { // 点到直线的距离，直线为AB所在直线
        Vector v1 = b - a, v2 = p - a;
        return fabs(cross(v1, v2) / get_length(v1));
    }

    double distance_to_segment(Point p, Point a, Point b)
    { // 点到线段的距离，线段为线段AB
        if (a == b)
            return get_length(p - a);

        Vector v1 = b - a, v2 = p - a, v3 = p - b;
        if (sign(dot(v1, v2)) < 0)
            return get_length(v2);
        if (sign(dot(v1, v3)) > 0)
            return get_length(v3);
        return distance_to_line(p, a, b);
    }

    Point get_line_projection(Point p, Point a, Point b)
    { // 点在直线上的投影，直线为AB所在直线
        Vector v = b - a;
        return a + v * (dot(v, p - a) / dot(v, v));
    }

    bool on_segment(Point p, Point a, Point b)
    { // 点是否在线段上
        return sign(cross(p - a, p - b)) == 0 && sign(dot(p - a, p - b)) <= 0;
    }

    bool segment_intersection(Point a1, Point a2, Point b1, Point b2)
    { // 判断两个线段是否相交
        double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
        double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
        return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
    }
    // 多边形
    double polygon_area(Point p[], int n)
    { // 求多边形面积
        double s = 0;
        for (int i = 1; i + 1 < n; i++)
            s += cross(p[i] - p[0], p[i + 1] - p[i]);
        return s / 2;
    }
}
using namespace Geometry;

计算几何（极角排序）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
typedef double db;
const db EPS=1e-9,Pi=acos(-1);
  
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
  
inline int cmp(db a, db b){ return sign(a-b); }
  
struct P {
	db x, y;
	P() {}
	P(db _x, db _y) : x(_x), y(_y) {}
	P operator+(P p) { return {x + p.x, y + p.y}; }
	P operator-(P p) { return {x - p.x, y - p.y}; }
	P operator*(db d) { return {x * d, y * d}; }
	P operator/(db d) { return {x / d, y / d}; }

	bool operator<(P p) const { 
		int c = cmp(x, p.x);
		if (c) return c == -1;
		return cmp(y, p.y) == -1;
	}

	bool operator==(P o) const{
		return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
	}

	db dot(P p) { return x * p.x + y * p.y; }
	db det(P p) { return x * p.y - y * p.x; }
	 
	db distTo(P p) { return (*this-p).abs(); }
	db alpha() { return atan2(y, x); }
	void read() { cin>>x>>y; }
	void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
	db abs() { return sqrt(abs2());}
	db abs2() { return x * x + y * y; }
	P rot90() { return P(-y,x);}
	P unit() { return *this/abs(); }
	int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
	P rot(db an){ return {x*cos(an) - y*sin(an),x*sin(an) + y*cos(an)}; }
}l[N],r[N];

#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
 
// 直线 p1p2, q1q2 是否恰有一个交点
bool chkLL(P p1, P p2, P q1, P q2) {
	db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
	return sign(a1+a2) != 0;
}

// 求直线 p1p2, q1q2 的交点
P isLL(P p1, P p2, P q1, P q2) {
	db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
	return (p1 * a2 + p2 * a1) / (a1 + a2);
}

// 判断区间 [l1, r1], [l2, r2] 是否相交
bool intersect(db l1,db r1,db l2,db r2){
	if (l1>r1) swap(l1,r1); 
	if (l2>r2) swap(l2,r2); 
	return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}

// 线段 p1p2, q1q2 相交
bool isSS(P p1, P p2, P q1, P q2){
	return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) && 
	crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
			* crossOp(q1,q2,p2) <= 0;
}

// 线段 p1p2, q1q2 严格相交  
bool isSS_strict(P p1, P p2, P q1, P q2){
	return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
			* crossOp(q1,q2,p2) < 0;
}

// m 在 a 和 b 之间
bool isMiddle(db a, db m, db b) {
	return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}

bool isMiddle(P a, P m, P b) {
	return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}

// 点 p 在线段 p1p2 上
bool onSeg(P p1, P p2, P q){
	return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
// q1q2 和 p1p2 的交点 在 p1p2 上？

// 点 p 严格在 p1p2 上
bool onSeg_strict(P p1, P p2, P q){
	return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}

// 求 q 到 直线p1p2 的投影（垂足） ⚠️ : p1 != p2
P proj(P p1, P p2, P q) {
	P dir = p2 - p1;
	return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}

// 求 q 以 直线p1p2 为轴的反射
P reflect(P p1, P p2, P q){
	return proj(p1,p2,q) * 2 - q;
}

// 求 q 到 线段p1p2 的最小距离
db nearest(P p1, P p2, P q){
	if (p1 == p2) return p1.distTo(q);
	P h = proj(p1,p2,q);
	if(isMiddle(p1,h,p2))
		return q.distTo(h);
	return min(p1.distTo(q),p2.distTo(q));
}

// 求 线段p1p2 与 线段q1q2 的距离
db disSS(P p1, P p2, P q1, P q2){
	if(isSS(p1,p2,q1,q2)) return 0;
	return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}

//求三角形面积
db get_s(P a,P b,P c){
	return cross(a,b,c)/2;
}

// 极角排序1
// sort(p, p + n, [&](P a, P b) {
	// int qa = a.quad(), qb = b.quad();
	// if (qa != qb) return qa < qb;
	// else return sign(a.det(b)) > 0;
// });


// 极角排序2
struct P{
    int x, y;
}p[N];

int cross1(P a, P b){
    return a.x * b.y - a.y * b.x;
}

bool up(P a){
    return a.y > 0 || (a.y == 0 && a.x >= 0);
}

sort(p, p + n , [&](P a, P b){
    if (up(a) != up(b)) return up(a) > up(b);
    return cross1(a, b) > 0;
});

向量叉积：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//定义点结构体
struct Point{
    double x,y;
    double angle;
    bool operator < (const point &t){
        return angle<t.angle;
    }
}p[N];

//求叉积
double cross(Point a,Point b,Point c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

//判定线线的位置关系
bool check(Point a,Point b,Point c,Point d){
    return cross(a,b,c)*cross(a,b,d)<=0;
}

//求两直线的交点
Point getNode(Point a,Point u,Point b,Point v)
{
    double t=(a-b)*v/(v*u);
    return a+u*t;
}

//求三角形面积
double get_s(Point a,Point b,Point c){
    return cross(a,b,c)/2;
}

//极角排序（atan2函数）
bool atan2cmp(Point a,Point b)
{
    if(a.angle==b.angle) return a.x<b.x;
    else return a.angle<a.angle;
}

//极角排序（叉积）
bool crosscmp(Point a,Point b)
{
    double f=cross(p[pos],a,b);
    if(f==0) return a.x-p[pos].x<b.x-p[pos].x;
    else if(f>0) return true;
    else return false;
}

凸包 + 旋转卡壳：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
struct P{
    int x,y;
}p[N],s[N];

//求叉积
int cross(P a,P b,P c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

//求两点距离
int dis(P a,P b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

//比较排序
bool cmp(P a,P b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

//求凸包的Andrew算法
void Andrew()
{
    sort(p+1,p+n+1,cmp);
	
    //求上凸包
    int top=0;
    for(int i=1;i<=n;i++){
        while(top>1&&cross(s[top-1],s[top],p[i])<=0) top--
        s[++top]=p[i];
    }
	
    //求下凸包
    int t=top;
    for(int i=n-1;i>=1;i--){
        while(top>t&&cross(s[top-1],s[top],p[i])<=0) top--;
        s[++top]=p[i];
    }
	
    n=top-1;
}

//旋转卡壳
int rotating_calipers()
{
    int res=0;
    for(int i=1,j=2;i<=n;i++){
        while(cross(s[i],s[i+1],s[j])<cross(s[i],s[i+1],s[j+1])) j=j%n+1;
        res=max({res,dis(s[i],s[j]),dis(s[i+1],s[j])});
    }
    return res;
}

自适应辛普森积分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
double eps=1e-6;
double l,r;

//积分函数
double f(double x){
    return sqrt(x*x*x);
}

//辛普森公式
double simpson(double l,double r){
    return (f(l)+f(r)+4*f((l+r)/2))*(r-l)/6;
}

//自适应
double asr(double a,double b,double ans)
{
    auto m=(l+r)/2,a=simpson(l,m),b=simpson(m,r);
    if(fabs(a+b-ans)<eps) return ans;
    return asr(l,m,a)+asr(m,r,b);
}

组合数（常规）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//快速幂逆元求组合数
int fact[N], infact[N];


int qmi(int a,int b)
{
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

//组合
int C(int a,int b)
{
    if(a<b) return 0;
    return fact[a]*infact[a-b]%mod*infact[b]%mod;
}

//排列
int A(int a,int b)
{
    if(a<b) return 0;
    return fact[a]*infact[a-b]%mod;
}

//圆排列
int Q(int a,int b){
    return fact[a]*infact[a-b]%mod*qmi(m,mod-2)%mod;
}

//错位排列
int D(int n)
{
    f[1]=0,f[2]=1;
    for(int i=3;i<=n;i++) f[i]=(i-1)*(f[i-1]+f[i-2])%mod;
    return f[n];
}

//预处理
fact[0]=infact[0]=1;
for(int i=1;i<N;i++){
    fact[i]=fact[i-1]*i%mod;
    infact[i]=infact[i-1]*qmi(i,mod-2)%mod;
}

组合数（优化）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using i64 = int64_t;
constexpr i64 mod = 1e9+7;
i64 fpow(i64 x, i64 r)
{
    i64 result = 1;
    while (r)
    {
        if (r & 1)result = result * x % mod;
        r >>= 1;
        x = x * x % mod;
    }
    return result;
}
namespace binom {
    i64 fac[N], ifac[N];
    int __ = []
    {
        fac[0] = 1;
        for (int i = 1; i <= N - 5; i++)
            fac[i] = fac[i - 1] * i % mod;
        ifac[N - 5] = fpow(fac[N - 5], mod - 2);
        for (int i = N - 5; i; i--)
            ifac[i - 1] = ifac[i] * i % mod;
        return 0;
    }();

    inline i64 C(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
    }

    inline i64 A(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[n - m] % mod;
    }
}
using namespace binom;

卡特兰数 C(2n,n)-C(2n,n-1) ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//分解质因数求组合数（可适用于mod非质数）
int primes[N],cnt;
bool st[N];

//筛质数
void init(int n)
{
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

//快速幂
int qmi(int a,int k)
{
    int res=1;
    while(k){
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

//分解质因数
int get(int n,int p)
{
    int s=0;
    for(int j=n;j;j/=p) s+=j/p;
    return s;
}

//分解质因数的方式求组合数
int C(int a,int b)
{
    int res=1;
    for(int i=0;i<cnt;i++){
        int p=primes[i];
        int s=get(a,p)-get(b,p)-get(a-b,p);
        res=res*qmi(p,s)%mod;
    }
    return res;
}


void slove()
{
    cin>>n>>mod;
    cout<<(C(2*n,n)-C(2*n,n+1)+mod)%mod<<'\n';
}

欧拉、莫比乌斯函数 + 整数分块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int primes[N],cnt;
int mobius[N],s[N];
bool st[N];

//线性筛求欧拉函数
void oula(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0){
                phi[i*primes[j]]=phi[i]*primes[j];
                break;
            }
            phi[i*primes[j]]=phi[i]*(primes[j]-1);
        }
    }
}

//线性筛求莫比乌斯函数
void init(int n)
{
    mobius[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            mobius[i]=-1;
        }
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0){
                mobius[primes[j]*i]=0;
                break;
            }
            mobius[primes[j]*i]=mobius[i]*-1;
        }
    }
    for(int i=1;i<=n;i++) s[i]=s[i-1]+mobius[i];
}

//除数分块
void slove()
{
    int a,b,d;
    cin>>a>>b>>d;
    a/=d,b/=d;

    int res=0,n=min(a,b);
    for(int l=1,r;l<=n;l=r+1){
        r=min(n,min(a/(a/l),b/(b/l)));
        res+=(s[r]-s[l-1])*(a/l)*(b/l);
    }

    cout<<res<<'\n';
}

矩阵快速幂：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//矩阵运算
void mul(int a[][N],int b[][N],int c[][N])
{
    int t[N][N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                t[i][j]=(t[i][j]+a[i][k]*b[k][j])%m;
				
    memcpy(c,t,sizeof t);
}


void slove()
{
    cin>>n>>m;
	
    //构造系数矩阵
    int f1[N][N]={1,1,1};
    int a[N][N]={
         {0,1,0},
         {1,1,1},
         {0,0,1}
    };
	
    //快速幂
    int k=n-1;
    while(k){
        if(k%2) mul(f1,a,f1);
        mul(a,a,a);
        k>>=1;
    }
	
    cout<<f1[2]<<'\n';
}

记忆化搜索求期望：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
vector<PII> c[N];
int d[N],a[N];
double f[N];
int T,n,m,k;


double dfs(int u)
{
    if(f[u]>0) return f[u];
    if(u==0) return f[u]=0;

    f[u]=0;
    for(auto p:c[u]){
        int i=p.x,j=p.y;
        f[u]+=(dfs(i)+j)*1.0/d[u];
    }

    return f[u];
}


void slove()
{
    cin>>n>>m;

    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        c[u].push_back({v,w});
        d[u]++;
    }

    printf("%.2lf\n",dfs(1));
}

扩展欧几里得（exgcd）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//扩展欧几里得
int exgcd(int a,int b,int &x,int &y)
{
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

    //求解不定方程ax+my==b;
    int x,y;
    int d=exgcd(a,m,x,y);
    //求出ax+my==gcd(a,m),判断gcd(a,m)|b?
    if(b%d==0) cout<<x*b/d%m<<'\n';
    //求解乘法逆元：
    cout<<(x%m+m)%m<<'\n';

扩展欧拉定理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//求欧拉函数
int get_phi(int m)
{
    int res=m;
    for(int i=2;i*i<=m;i++){
        if(m%i==0){
            res=res/i*(i-1);
            while(m%i==0) m/=i;
        }
    }
    if(m>1) res=res*/m*(m-1);
    return res;
}

//降幂
int depow(int phi)
{
    int b=0;
    bool flag=false;
    for(int i=0;s[i];i++){
        b=b*10+(s[i]-'0');
        if(b>=phi) flag=true,b%=phi;
    }
    if(flag) b+=phi;
    return b;
}

容斥原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N=20;
int n,m,primes[N];

//位运算求容斥原理，复杂度为 O(2^m)
int calc()
{
    int res=0;
    for(int i=1;i<1<<m;i++){ 
        int t=1,sign=-1;
        for(int j=0;j<m;j++){
            if(i&1<<j){
                if(t*primes[j]>n) t=0,break;
                t*=primes[j];
                sign=-sign;
            }
        }
        if(t) res+=n/t*sign;
    }
    return res;
}

sg 函数：

1
2
3
4
5
6
7
8
9
10
11
int sg(int x)
{
    if(f[x]!=-1) return f[x];

    set<int> s;
    for(auto i:c[x]) s.insert(sg(i));

    for(int i=0;;i++)
        if(!s.count(i))
            return f[x]=i;
}

整数三分：

1
2
3
4
5
6
7
8
int l=0,r=2e9;
while(l<r){
    int t=(r-l)/3;
    int mid1=l+t;
    int mid2=r-t;
    if(check(mid1)>check(mid2)) l=mid1;
    else r=mid2;
}

小数三分：

1
2
3
4
5
6
7
8
double l=1,r=2e9;
while(r-l>eps){
    double t=(r-l)/3;
    double mid1=l+t;
    double mid2=r-t;
    if(check(mid1)>check(mid2)) l=mid1;
    else r=mid2;
}

LCA（最近公共祖先）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void dfs(int u,int father)
{
    dep[u]=dep[father]+1;
    fa[u][0]=father;
    for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	
    for(auto v:c[u]){
        if(v!=father){ 
            dfs(v,u);
        }
    }
}


int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return v;
	
    for(int i=19;i>=0;i--) 
        if(fa[u][i]!=fa[v][i]) 
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

ST表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int f[N][logN + 1], Logn[N + 1];

void pre() {  // 准备工作，初始化
	Logn[1] = 0;
  	Logn[2] = 1;
	for (int i = 3; i < MAXN; i++) {
		Logn[i] = Logn[i / 2] + 1;
	}
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> f[i][0];
	pre();
	for (int j = 1; j <= logN; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);  // ST表具体实现
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		int s = Logn[y - x + 1];
		cout << max(f[x][s], f[y - (1 << s) + 1][s]) << '\n';
	}
	return 0;
}