最后的代码模板

发表于 | 阅读次数:
字数统计: 4,494 字

代码模板。

巨长的代码模板。

图论

图

连通块的划分（图的染色）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int x) {
    color[x] = cnt;
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (color[y]) continue;
        dfs(y);
    }
}
for (int i=1;i<=n;++i) {
    if (!color[i]) {
        cnt++;
        dfs(i);
    }
}

BFS遍历一个树/图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bfs() {
    queue<int> q;
    memset(d, 0, sizeof(d));//如果搜索的是一棵树的话， 那么d数组指的是节点x在树中的深度。如果是一张图的话， d数组指的是x的层次， （从起点1走到x所要经历的最少点数）。
    q.push(1); d[1] = 1;
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}//bfs有两个重要的性质， 1.在访问过所有的第i层节点之后，才会开始访问i+1层节点2.任意时刻，队列里只会出现i层的节点和i+1层的节点，并且所有的第i层节点都在第i+1层节点之前。（简单来说就是满足“两端性”和“单调性”）
//并且dfs的时间复杂度和bfs的时间复杂度是相同的， 都为O(n+e)的时间复杂度，只不过限制两个算法的一个是堆栈大小， 一个是队列的大小

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Dijkstra(int x) {
    priority_queue<pair<ll ll> > q;
    for (int i=1;i<=n;++i)	dis[i] = INF, vis[i] = false;
    dis[x] = 0;
    q.push(make_pair(0, x));
    while(q.size()) {
        int x = q.top().second;	q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i], w = edge[i];
            if (dis[y] > dis[x] + w) {//由于是拿出现在堆中最小的那个点来更新其他的点， 所以写的顺序需要注意
                dis[y] = dis[x] + w;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
}//适用于有向图和无向图中，只适用于边长不为负的图。时间复杂度为O(n+m)log(n));

Floyed

1
2
3
4
5
6
void Floyed() {
    for (int k=1;k<=n;++k) 
        for (int i=1;i<=n;++i) 
            for (int j=1;j<=n;++j) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}//多源最短路，可以有负权边。适用于大部分的情况。但是时间复杂度高达O(n³)。

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Kruskal() {
	for (int i=1;i<=n;++i)	f[i] = i;
    sort(e+1, e+1+m);
    for (int i=1;i<=m;++i) {
        int a = getf(e[i].x), b = getf(e[i].y);
        if (a == b)	continue;
        else {
            ans += e[i].v;
            f[b] = a;
            ++cnt;
        }
        if (cnt == n - 1)	break;
    }
}//这个是求出最小生成树的所有边的权值和， 其实可以可以在计算所有边的权值和的同时从新建一棵最小生成树

并查集

1
2
3
4
5
6
7
8
9
10
11
void init() {
    for (int i=1;i<=n;++i) f[i] = i;
}//使用并查集的初始化
int getf(int x) {
    return (f[x] == x) ? x : f[x] = getf(f[x]);
}//进行路径压缩的并查集
void un(int x, int y) {
    int a = getf(x), b = getf(y);
    if (a == b) return;
    else f[b] = a;
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Topsort() {
    queue<int> q;
    for (int i=1;i<=n;++i) {
        if (du[i] == 0) {
            q.push(i);
        }
    }//找到入度为0的点， 入队
    while(q.size()) {
        int x = q.front(); q.pop();
        a[++tot] = x;
        for (int i=head[x]; i; i=Next[i]) {
            if (--du[ver[i]] == 0) {
                a[++tot] = ver[i];
                q.push(ver[i]);
            }
        }
    }
}//有向图中使用，记清楚！必须是有向图。显然的是，在进行完成拓扑排序之后，图中还留下来的东西就是一些环。即tot != n;
//算法的应用：1.有向图找环（无向图是不能使用拓扑排序的）

二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool find(int x) {
    for (int i=1;i<=m;++i) {  
        if (Link[x][i] && !used[i]) {
            used[i] = true;
            if (girl[i] == 0 || find(girl[i])) {
                girl[i] = x;
             	return true;   
            }
        }
    }
    return false;
}//其实就是在寻找增广路的过程
int Maxmatch() {
    int ans = 0;
    for (int i=1;i<=n;++i) {
        memset(used, 0, sizeof(used));
        if (find(i)) ++ans;
    }
    return ans;
}//匈牙利算法如果使用邻接矩阵的话可以在O(n³)的时间内找到一个二分图的最大匹配数。空间复杂度是一个邻接矩阵(n²)。

Tarjan求强联通分量

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
void Tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    Stack[++top] = x;
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (!dfn[ver[i]]) {
            Tarjan(ver[i]);
            low[x] = min(low[x], low[ver[i]]);
        }else if (vis[ver[i]]) {
            low[x] = min(low[x], dfn[ver[i]]);
        }
    }
    if (dfn[x] == low[x]) {
		int temp = 0;
		++cnt;//一个新的强联通块
		do{
			temp = Stack[--top];
			color[temp] = cnt;//color里存的是第i个点属于第几个联通块
			vis[temp] = false;
		}while(x != temp);
	}
}
int main() {
    for (int i=1;i<=n;++i) {
        if (!vis[i])
            tarjan(i);//因为这张图可能不连通
    }
}

