快排模板

void quick_sort(int q[], int l, int r) 
{
    if ( l >= r ) return;
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while ( i < j )
    {
        while ( x > q[++ i] );
        while ( x < q[-- j] );
        if ( i < j ) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

归并模板

const int t[N];

void merge_sort(int l, int r)
{
    if ( l >= r ) return;
    int m = l + r >> 1;
    merge_sort(l, m);
    merge_sort(m + 1, r);
    int i = l, j = m + 1, k = 0;
    while ( i <= m && j <= r )
        if ( q[i] <= q[j] ) t[k ++] = q[i ++];
        else t[k ++] = q[j ++];
    while ( i <= m ) t[k ++] = q[i ++];
    while ( j <= r ) t[k ++] = q[j ++];
    for ( int i = l, j = 0; i <= r; i ++, j ++  ) q[i] = t[j];
}

二分模板1(找到第一次大于等于x的下标)

// 例如：int q[] = {1, 2, 3, 3, 3, 4};
// binary_search()后，应该返回：2
int binary_search(int q[], int l, int r, int x)
{
    while (l < r) 
    {
        int mid = l + r >> 1;
        if (q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

二分模板1(找到第最后一次小于等于x的下标)

// 例如：int q[] = {1, 2, 3, 3, 3, 4};
// binary_search()后，应该返回：4
int binary_search(int q[], int l, int r, int x)
{
    while (l < r) 
    {
        int mid = (l + r + 1) >> 1;
        if (q[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}