在线等，急！！！

题面

题目描述

给定一个长度为 n 的整数数组 a，按下标从小到大的顺序，提取 k 个元素，组成一个新的数列。

再定义潜力子数列，即两个数列按下标从第一位开始比较，第一次出现不同的数字时，较小数字的那个数列的潜力更大。

请你帮忙找出这个最大潜力的子数列。

输入

第一行，整数 n 和 k。

第二行，n 个整数 ai。

输出

k 个整数，为最具潜力的子序列，每个两个整数之间用空格隔开。

样例输入 复制

4 2 3 5 2 6

样例输出 复制

2 6

数据范围：

对于 30% 的数据，1 <= n <= 1000 。

对于 70% 的数据，1 <= n <= 10000。

对于 100% 的数据，1 <= n <=100000。

0 <= ai <= 109 。

1 <= k <= n 。

8.3 pts:

#include<bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define key first
#define value second
using namespace std;
int n,m,num[100005],tree[400005];
void build(int pl,int pr,int p){
	if (pl==pr){ tree[p]=num[pl]; return; }
	int mid=(pl+pr)>>1;
	build(pl,mid,ls(p));
	build(mid+1,pr,rs(p));
	tree[p]=max(tree[ls(p)],tree[rs(p)]);
}
pair<int /*key*/,int /*value*/>
query(int pl,int pr,int p,int l,int r){
	if (l<=pl && pr<=r) return pair<int,int>(pl,tree[p]);
	int mid=(pl+pr)>>1;
	pair<int,int> s(0x7fffffff,0x7fffffff);
	if (l<=mid){
		pair<int,int> pt=query(pl,mid,ls(p),l,r);
		if (s.value>pt.value || (s.value==pt.value && s.key>pt.key))
			s.key=pt.key,s.value=pt.value;
	}
	if (r>mid){
		pair<int,int> pt=query(mid+1,pr,rs(p),l,r);
		if (s.value>pt.value || (s.value==pt.value && s.key>pt.key))
			s.key=pt.key,s.value=pt.value;
	}
	return s;
}
signed main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&num[i]);
	build(1,n,1);
	for (int i=1,startx=1,endx=n-m+1;i<=m;i++,endx++){
		pair<int,int> pr=query(1,n,1,startx,endx);
		startx=pr.key;
		printf("%d ",pr.value);
	}
	return 0;
}

16.7 pts:

#include<bits/stdc++.h>
using namespace std;
int f[1000001],q[1000001];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>f[i];
	}
	for(int i=n-k+1;i<=n;i++){
		cout<<f[i]<<' ';
	}
	return 0;
}

25 pts:

#include<bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define key first
#define value second
using namespace std;
int n,m,num[100005],tree[400005];
void build(int pl,int pr,int p){
	if (pl==pr){ tree[p]=num[pl]; return; }
	int mid=(pl+pr)>>1;
	build(pl,mid,ls(p));
	build(mid+1,pr,rs(p));
	tree[p]=min(tree[ls(p)],tree[rs(p)]);
}
pair<int /*key*/,int /*value*/>
query(int pl,int pr,int p,int l,int r){
	if (l<=pl && pr<=r) return pair<int,int>(pl,tree[p]);
	int mid=(pl+pr)>>1;
	pair<int,int> s(0x7fffffff,0x7fffffff);
	if (l<=mid){
		pair<int,int> pt=query(pl,mid,ls(p),l,r);
		if (s.value>pt.value || (s.value==pt.value && s.key>pt.key))
			s.key=pt.key,s.value=pt.value;
	}
	if (r>mid){
		pair<int,int> pt=query(mid+1,pr,rs(p),l,r);
		if (s.value>pt.value || (s.value==pt.value && s.key>pt.key))
			s.key=pt.key,s.value=pt.value;
	}
	return s;
}
signed main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&num[i]);
	build(1,n,1);
	for (int i=1,startx=1,endx=n-m+1;i<=m;i++,endx++){
		pair<int,int> pr=query(1,n,1,startx,endx);
		startx=pr.key+1;
		printf("%d ",pr.value);
	}
	return 0;
}

对于最后一个随机生成的数据

输入：

5 2
5 1 14 13 7

输出：

1 1

输入：

16 11
12 12 8 10 7 3 11 3 13 14 10 0 2 9 4 6

输出：

3 3 3 3 13 10 0 2 9 4 6

在线等，急！！！