第十一届蓝桥杯校内赛：选节目(线段树解法)
选节目
作者：xcatf
小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。
小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。
小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。
输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。
第二行包含 n 个整数，依次为每个节目的好看值。
输出一行包含 m 个整数，为选出的节目的好看值。
样例输入5 3
3 1 2 5 4
3 5 4
样例说明选择了第1, 4, 5个节目。
评测用例规模与约定
对于 30% 的评测用例，1 <= n <= 20；
对于 60% 的评测用例，1 <= n <= 100；
对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。
存储下标与最大值)
初始查询区间为(1,n-m+1)(ql=1,qr=n-m+1)
查询区间ql根据查询范围移动,qr++
#include
using namespace std;
static const int maxn = 1e5 + 5;
static const int mod = 10000;
typedef long long ll;
int a[maxn];
struct node
{
int id;
int left,right;
int max;
}tr[maxn << 2];
pair buildmax(int left,int right,int now)
{
tr[now].left=left;
tr[now].right=right;
if(left==right)
{
tr[now].id=left;
tr[now].max=a[left];
return make_pair(left,a[left]);
}
int mid=(left+right)>>1;
pair r1=buildmax(left,mid,now*2);
pair r2=buildmax(mid+1,right,now*2+1);
if(r1.second>=r2.second)
{
tr[now].id=r1.first;
tr[now].max=r1.second;
return r1;
}
else
{
tr[now].id=r2.first;
tr[now].max=r2.second;
return r2;
}
}
pair querymax(int left,int right,int now)
{
if(left == tr[now].left && right == tr[now].right)
return make_pair(tr[now].id,tr[now].max);
int mid=(tr[now].left+tr[now].right)>>1;
if(right<=mid)
return querymax(left, right, now <mid)
return querymax(left, right, now << 1 | 1);
else
{
pair r1=querymax(left, mid, now << 1);
pair r2=querymax(mid+1, right, now <= r2.second ? r1 : r2;
}
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
buildmax(1, n, 1);
int ql = 1, qr = n - m + 1;
for(int i = 1; i <= m; ++i){
pairres = querymax(ql, qr, 1);
printf("%d%c", res.second, i == m ? '\n' : ' ');
ql = res.first + 1;
qr++;
}
return 0;
}
作者：xcatf
