//快排
void quick_sort(int &q[], int l, int r){
if(l >= r) return;
int i = l - 1, j = r + 1;
while(i < j)
{
while(q[++ i] < q[r]);
while(q[– j]) > q[r]);
if(i < j) swap(q[i], q[j]);
else break;
}
quick_sort(q, l, i - 1);
quick_sort(q, i, r);
}

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

//归并排序
void mergr_sort(int q[], int l, int r){
if(l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r){
    if(q[i] < q[j]) tmp[k ++] = q[i ++];
    else tmp[k ++] = q[j ++];

while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];

for(i = l, j = 0; i <= r, i ++, j ++) q[i] = tmp[j];
}

}

//整数二分模板
bool check(int x){/…/} 检查x是否满足某种特性

//区间[l, r]被分为[l, mid], [mid + 1, r]时
int bsearch_1(int l, int r){
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid; //check判断mid是否满足性质
else l = mid + 1;
}
return l;
}

//区间被分为[l, mid - 1], [mid, r]时使用：
int bsearch_2(int l, int r){
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}