缩点

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
void Tarjan() {
    dfn[x] = low[x] = ++tim;
    Stack[++top] = x;
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (!dfn[ver[i]]) {
            Tarjan(ver[i]);
            low[x] = min(low[x], low[ver[i]]);
        }else if (vis[ver[i]]) {
            low[x] = min(low[x], dfn[ver[i]]);
        }
    }
    if (low[x] == dfn[x]) {
        int temp;
        ++cnt;
        do {
            temp = Stack[top--];
            color[temp] = cnt;
            vis[y] = false;
        }while(x != temp)
    }
}
/*现在说一说缩点，其实就是拿着邻接表，和强连通分量们来建一张新的图，在新的图中，点就是原来的强连通分量，边的具体操作有点复杂，现在具体说一说，大致意思就是：既然点都变成了强连通分量，那么边就应该在他们当中去连接不是吗?那什么和什么连？似乎可以看到，连接同一个强连通分量里的点是没有任何意义的，所以就好办了，跑一遍原邻接表，如果一条边（u，v,w）的u和v不在同一个强连通分量中，那么就在新图中连这条边，就这样点就缩好了。听起来也许有些玄幻，但是它就真真切切的完成了？！*/
for (int i=1;i<=m;++i) {//一共m条边
    if (color[a[i]] != color[b[i]]) {//如果两条边的两个端点不在一个强连通分量里面， 那么我们在这两个点之间连一条边
        adde(color[a[i]], color[b[i]], z[i]);
    }
}
//等于用剩下的信息建了一张新图

树

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
26
27
28
29
30
void bfs() {
    t = log(n)/log(2);
    queue<int> q;
    d[s] = 1;
    q.push(s);
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x]　＋ 1;
            f[y][0] = x;
            for (int j=1;j<=t;++j) {
                f[y][j] = f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i=t;i>=0;--i) {
        if (d[f[y][i]] >= d[x])	y = f[y][i];
    }
    if (x == y) return x;
    for (int i=t;i>=0;--i) {
        if (f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}
Tarjan算法离线求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
26
void init() {
    int a, b;
    for (int i=1;i<n;++i) {
        a = Read(); b = Read();
        adde(a, b); 
        adde(b, a);
    }//一棵树n-1条边
    for (int i=1;i<=k;++i) {
        a = Read(); b = Read();
        qadde(a, b);
        qadde(b, a);
    }//k个询问
    for (int i=1;i<=n;++i) f[i] = i;
}
void Tarjan(int x) {
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (vis[ver[i]])  continue;
        tarjan(ver[i]);
        f[ver[i]] = x;
    }
    for (int i=qhead[x]; i; i=Next[i]) {
        if (vis[qver[i]]) 
            ans[edge[i]] = getf(qver[i]);
    }
}

树的直径

