好的今天又是摸鱼的一天,就看了一下单调队列的优化。
单调队列的使用满足几个条件:
1.区间的最值询问
2.区间在滑动
单调队列的本质是:
当一个选手比你小,且比你强,那你就没有机会了——Chen_zhe
我们要维护一个单调的队列,满足队列里面的两个值,即元素在原来排列中的位置,还有元素的值,都是单调递增或减的。
这样,每一个元素只会进出队列一次,把时间复杂度降到了O(n)级别
板子题:
https://www.luogu.com.cn/problem/P1886
一样,维护两个单调队列,每次将不在当前区间内的元素出队,然后加入元素,注意要保证队列的单调性质,递增或者递减;
放代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int N=1000005; 6 int a[N],q[N],num[N]; 7 int Fmax[N],Fmin[N]; 8 int i,k,n,head,tail; 9 int Read(){ 10 scanf("%d%d",&n,&k); 11 for(int i=1;i<=n;i++){ 12 scanf("%d",&a[i]); 13 } 14 } 15 void DPmin(){ 16 head=1; 17 tail=0; 18 for(i=1;i<=n;i++){ 19 while(head<=tail&&num[head]<i-k+1){ 20 head++; 21 } 22 while(head<=tail&&q[tail]>=a[i]){ 23 tail--; 24 } 25 tail++; 26 q[tail]=a[i]; 27 num[tail]=i; 28 Fmin[i]=q[head]; 29 } 30 } 31 void DPmax() 32 { 33 head=1; 34 tail=0; 35 for(i=1;i<=n;i++){ 36 while(head<=tail&&num[head]<i-k+1){ 37 head++; 38 } 39 while(head<=tail&&q[tail]<=a[i]){ 40 tail--; 41 } 42 tail++; 43 num[tail]=i; 44 q[tail]=a[i]; 45 Fmax[i]=q[head]; 46 } 47 } 48 int main() 49 { 50 Read(); 51 DPmin(); 52 memset(num,0,sizeof(num)); 53 memset(q,0,sizeof(num)); 54 DPmax(); 55 for(int i=k;i<=n;i++){ 56 printf("%d ",Fmin[i]); 57 } 58 printf("\n"); 59 for(int i=k;i<=n;i++){ 60 printf("%d ",Fmax[i]); 61 } 62 63 64 return 0; 65 }
还有一道板子题;
POJ 洒水装置
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int N=1000005,inf=0x3f3f3f3f; 5 int n,l,a,b,s,e,head,tail,c[N],f[N],q[N]; 6 int main() 7 { 8 scanf("%d%d%d%d",&n,&l,&a,&b); 9 for(int i=1;i<=n;i++){ 10 scanf("%d%d",&s,&e); 11 c[s+1]++; 12 c[e]--; 13 } 14 for(int i=1;i<=l;i++){ 15 c[i]+=c[i-1]; 16 } 17 head=1,tail=0; 18 for(int i=2;i<=l;i+=2){ 19 while(head<=tail&&q[head]<i-2*b){ 20 head++; 21 } 22 if(i-2*a>=0){ 23 while(head<=tail&&f[i-2*a]<=f[q[tail]]){ 24 tail--; 25 } 26 tail++; 27 q[tail]=i-2*a; 28 } 29 if(c[i]){ 30 f[i]=inf; 31 }else{ 32 if(head<=tail){ 33 if(f[q[head]]!=inf){ 34 f[i]=f[q[head]]+1; 35 }else{ 36 f[i]=inf; 37 } 38 }else{ 39 f[i]=inf; 40 } 41 42 } 43 } 44 printf("%d\n",f[l]==inf?-1:f[l]); 45 return 0; 46 }
这道题很奇葩,先用一个查分数组来记录该区间是否被覆盖,再用单调队列来维护一个最小值,如果该点被标记了,那么队里的最小值还是INF,注意从2开始要判断l<2a的情况
我就这么wa了两个小时