洛谷—— P1440 求m区间内的最小值

https://www.luogu.org/problemnew/show/P1440

题目描述

一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。

输入输出格式

输入格式：

第一行两个数n，m。

第二行，n个正整数，为所给定的数列。

输出格式：

n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。

输入输出样例

输入样例#1：复制

6 2
7 8 1 4 3 2

输出样例#1：复制

说明

【数据规模】

m≤n≤2000000

 1 #include <cstdio>
 2 
 3 #define max(a,b) (a>b?a:b)
 4 #define min(a,b) (a<b?a:b)
 5 
 6 inline void read(int &x)
 7 {
 8     x=0; register char ch=getchar();
 9     for(; ch>'9'||ch<'0'; ) ch=getchar();
10     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
11 }
12 const int N(2000005);
13 int n,m,st[N][20],log2[N],t;
14 
15 int Presist()
16 {
17     read(n),read(m);
18     for(int i=1; i<=n; ++i)
19         read(st[i][0]),log2[i]=(1<<t+1==i)?++t:t;
20     for(int j=1; 1<<j<=n; ++j)
21       for(int i=1; i+(1<<j)<=n+1; ++i)
22         st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
23     puts("0");
24     for(int l,r=1,mid; r<n; ++r)
25     {
26         l=max(r-m+1,1); mid=log2[r-l+1];
27         printf("%d
",min(st[l][mid],st[r-(1<<mid)+1][mid]));
28     }
29     return 0;
30 }
31 
32 int Aptal=Presist();
33 int main(int argc,char**argv){;}

80分 ST表

单调队列跑一边

 1 #include <cstdio>
 2 
 3 inline void read(int &x)
 4 {
 5     x=0; register char ch=getchar();
 6     for(; ch>'9'||ch<'0'; ) ch=getchar();
 7     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 8 }
 9 const int N(2000005);
10 int n,m,a[N];
11 int head=1,tail,que[N];
12 
13 int Presist()
14 {
15     read(n),read(m);
16     for(int i=1; i<=n; ++i)
17     {
18         read(a[i]);    printf("%d
",a[que[head]]);
19         for(; head<=tail&&a[que[tail]]>=a[i]; ) tail--;
20         for(que[++tail]=i; head<=tail&&que[head]<=i-m; ) head++;
21     }
22     return 0;
23 }
24 
25 int Aptal=Presist();
26 int main(int argc,char**argv){;}

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。