学习笔记——单调数据结构

题目

定义：一个下标 \(i\) 是序列 \(a\) 的后缀最大值下标当且仅当对于所有的 $i < j \le |a| $ ，都有 \(a_i>a_j\)。其中 \(|a|\) 表示序列 \(a\) 的长度。给出整数 \(n\) 和一个长为 \(n\) 的序列 \(a\)，对于每个 \(1 \le i \le n\) ，输出 \(a_1 \sim a_i\) 所有后缀最大值下标的异或和。

思路

考虑用一个栈来维护当前 \(a_1 \sim a_i\) 所有的后缀最大值下标，容易发现栈中的数单调递增（指栈顶到栈底的下标对应的值单调递增）。当遍历到 \(i\) 时，如果栈顶存放的下标 \(j\) 满足 \(a_j>a_i\)，则因为栈是单调递增的，栈中的其他下标对应的值均大于 \(a_i\)，可以正确维护。如果不满足条件则需要不断弹出栈顶直到满足条件。并将 \(i\) 入栈，栈中的下标即为后缀最大值下标

Code:

vector<int> stk;
int ans=0;
for(int i=1;i<=n;i++){
    while(!stk.empty()&&a[stk.back()]<=a[i]){
        ans^=stk.back();
        stk.pop_back();
    }
    stk.push_back(i);
    cout<<ans<<" ";
}

复杂度

共有 \(n\) 次循环且共执行了 \(n\) 次入栈操作，时间复杂度 \(O(n)\)。

单调栈需要额外空间，空间复杂度 \(O(n)\) 。

题目

将单调栈的问题稍加变化：给出整数 \(n, k\) 和一个长为 \(n\) 的序列 \(a\)，对于每个长度为 \(k\) 的区间，输出该区间内所有后缀最大值下标的数量。

思路

这个问题对比上个问题来说多了一个删除过期元素的功能。可以用 STL 中的 deque 双端队列来维护。每次循环开始时先从队首（front）取出过期元素。再按照单调栈的方法维护

单调队列还可以求区间最小/最大值，将新的下标加入队列中后队首的下标就是最值所在的下标

Code

deque<int> q;
int ans=0;
for(int i=1;i<=n;i++){
    while(!q.empty()&&q.front()<=i-k){
        ans--;
        q.pop_front();
    }
    while(!q.empty()&&a[q.back()]<=a[i]){
        ans--;
        q.pop_back();
    }
    q.push_back(i);
    ans++;
    if(i>=k)cout<<ans<<" ";
}

复杂度

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

P6510 奶牛排队

题意

给定一个长度为 \(n\) 的序列 \(a\)，求出满足区间内 \(a_l\) 最小且 \(a_r\) 最大的区间 \([l,r]\) 的最大长度。（ \(2 \le N \le 10^5\) ）

思路

考虑暴力，枚举右端点 \(r\) ，对每个 \(r\) 求出符合条件的 \(l\) 。时间复杂度 \(O(n^2)\) ，对 \(10^5\) 的数据显然会超时。

因为 \(a_l < a_i\) （ \(l < i \le r\) ），所以 \(l\) 一定是 \(1 \sim r\) 的后缀最小值。又因为 \(l \sim r\) 中 \(a_r\) 最大，即这段区间不能有任何一个数比 \(a_r\) 大。可以二分求出 \(l\) 的值。

用单调栈 \(s1\) 和 \(s2\) 分别维护后缀最大值和最小值，每次循环时在 \(s2\) 上二分找出第一个大于 \(s1.back()\) （即栈顶）的下标，更新答案。时间复杂度 \(O(n \log n)\) 。

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int> s1,s2;
    int ans=0;
    for(int r=1;r<=n;r++){
        while(s1.size()&&a[s1.back()]<=a[r])
            s1.pop_back();
        while(s2.size()&&a[s2.back()]>=a[r])
            s2.pop_back();
        auto l=upper_bound(s2.begin(),s2.end(),s1.back());
        if(l!=s2.end())ans=max(ans,r-*l+1);
        s1.push_back(r);
        s2.push_back(r);
    }
    cout<<ans;
    return 0;
}

P13889 子矩阵

题意

有一个 \(n \times m\) 个整数组成的矩阵，求所有大小为 \(a \times b\) 的子矩阵中最大值与最小值的乘积的和。

思路

考虑暴力做法，先找出每个子矩形，再计算最小值和最大值，统计答案，时间复杂度 \(O(nmab)\) ，显然不能通过本题。

我们可以使用单调队列进一步优化，对于输入的 \(n \times m\) 的矩阵，我们可以把每一行看作一个单独的数列，对其求出它的每个长度为 \(b\) 的子段的区间最大值，易得出这样的最大值有 \(n \times (m-b+1)\) 个，将每行的最大值构成新矩阵 \(mx1\) 的一行，则 \(mx1\) 的大小是 \(n \times (m-b+1)\) 。

对新矩阵，再将它的每一列看作一个单独的数列，求出这一列上每个长度为 \(a\) 的子段的区间最大值，存到另一个矩阵 \(mx2\) 中， \(mx2\) 的大小就是 \((n-a+1) \times (m-b+1)\) 。最小值同理。

经过这一步，我们可以得出两个存储原矩阵的子矩阵最值的矩阵，最后统计答案即可。

Code

#include<bits/stdc++.h>
using namespace std;


int main(){
    int n,m,a,b; cin>>n>>m>>a>>b;
    vector<vector<int>> c(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
        }
    }


    vector<vector<int>> mx1(n+1,vector<int>(m-b+2)),
    mn1(n+1,vector<int>(m-b+2));
    vector<vector<int>> mx2(n-a+2,vector<int>(m-b+2)),
    mn2(n-a+2,vector<int>(m-b+2));


    for(int i=1;i<=n;i++){
        deque<int> q;
        for(int j=1;j<=m;j++){
            while(q.size()&&q.front()<j-b+1)q.pop_front();
            while(q.size()&&c[i][q.back()]<=c[i][j])q.pop_back();
            q.push_back(j);
            if(j>=b)mx1[i][j-b+1]=c[i][q.front()];
        }
    }
    for(int j=1;j<=m-b+1;j++){
        deque<int> q;
        for(int i=1;i<=n;i++){
            while(q.size()&&q.front()<i-a+1)q.pop_front();
            while(q.size()&&mx1[q.back()][j]<=mx1[i][j])q.pop_back();
            q.push_back(i);
            if(i>=a)mx2[i-a+1][j]=mx1[q.front()][j];
        }
    }

    for(int i=1;i<=n;i++){
        deque<int> q;
        for(int j=1;j<=m;j++){
            while(q.size()&&q.front()<j-b+1)q.pop_front();
            while(q.size()&&c[i][q.back()]>=c[i][j])q.pop_back();
            q.push_back(j);
            if(j>=b)mn1[i][j-b+1]=c[i][q.front()];
        }
    }
    for(int j=1;j<=m-b+1;j++){
        deque<int> q;
        for(int i=1;i<=n;i++){
            while(q.size()&&q.front()<i-a+1)q.pop_front();
            while(q.size()&&mn1[q.back()][j]>=mn1[i][j])q.pop_back();
            q.push_back(i);
            if(i>=a)mn2[i-a+1][j]=mn1[q.front()][j];
        }
    }

    long long ans=0;
    long long mod=998244353;
    for(int i=1;i<=n-a+1;i++){
        for(int j=1;j<=m-b+1;j++){
            ans=(ans+(mx2[i][j]*1LL*mn2[i][j]%mod))%mod;
        }
    }
    cout<<ans;
    return 0;
}