29

$1\le n\le100000$
$1\le q\le10000$
$1\le k\le10000$

6 3
1 2 2 3 3 4
3
4
5


3 4
5 5
-1 -1


#include<iostream>
using namespace std;
const int N=100010;
int n,m,q[N];

int main(){
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++){
scanf("%d",&q[i]);
}
while(m--){
int x;
scanf("%d",&x);
int l=0,r=n-1;
//第一个模版，从中往右寻找
while(l<r){
int mid=l+r>>1;
if (q[mid]>=x){
r=mid;
}
else{
l=mid+1;
}
}
if (q[l]!=x){
cout<<"-1 -1"<<endl;
}
else{
cout<<r<<' ';
int l=0,r=n-1;
//第二个模版，从右往左寻找
while(l<r){
int mid=l+r+1>>1;//记得加一
if (q[mid]<=x){
l=mid;
}
else{
r=mid-1;
}
}
cout<<r<<endl;
}
}
return 0;
}


$1\le n \le 10000$

6
2 3 4 5 6 1


5


#include<iostream>
using namespace std;
typedef long long  LL;
const int N=1e+5+10;
int q[N],tem[N];

LL merge_sort(int q[],int l,int r){
if (l >= r){
return 0;
}
int mid=l + r >> 1;
LL num=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]){
tem[k++]=q[i++];
}
else{
//逆序对的数量为第一个区间中剩下的元素个数，也就是i-mid之间的元素个数
num += mid-i+1;
tem[k++]=q[j++];
}
}
while (i<=mid){
tem[k++]=q[i++];
}
while (j<=r){
tem[k++]=q[j++];
}
for (int i=l,k=0;i<=r;i++,k++){
q[i]=tem[k];
}
return num;
}

int main(){
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&q[i]);
}
printf("%lld",merge_sort(q,0,n-1));
return 0;
}


$1\le n \le 10000$

5
3 1 2 4 5


1 2 3 4 5


#include<iostream>
using namespace std;
const int N=100010;
int n, q[N],tmp[N];

//归并排序模版
void merge_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,k=0;i<=r;i++,k++){
q[i] = tmp[j];
}
}

int main(){
scanf("%d", &n);
for (int i = 0; i < n ;i ++){
scanf("%d", &q[i]);
}
merge_sort(q, 0, n - 1);
for (int i = 0;i < n;i ++){
printf("%d ", q[i]);
}
return 0;
}


$1\le n\le100000$
$1\le k\le n$

5 3
2 4 1 5 3


3


#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;

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

int main(){
int q[N],n,k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++){
scanf("%d", &q[i]);
}
quick_sort(q,0,n-1);
printf("%d", q[k-1]);


$1\le n \le 10000$

5
3 1 2 4 5


1 2 3 4 5


#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;

int q[N],n;

//快排模版
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)//左指针未与右指针相遇
{
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if (i < j) swap(q[i],q[j]);
}
quick_sort(q, l, j);//递归左边部分
quick_sort(q, j + 1, r);//递归右边部分
}

int main(){
scanf("%d", &n);
for (int i = 0; i < n ;i ++){
scanf("%d", &q[i]);
}
quick_sort(q, 0, n - 1);
for (int i = 0;i < n;i ++){
printf("%d ", q[i]);
}
return 0;
}