题目链接：https://ac.nowcoder.com/acm/contest/5667/F
这道题我们队之前没用过单调队列，这道题用二维线段树其实有点杀鸡用宰牛刀的感觉。并且由于数据量的原因导致二位线段树不用树套树会tle，用树套树会mle。
预备知识：
单调队列：
单调队列要从一个比较经典的问题说起来
图片说明
这道题的题意是用一个固定长度的窗口，在一个数列上从左向右移动，找到每个窗口覆盖区域里的最大值。
暴力比较：O(N^2)
复杂度高的原因是在求解f(i)的时候，重复比较了它前面的m-1个数。
单调队列优化：O(N)
基本思想：
同样维护队首元素作为答案，去掉多余元素。(维护单调性)
图片说明
队列中的每一个元素用一个二元组(id,val)表示，每次从队尾入队，删除队尾的无用元素，保证编号递增，值递减。
图片说明

复杂度分析：
由于每个元素只会进队和被删掉(出队)一次，故复杂度为O(N)
代码实现：
数据结构：双端队列deque

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        if(nums.empty() || k==0)
            return res;

        deque<int> que;

        //先处理前k个元素，此时不需要输出
        for(int i=0;i<k;++i){
            //如果队尾元素不比新元素大，就将队尾元素弹出
            while(!que.empty() && nums[que.back()]<=nums[i])
                que.pop_back();
            que.push_back(i);
        }
        //队首元素就是此时的最大值
        res.push_back(nums[que.front()]);

        //处理后面的元素，每次for循环都会输出一次
        for(int i=k;i<nums.size();++i){
            while(!que.empty() && nums[que.back()]<=nums[i])
                que.pop_back();
            que.push_back(i);

            //如果队首元素出了窗口的范围，则弹出
            if(!que.empty() && que.front()<i-k+1)
                que.pop_front();
            res.push_back(nums[que.front()]);
        }

        return res;
}

学习完单调队列回来再看这道题是不是就很简单啦 ^_^
解题思路：
对每一行都求一遍maxSlidingWindow，并把结果保存在res数组中。总共有n行，每行是O(m)
然后对res的每一列求一遍maxSlidingWindow，因为每个window中的k个数分别是各k行的k列的最大值，即求得的就是kk个数的最大值，总共有m列，每列是O(n)
最后的代码复杂度是O(nm)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int lcm[5010][5010];
int res[5010][5010], cnt;
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
int main()
{
    int n, m, k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            lcm[i][j] = i*j/gcd(i,j);
        }
    }

    deque<int> que;

    for(int i = 1; i <= n; i++)
    {
        cnt = 0; // res
        que.clear();
        for(int j = 1; j <= k; j++) {
            while(!que.empty() && lcm[i][que.back()]<=lcm[i][j])
                que.pop_back();
            que.push_back(j);
        }
        res[i][++cnt] = lcm[i][que.front()];
        for(int j = k+1; j <= m; j++) {
            while(!que.empty() && lcm[i][que.back()]<=lcm[i][j])
                que.pop_back();
            que.push_back(j);
            if(!que.empty() && que.front()<j-k+1)
                que.pop_front();
            res[i][++cnt] = lcm[i][que.front()];
        }
    }
    ll result =  0;
    for(int j = 1; j <= cnt; j++)
    {
        que.clear();
        for(int i = 1; i <= k; i++) {
            while(!que.empty() && res[que.back()][j]<=res[i][j])
                que.pop_back();
            que.push_back(i);
        }
        result += res[que.front()][j];
        for(int i = k+1; i <= n; i++) {
            while(!que.empty() && res[que.back()][j]<=res[i][j])
                que.pop_back();
            que.push_back(i);
            if(!que.empty() && que.front()<i-k+1)
                que.pop_front();
            result += res[que.front()][j];
        }
    }
    printf("%lld\n",result);
}