1
2
3
4
5
6
7
8
9
10
11
12
void dp(int x) {
    vis[x] = true;
    for(int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);//d数组的含义是从x节点出发走向x的子树， 所能到达的最远距离。
        //那么树上最长链的距离即为从x到x的子节点yi的距离加上x到x的子节点yj的距离加上d[yi]再加上d[yj]即可
        //d[x]中存的是从x走向他的前i个子节点最长的路径， 再加上当前的点到它子节点最长的路径即可得到x所在链的长度， 取一下max即为最长链的长度， 即为树的直径
    }
}

树的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int x) {//树的重心的定义就是将该点删去之后所形成的最大的子树最小的那个点
    vis[x] = true;
    size[x] = 1;//子树x的大小
    int max_part = 0;//删掉子树x后分成的最大子树的大小
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y])	continue;
        dfs(y);
        size[x] += size[y];//从子节点向上更新
        max_part = max(maxn_part, size[y]);//x的子节点中最大的那个节点的size
    }
    	max_part = max(maxn_part, n - size[x]);//现在max_part中储存的是该节点删去之后形成的若干个子树最大的那个的大小 
    //n - max_part里存的是x向上连接他的父亲节点的那一棵子树的大小。
    if (max_part < ans) {
        ans = max_part;
        pos = x;
    }
}

树的各点子树的大小

1
2
3
4
5
6
7
8
9
10
void dfs(int x) {
    vis[x] = true;
    size[x] = 1;
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y);
        size[x] += size[y];
    }
}

树的各点的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int x) {
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i) {
        int y = ver[i];
        if (vis[y])	continue;
        d[y] = d[x] + 1;
        dfs(y);
    }
}
void bfs(int x) {
    memset(d, 0, sizeof(d));
	queue<int> q;
    d[x] = 1; q.push(x);
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x];i;i=Next[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}

数论

Gcd 和 Lcm

