校内互测 [from abclzr] T1 （贪心+单调队列）

题目描述

给你一个长为n 的序列a ，让你找a 中长度恰好为k 的子序列b ，使
得b 的字典序尽可能大。

输入格式

从文件 in red. 中读入数据。
第一行x , y , z 用于生成a 序列：a[1]=x,a[i]=a[i-1]*y%z+1
第二行n ,k
对于所有数据，保证 a[i],x,y,z<=1e9

输出格式

输出到文件 out red. 中。
输出k 行，每行一个正整数，表示b 序列。

样例输入

1 0 1
3 3

样例输出

1
1
1

数据范围

n<=1.5*10^7 k<=10^6

题解

每次贪心的选取最大的
设上一次选取的位置为pos,当前选到第k位。
那么选取的一定是[pos+1,n-k+1]中最大的数，如果有相同的，选取位置靠前的。
每次区间的左右端点一定会向右移动，所以我们维护一个元素单调递减的单调队列，每次选取的时候弹队首元素即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long 
#define N 15000003
using namespace std;
int x,y,z,n,k,a[N],head,tail,q[N];
int main()
{
    freopen("red.in","r",stdin);
    freopen("my.out","w",stdout);
    scanf("%d%d%d",&x,&y,&z);
    scanf("%d%d",&n,&k);
    a[1]=x; 
for (int i=2;i<=n;i++) a[i]=(LL)a[i-1]*y%z+1;
//for (int i=1;i<=n;i++) cout<<a[i]<<" ";
//cout<<endl;
    head=1; 
for (int i=1;i<=n-k+1;i++) {
while (head<=tail&&a[q[tail]]<a[i]) 
         tail--;
q[++tail]=i;
    }
int pos=0; int j=n-k+1;
for (int i=1;i<=k;i++) {
printf("%d\n",a[q[head]]);
pos=q[head]+1;
while (head<=tail&&q[head]<pos) head++;
while (head<=tail&&a[q[tail]]<a[j+i]) tail--;
q[++tail]=i+j;
    }
}