题解 P1886 滑动窗口 /【模板】单调队列

## 前言 - 尽管题目名称是单调队列模板，但这并不能阻止我们用其他的思路。 - 这篇题解简要介绍了一个**线性**的分块做法，它的复杂度不亚于单调队列。 - 同时，这篇文章分析了这种方法的优劣，希望你能学到一些。 ## 题解 滑动窗口的询问操作，有一个特殊的性质：**每个询问的长度相同**，都为 $k$ 。 这个性质告诉我们，任何询问都会恰好包含 $k,2\times k,\cdots ,\lfloor\frac{n}{k}\rfloor \times k$ 这 $\lfloor\frac{n}{k}\rfloor-1$ 个节点中的某个节点。 考虑题目要求的 $\min$ 和 $\max$ 操作。我们发现，它们满足结合律。因此，如果我们能够将一个询问拆成两个区间，使得它们的并为这个询问，那么我们就能通过合并它们来直接求得答案。 于是，我们将上述节点定义为**关键点**。枚举每个关键点，然后分别向左右拓展，计算以它为左/右端点的区间最大值和最小值，直到碰到另外一个关键点或边界。于是， 每个询问都能通过它包含的关键点的信息得出。 以题面的样例 $a=\{1,3,-1,-3,5,3,6,7\},k=3$ 为例，计算滑块的最小值： - 枚举到关键点 $3$ 。 - 分别计算出 $[3,3],[2,3],[1,3]$ 的最小值，以及 $[3,4],[3,5]$ 的最小值。 - 计算出 $[1,3],[2,4]=[2,3]\cup[3,4],[3,5]$ 的最小值分别为 $-1,-3,-3$ 。 - 枚举到关键点 $6$ 。 - 分别计算出 $[6,6],[5,6],[4,6]$ 的最小值，以及 $[6,7],[6,8]$ 的最小值。 - 计算出 $[4,6],[5,7]=[5,6]\cup [6,7],[6,8]$ 的最小值分别为 $-3,3,3$ 。 最大值过程同理。 该算法的复杂度为 $\mathcal O(n)$ ，因为我们从每个关键点向左右拓展的次数为 $4\times k$ ，而一共有 $\lfloor \frac{n}{k}\rfloor$ 个关键点。 ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<r;i++) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } const int MAXN =2e6+3; int n,k,A[MAXN],B[MAXN],C[MAXN],P[MAXN],Q[MAXN]; int main(){ n=qread(),k=qread(); up(0,n,i) A[i]=qread(); for(int i=k-1;i<n;i+=k){ B[i]=C[i]=A[i]; int j=i+1; B[j]=C[j]=A[j]; up(1,k,t) B[i-t]=min(B[i-t+1],A[i-t]); up(1,k,t) C[i-t]=max(C[i-t+1],A[i-t]); up(1,k,t) B[j+t]=min(B[j+t-1],A[j+t]); up(1,k,t) C[j+t]=max(C[j+t-1],A[j+t]); up(j-k,j,t) P[t]=min(B[t],B[t+k-1]),Q[t]=max(C[t],C[t+k-1]); } up(0,n-k+1,i) printf("%d ",P[i]); puts(""); up(0,n-k+1,i) printf("%d ",Q[i]); puts(""); return 0; } ``` ## 分析 - 这种方法和单调队列复杂度相同，码量略少。 - 单调队列还可以处理滑块长度不一定固定的情况。该方法可能会有问题。 - 这种方法能够处理下方问题： > 有一个长度为 $n$ 的整数序列 $a$ 。现在要求求出区间 $[i,i+m-1]$ 的**连乘积**对 $p$ 取模的值。 单调队列难以维护；而求前缀积及其逆元的方法，无法处理逆元不存在的情况。 这种时候，我们就能用上述的分块做法，直接维护每个关键点向左右延伸的前缀/后缀积。