1
2
3
4
5
6
int gcd(int a, int b) {
    return b? gcd(b, a%b) : a;
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

线性筛求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll prime[maxn]， size = 0;
bool vis[maxn]; 
inline void init() {
    memset(vis, true, sizeof(vis));
    memset(prime, 0, sizeof(vis));
    vis[1] = false;
    for (int i=2;i<=n;++i) {
        if (vis[i]) prime[++size] = i;
        for (int j=1;j<=size&&i*prime[j]<=n;++j) {
            vis[i*prime[j]] = false;
            if (i % prime[j] == 0)	break;
        }
    }
}//时间复杂度O(n)

EXGCD

1
2
3
4
5
6
7
8
9
10
11
12
void Exgcd(int a, int b, int& d, int& x, int& y) {
    if (!b) {
        x = 1;
        y = 0;
        d = a;
        return;
    }
    int x1, y1;
    Exgcd(b, a%b, d, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;  
}

求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//如果p是素数那么可以使用小费马定理
int inv(int a, int p) {
	return = power(a, p - 2, p);    
}
//如果p不是素数那么可以使用EXgcd
int inv(int a, int p) {
	int x, y, d;
    exgcd(a, p, d, x, y);
    return d == 1 ? (a + p)% p : -1;
}//如果返回-1则这个数没有逆元
//如果要求出n以内所有在膜p情况下的的逆元,可以线性递推
void inv(int n, int p) {
    inv[1] = 1;
    for (int i=2;i<=n;++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
}

快速幂

1
2
3
4
5
6
7
8
int power(int a, int b, int p) {
    int res = 1 % p;
    for(; b; b >>= 1) {
        if (b & 1) res = (long long)res * a % p;
        a =(long long)a * a % p;
    }
    return res;
}

龟速乘

1
2
3
4
5
6
7
8
ll Mul(ll a, ll b, ll p) {
    ll res = 0;
    for(; b; b >>= 1) {
        if (b & 1) res = (res % p + a % p) % p;
        a = (a << 1) % p;
    }
    return res;
}//可以防止两数相乘过大炸掉long long

组合数学

1
2
3
4
5
6
7
8
9
10
void init() {
    memset(c, 0, sizeof(c));
    c[1][0] = c[1][1] = 1;
    for (int i=2;i<=maxn;++i) {
        c[i][0] = c[i][i] = 1;
        for (int j=1;j<i;++j) {
            c[i][j] =(c[i-1][j] % mod + c[i-1][j-1] % mod)% mod;
        }
    }
}

矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Mat {
    a[maxn][maxn];
}A, e;
Mat Mul(Mat x, Mat y) {
    Mat c;
    for (int i=1;i<=n;++i)
    for (int j=1;j<=n;++j)
        c.a[i][j] = 0;
   	for (int k=1;k<=n;++k)
	for (int i=1;i<=n;++i)	
	for (int j=1;j<=n;++j)
        c.a[i][j] = c.a[i][j] % mod + (x.a[i][k] * y.a[k][j] % mod) % mod;
    return c;
}
Mat power(Mat x, int p) {
    Mat ans = e;
    for (; b; b>>=1) {
        if (b & 1) ans = Mul(ans, a);
        a = Mul(a, a);
    }
    return ans;
}

数据结构

链表

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
inline void init() {
    a[1].pre = 0;
    a[1].next = -1;
    a[0].next = 1;
    a[0].pre = -1;
}
inline void insert(int x, int k, int p) {
    if (p == 1) {
        a[x].pre = k;
        a[x].next = a[k].next;
        a[a[k].next].pre = x;
        a[k].pre = x;
    }else {
        k = a[k].pre;
        a[x].pre = k;
        a[x].next = a[k].next;
        a[a[k].next].pre = x;
        a[k].next = x;
    }
    return;
}//在k的前或者后面插入一个值为x的点
//p == 1 时表示在k的后面插入了x
//p == 0 时表示在k的前面插入了x
inline void del(int x) {
    if (a[x].pre != -1) {
        a[a[x].pre].next = a[x].next;
        a[a[x].next].pre = a[x].pre;
        a[x].pre = -1;
    }
}
//一个数的pre为-1表示这个点已经被删除
for (int i=a[0].next;i!=-1;i=a[i].next) {
    //一个链表的遍历
}

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//STL
queue<int> q;

q.push(x);
q.pop();
int x = q.front();
int size = q.size();
bool is_empty = q.empty();

//手写一个队列
inline void init(){
    head = 0; tail = 0;
	memset(q, 0, sizeof(q));
}
inline void push(int x) {q[++tail] = x;}
inline void pop()		{head++;}
inline int  front()		{return q[tail];}
inline bool empty()		{return head >= tail;}
inline int 	size()		{return tail - head;}

优先队列

1
2
3
4
5
6
7
8
9
10
//STL
priority_queue<int> q;
priority_queue<int, vector<int>, greater<int> > q;

q.push(x);
q.pop();
int x = q.top();
int size = q.size();
bool is_empty = q.empty();
//不会手写

栈

1
2
3
4
5
stack<int> s;
s.push(x);
s.pop();
int x = s.top();
bool is_empty = s.empty();

单调队列

1
2


单调栈

1
2


Hash表

1
2
3
4
5
6
7
unsigned long long h(char s[]) {
    int len = strlen(s);
    unsigned long long ans = 0;
    for (int i=0;i<len;++i) 
		ans += ans * 131 + (unsigned long long)(s[i] - 'a' + 1);
	return ans;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void prekmp() {
    m = strlen(b + 1);
    Next[1] = 0;
    for (int i=2,j=0;i<=m;++i) {
        while(j && b[i] != b[j + 1])j = Next[j];
        if (b[i] == b[j + 1]) ++j;
        Next[i] = j;
    }
}
void kmp() {
    n = strlen(a + 1);
    for (int i=1,j=0;i<=n;++i) {
        while(j && a[i] != b[j + 1])j = Next[j];
        if (a[i] == b[j + 1]) ++j;
        if (j == m) {
            ++ans;
            printf("%d\n", i - m + 1);
            j = Next[j];
        }
    }
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void add(int x, int v) {
    for (; x <= n; x += x & (-x))	c[x] += v;
}
inline int ask(int x) {
    int res = 0;
    for (; x; x -= x & (-x))	res += c[x];
    return x;
}
inline void init() {
    for (int i=1;i<=n;++i)	add(i, a[i]);
}
inline int sum(int x, int y) {
    return ask(y) - ask(x - 1);
}
add(x, v);//单点修改x加上v
int sum = sum(a, b)//区间求和， 从a到b的区间
//区间修改，区间求和
inline void change(int l, int r, ll d) {
	    
}

线段树

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
struct Segment {
    int l, r;
    ll dat, add;
    #define l(x)	tree[x].l
    #define r(x)	tree[x].r
    #define dat(x)	tree[x].dat
    #define add(x)	tree[x].add
}tree[maxn << 2];
int a[maxn];

inline void update(int p) {
    dat(p) = dat(p<<1) + dat(p<<1|1);
}
void build(int p, int l, int r) {
    l(p) = l; r(p) = r;
    if (l == r) {dat(p) = a[i];return;}
    int mid = (l + r) >> 1;
    build(p<<1,	l, mid);
    build(p<<1|1,mid+1, r);
    update(p);
}
void spread(int p) {
    if (add(p)) {
        dat(p<<1) += add(p) * (r(p<<1) - l(p<<1) + 1);
        dat(p<<1|1) += add(p) * (r(p<<1|1) - l(p<<1|1) + 1);
        add(p<<1) += add(p);
        add(p<<1|1) += add(p);
        add(p) = 0;
    }
}
void change(int p, int l, int r, int d) {
    if (l <= l(p) && r >= r(p)) {
        dat(p) += (long long)d * (r(p) - l(p) + 1);
        add(p) += d;
        return;
    }
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    if (l <= mid)	change(p<<1, l, r, d);
    if (r > mid)	change(p<<1|1, l, r, d);
    update(p);
}
long long ask(int p, int l, int r) {
    if (l <= l(p) && r >= r(p))	return dat(p);
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    long long res = 0;
    if (l <= mid)	res += ask(p<<1, l, r);
    if (r > mid)	res += ask(p<<1|1, l, r);
    return res;
}

分块

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
void build() {
    block = sqrt(n);
    num = n / block;  if (n % block) num++;
    for (int i=1;i<=num;++i)
        l[i] = (i - 1) * block + 1, r[i] = i * block;
    r[num] = n;
    for (int i=1;i<=n;++i) {
        a[i] = Read();
        belong[i] = (i - 1) / block + 1;
        sum[belong[i]] += a[i];
    }
}
void add(int x, int y, int d) {
    for (int i=x;i<=min(x, r[belong[x]]);++i) 
        a[i] += d, sum[belong[i]] += d;
    if (belong[x] != belong[y]) {
        for (int i=l[belong[y]];i<=y;++i)
            a[i] += d, sum[belong[i]] += d;
    }
    for (int i=belong[x]+1;i<=belong[y]-1;++i)
        sum[i] += block * d, tag[i] +=d;
}
int ask(int x, int y) {
    ll ans = 0;
    for (int i=x;i<=min(x, r[belong[x]]);++i) 
        ans += tag[belong[i]] + a[i];
    if (belong[x] != belong[y]) {
        for (int i=l[belong[y]];i<=y;++i)
            ans += tag[belong[i]] + a[i];
    }
    for (int i=belong[x]+1;i<=belong[y]-1;++i)
        ans += sum[i];
    return ans;
}

搜索

Dfs

1
2
3
4
5
6
7
8
void dfs(int x) {
    if (x > n) {
        ...
        return;
    }
    ...
	dfs(x + 1);
}

Bfs

1
2
3
4
5
6
7
8
9
void bfs(int x) {
    queue<int> q;
    q.push(x);
    while(q.size()) {
        int x = q.front();
        ...
        q.push(...);
    }
}

迭代加深

1
2


其他

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//求小于等于x最大的那一个
inline bool check(int x) {
    if (...) return true;
    else return false;
}
int work() {
    int l = 0; r = max_n;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))	l = mid;
        else r = mid - 1;
    }
    return l;
}
//求大于等于x的最小的那一个
int work() {
    int l = 0; r = max_n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}