您当前位置：首页 > php开源 > php教程 > 单调栈/单调队列/RMQ

单调栈/单调队列/RMQ

来源：程序员人生发布时间：2016-06-07 08:18:28 阅读次数：2230次

在上上周的交友大会中，队长大人提到了st算法，然后仔细的发愣了1个星期，因而就开始做队长的专题了， 6天后的我总算在此专题做题数目和队长1样了。。明早没课，准备通宵把这几天的零散的记忆整理1下。

HDU 3530 Subsequence

1开始想为什么不能m和k1起放到while语句里进行处理
nowmax和nowmin保存了i之前的最大和最小值，假定此时已出现不满足k和m的序列（A）了（比k大or比m小or both），然后我们往后找，发现了1个比序列（A）的min更小的值（me），此时nowmax - nowmin就会上升，便可能会出现满足k和m的序列。要是出现了1个比（A）max更大的值（me），此时m上升，同理。

要是我们把m和k放在1起，就会在找到（me）之前就把序列给kill了。

然后，从上面的推理中可以看出k是硬道理，而m存在可能性，所以代码就是这样

#include <cstdio>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
const int MAXN = 1000010;
int a[MAXN];
deque<int>nowmax;
deque<int>nowmin;
int main()
{
    int n , m , k;
    while(~scanf("%d%d%d" , &n , &m ,&k))
    {
        int nowme = 0;
        int ans = 0;
        nowmax.clear();
        nowmin.clear();
        for(int i = 0; i < n ; ++ i)
        {
            scanf("%d" , &a[i]);
            while(!nowmax.empty() && a[nowmax.back()] < a[i])//保护当前最大的
            {
                nowmax.pop_back();
            }
            while(!nowmin.empty() && a[nowmin.back()] > a[i])//保护当前最小的
            {
                nowmin.pop_back();
            }
            nowmin.push_back(i);
            nowmax.push_back(i);
            while(!nowmax.empty() && !nowmin.empty() && a[nowmax.front()] - a[nowmin.front()] > k)//去除不符合k的
            {
                if(nowmax.front() < nowmin.front())//此时我的位置应当是在nowmax和nowmin中最远的1个
                {
                    nowme = nowmax.front() + 1;
                    nowmax.pop_front();
                }
                else
                {
                    nowme = nowmin.front() + 1;
                    nowmin.pop_front();
                }
            }//出来以后如果nowmax或nowmin为空，说明当前区间没有1个符合条件的，如果是由于发现了符合条件k，那末k就判断其是不是符合条件m
            if(!nowmax.empty() && !nowmin.empty() && a[nowmax.front()] - a[nowmin.front()] >= m)//如果符合m的话
            {
                ans = max(ans , i - nowme + 1);
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

HDU 3706 Second My Problem First
这道题就是问区间的最大值，这里之间用单调队列摹拟了，要是先处理出所有的ai%b然后st跑1遍，感觉会爆炸。。

#include <cstdio>
#include <iostream>
#include <deque>
#include <algorithm>
#include <cmath>
using namespace std;
struct mymin
{
    int x;
    int v;
    mymin(int a , int b)
    {
        x = a;
        v = b;
    }
};
deque<mymin>nowmin;
int main()
{
    int n , a , b;
    while(~scanf("%d%d%d" , &n , &a , &b))
    {
        int t = a % b;//由于a是要用来判断距离的，所以不能让a变化
        nowmin.clear();
        int test = 1;
        int ans = 1;
        for(int i = 1; i <= n ; ++ i)
        {
            test = (long long)test * t % b;
            while(!nowmin.empty() && nowmin.front().x < i - a)
            {
                nowmin.pop_front();
            }
            while(!nowmin.empty() && nowmin.back().v >= test)
            {
                nowmin.pop_back();
            }
            nowmin.push_back(mymin(i , test));
            ans = (long long)ans * nowmin.front().v % b;
        }
        printf("%d\n", ans);
    }
    return 0;
}

hdu 4122 Alice’s mooncake shop
简单的用单调队列摹拟1下，算个日期就行了。。但是这道题要是hour的数量级再大1点，估计就gg了。。

#include <cstdio>
#include <deque>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int ding[1000010];
int p[1000010];
void finddate(string month , int day ,int year , int  hour , int r)
{
    int finmonth;
    if(month == "Jan")
        finmonth = 1;
    else if(month == "Feb")
        finmonth = 2;
    else if(month == "Mar")
        finmonth = 3;
    else if(month == "Apr")
        finmonth = 4;
    else if(month == "May")
        finmonth = 5;
    else if(month == "Jun")
        finmonth = 6;
    else if(month == "Jul")
        finmonth = 7;
    else if(month == "Aug")
        finmonth = 8;
    else if(month == "Sep")
        finmonth = 9;
    else if(month == "Oct")
        finmonth =10;
    else if(month == "Nov")
        finmonth = 11;
    else
        finmonth = 12;
    int finhour = (day - 1) * 24 + hour + 1;
    for(int i = 2000 ; i < year ; ++ i)
    {
        if(i % 400 == 0 || (i % 4 == 0 && i % 100 != 0))
        {
            finhour += 366 * 24;
        }
        else
        {
            finhour += 365 * 24;
        }
    }
    for(int i = 1 ; i < finmonth ; ++ i)
    {
        if(i == 1 || i == 3 || i == 5 || i ==7 || i == 8 || i == 10 || i == 12)
        {
            finhour += 31 * 24;
        }
        else if(i != 2)
        {
            finhour += 30 *24;
        }
        else
        {
            if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
            {
                finhour += 29 * 24;
            }
            else
            {
                finhour += 28 * 24;
            }
        }
    }
    ding[finhour] += r;
}
struct mine
{
    int x;
    int v;
    mine(int a , int b)
    {
        x = a;
        v = b;
    }
};
deque<mine>mymin;
int main()
{
    int n , m;
    while(~scanf("%d%d" , &n , &m))
    {
        if(n == 0 && m == 0)
            break;
        memset(ding, 0 , sizeof(ding));
        while(n --)
        {
            string month;
            int day , year , h , r;
            cin>>month;
            scanf("%d%d%d%d" , &day , &year , &h , &r);
            finddate(month , day , year , h , r);
        }
        int t , s;
        scanf("%d%d" , &t , &s);
        long long ans = 0;
        mymin.clear();
        for(int i = 1; i <= m ; ++ i)
        {
            scanf("%d", &p[i]);
            while(!mymin.empty() && mymin.front().x < i - t)
            {
                mymin.pop_front();
            }
            int test = p[i] - i * s;
            while(!mymin.empty() && mymin.back().v >= test)
            {
                mymin.pop_back();
            }
            mymin.push_back(mine(i , test));
            if(ding[i])
            {
                ans += ding[i] * (mymin.front().v + s * i);
            }
        }
        printf("%I64d\n" ,ans);
    }
    return 0;
}

poj 1821 Fence
彻彻底底的3个半天。。这道题。。
觉得是本专题目前做到过的最难的题目了。。

#include <cstdio>
#include <iostream>
#include <deque>
#include <cstring>
#include <string>
using namespace std;
struct myworks
{
    int l;
    int p;
    int s;
}work[110];
int dp[100010];//前n面墙的最大金钱
struct maxer
{
    int x;
    int v;
    maxer(int a , int b)
    {
        x = a;
        v = b;
    }
};
int main()
{
    int  n , k;
    while(~scanf("%d%d" , &n , &k))
    {
        for(int i = 1; i <= k ; ++ i)
        {
            scanf("%d%d%d" , &work[i].l , &work[i].p , &work[i].s);
        }
        memset(dp , 0 ,sizeof(dp));
        deque<maxer>nowmax[110];//用来表示，每个工人他的刷墙出发点
        for(int i = 0; i <= k ; ++ i)
        {
            nowmax[i].clear();
        }
        for(int i = 1; i <= n ; ++ i)
        {
            for(int j = 1; j <= k ; ++ j)
            {
                if(work[j].s - work[j].l + 1 <= i && work[j].s + work[j].l - 1 >= i)//选出可以刷这面墙的工人
                {
                    while(!nowmax[j].empty() && nowmax[j].front().x < i - work[j].l + 1)//如果这名工人从1开始刷的墙不能到达当前的墙，若他要刷这面墙，那末，他的出发点就要改变
                    {
                        nowmax[j].pop_front();
                    }
                    if(work[j].s >= i)//工人刷墙出发点的决定，出发点必须是小于等于s。
                    {
                        int test = dp[i - 1] - work[j].p * (i - 1);//工人的钱，由于此时已处理好dp【i - 1】，dp【i】 = dp[i - 1] + work[i].p = dp[i - 1] - work[j].p * (i - 1) + work[j].p * i所以可以当作这名工人从头以work[j].p * (i - 1) 的钱干起，然后干到终点,这1点最关键了，比如，dp【i- a】是工人A干的，要是dp【i】也是工人A干的话，那末nowmax【a】。front（）。v应当是相等的，但是，要是dp【i】时A的test大了，说明中间有更好的工人替换了A。同时也解决了：要是这面墙被工人A刷了，把工人B的出发点给占据了,那末B就刷不了后面的墙，此时要决定是不是值得刷这面墙
                        while(!nowmax[j].empty() && nowmax[j].back().v < test)//要是有更好的工人，那末就选择更好的工人，把A从front到i的之间的记录kill掉
                        {
                            nowmax[j].pop_back();
                        }
                        nowmax[j].push_back(maxer(i , test));//此时的nowmax【j】。front是j工人可以到达i的最大价值
                    }
                    if(!nowmax[j].empty() && nowmax[j].front().x + work[j].l - 1 >= i && work[j].s <= i)//枚举所有符合条件的work，得出最大值
                            dp[i] = max(nowmax[j].front().v + work[j].p * i, dp[i]);
                }
            }
            dp[i] = max(dp[i - 1] , dp[i]);//这里很重要，要是这面墙没人刷的了，那末这面墙我就不刷，要是要实现刷这面墙，就不能让实力派A刷这面墙，要必须让超级无敌大蒟蒻me刷这面墙，固然不让me刷喽。。
        }
        printf("%d\n" , dp[n]);
    }
    return 0;
}

poj 2559 Largest Rectangle in a Histogram
这道题去年寒假用dp做的，现在学了新知识，发现还是dp优秀。

#include <cstdio>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int h[100010];
struct mine
{
    int l;
    int r;
}me[100010];
deque<int>lefts;
deque<int>rights;
int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n ; ++ i)
        {
            scanf("%d" , &h[i]);
        }
        lefts.clear();
        rights.clear();
        for(int i = 1; i <= n ; ++ i)
        {
            while(!lefts.empty() && h[i] <= h[lefts.back()])//从左往右跑，查找每一个h【i】的最大延伸长度，之所以可以用单调队列，是应为这道题，小的h【i】，可以切断前后的联系，只要看准小的h【i】就能够了
            {
                lefts.pop_back();
            }
            if(lefts.empty())
            {
                me[i].l = 1;
            }
            else
            {
                me[i].l = lefts.back() + 1;
            }
            lefts.push_back(i);
        }
        for(int i = n ; i >= 1 ; -- i)
        {
            while(!rights.empty() && h[i] <= h[rights.back()])//同
            {
                rights.pop_back();
            }
            if(rights.empty())
            {
                me[i].r = n;
            }
            else
            {
                me[i].r = rights.back() - 1;
            }
            rights.push_back(i);
        }
        long long ans = 0;//这里wa最不能忍了。。。。
        for(int i = 1 ; i <= n ; ++ i)
        {
            ans = max(ans , (long long)(me[i].r - me[i].l + 1) * h[i]);
        }
        printf("%I64d\n" , ans);
    }
    return 0;
}

这是现在的我写的dp。。和寒假差不多的模样。。
由于，我们知道了，前1个me - 1的最大延伸长度，如果me比它小，自然可以延伸下去，到时候就看可不可以跨出边界了，else 我立刻就知道它的边界了

#include <cstdio>
#include <iostream>
#include <deque>
#include <stack>
using namespace std;
int h[100010];
struct zy
{
    int l;
    int r;
}me[100010];
int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n ; ++ i)
        {
            scanf("%d", &h[i]);
        }
        h[0] = -1;
        h[n + 1] = -1;
        for(int i = 1; i <= n ; ++ i)
        {
            int now =  i - 1;
            while(h[i] <= h[now])
            {
                now = me[now].l;
            }
            me[i].l = now;
        }
        for(int i = n ; i >= 1 ; -- i)
        {
            int now =  i + 1;
            while(h[i] <= h[now])
            {
                now = me[now].r;
            }
            me[i].r = now;
        }
        long long ans = -0x3f3f3f3f;
        for(int i = 1; i <= n ; ++ i)
        {
            ans = max(ans , (long long)h[i] * (me[i].r - me[i].l - 1));
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

codeforces 91B - Queue
很愁闷的读错题了，致使浪费好久好久orz。。
由于问的是最远的，所以保护序列递减就能够了。由于那些比当前判断值大的数字根本没有判断的意义。复杂度计算是nlogn ，那就2分查找1下就行了，，然后计算1下距离就能够了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
vector<int>savemin;
vector<int>num;
int a[100010];
int ans[100010];
int main()
{
    int n;
    scanf("%d" , &n);
    for(int i = 1; i <= n ; ++ i)
    {
        scanf("%d" , &a[i]);
    }
    savemin.push_back(a[n]);
    num.push_back(n);
    ans[n] = -1;
    for(int i = n - 1; i >= 1; -- i)
    {
        if(a[i] <= savemin.back())
        {
            ans[i] = -1;
            savemin.push_back(a[i]);
            num.push_back(i);
        }
        else
        {
            int p = savemin.rend() - lower_bound(savemin.rbegin() , savemin.rend() , a[i]);
            ans[i] = num[p] - i - 1;
        }
    }
    for(int i = 1; i <= n ; ++ i)
    {
        printf("%d" , ans[i]);
        if(i == n)
            printf("\n");
        else
            printf(" ");
    }
    return 0;
}

codeforces 372 C Watching Fireworks is Fun
这道题就是单调队列的简单摹拟了，由于st会爆炸。dp保存上个时期的最优值，最优的来自左侧（包括自己）或右侧（包括自己）因而，就左跑1遍又跑1遍就行了，然后得到了cf上可以跑e9这个惊人的消息。。
但是感觉自己的复杂度实在是太高了，但是怠惰的我不知道怎样优化。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <deque>
#include <cmath>
using namespace std;
long long dp[150010];
long long test[150010];
int main()
{
    long long n , m , d;
    scanf("%I64d%I64d%I64d" , &n , &m , &d);
    long long a , b , t;
    scanf("%I64d%I64d%I64d" , &a , &b , &t);
    for(int i = 1; i <= n ; ++ i)
    {
        dp[i] = b - abs(a - i);
    }
    deque<long long>findmax;
    long long oldt = t;
    for(int i = 1; i < m ; ++ i)
    {
        scanf("%I64d%I64d%I64d" ,&a , &b , &t);
        findmax.clear();
        long long chat= t - oldt;
        oldt = t;
        for(int j = 1; j <= n ; ++ j)
        {
            while(!findmax.empty() && findmax.front() <  j - d * chat)
            {
                findmax.pop_front();
            }
            while(!findmax.empty() && dp[findmax.back()] <= dp[j])
            {
                findmax.pop_back();
            }
            findmax.push_back(j);
            test[j] = dp[findmax.front()];
        }
        findmax.clear();
        for(int j = n; j >= 1 ; -- j)
        {
            while(!findmax.empty() && findmax.front() >  j + d * chat)
            {
                findmax.pop_front();
            }
            while(!findmax.empty() && dp[findmax.back()] <= dp[j])
            {
                findmax.pop_back();
            }
            findmax.push_back(j);
            test[j] = max(dp[findmax.front()] , test[j]);
        }
        for(int j = 1; j <= n ; ++ j)
        {
            dp[j] = test[j] + b - abs(a - j);
        }
    }
    long long ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; ++ i)
    {
        ans = max(ans , dp[i]);
    }
    printf("%I64d\n" ,ans);
    return 0;
}

codeforces 251 A Points on Line
这道题，就是计算组合数，为了避免重复，那就在组合数里面肯定最大的那个数，然后另外两个组合1下。。

#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
deque<int>me;
int main()
{
    int n , k;
    scanf("%d%d" , &n , &k);
    int test;
    scanf("%d", &test);
    me.push_back(test);
    long long ans = 0;
    for(int i = 1; i < n ; ++ i)
    {
        scanf("%d" , &test);
        while(!me.empty() && test - me.front() > k)
        {
            me.pop_front();
        }
        if(me.size() > 1)
            ans += (long long)me.size() * (me.size() - 1) / 2;
        me.push_back(test);
    }
    printf("%I64d\n" , ans);
    return 0;
}

codeforces 253 D. Table with Letters - 2
这道题想了近3小时。。。由于1开始没想到矩阵中套矩阵的适合方法
联系到上面有1道works的题目，瞬间的懂了。。who【id】表示当前这个字母所具有的a，这样就出来了。。

#include <cstdio>
#include <deque>
#include <iostream>
using namespace std;
char way[410][410];
long long a[410][410];
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n , m , key;
    scanf("%d%d%d" , &n , &m, &key);
    for(int i = 1; i <= n ; ++i)
    {
        scanf("%s" , way[i] + 1);
        for(int j = 1; j <= m; ++ j)
        {
            if(way[i][j] == 'a')
            {
                a[i][j] = a[i - 1][j] + 1;
            }
            else
            {
                a[i][j] = a[i - 1][j];
            }
        }
    }
    deque<int>who[26];
    long long ans = 0;
    for(int i = 1; i < n ; ++ i)
    {
        for(int j = i + 1 ; j <= n; ++ j)
        {
            for(int k = 0; k < 26 ; ++ k)
            {
                who[k].clear();
            }
            int sum = 0;
            for(int k = 1 ; k <= m; ++ k)
            {
                sum = sum + a[j][k] - a[i - 1][k];
                if(way[i][k] == way[j][k])
                {
                    int id = way[i][k] - 'a';
                    while(!who[id].empty() && sum - who[id].front() > key)
                    {
                        who[id].pop_front();
                    }
                    ans += who[id].size();
                    who[id].push_back(sum - a[j][k] + a[i - 1][k]);
                }
            }
        }
    }
    printf("%I64d\n" ,ans);
    return 0;
}

poj 2823 Sliding Window
水题。。
但是看discuss有人用1维st。。好利害。。

#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
int a[1000010];
int testmax[1000010];
int testmin[1000010];
deque<int>leftmax,rightmax,leftmin,rightmin;
int main()
{
    int n , k;
    while(~scanf("%d%d" , &n ,&k))
    {
        for(int i = 1; i <= n ; ++ i)
        {
            scanf("%d" ,&a[i]);
        }
        leftmin.clear();
        leftmax.clear();
        for(int i = 1; i <= n; ++ i)
        {
            while(!leftmax.empty() && leftmax.front() <= i - k)
            {
                leftmax.pop_front();
            }
            while(!leftmax.empty() && a[leftmax.back()] <= a[i])
            {
                leftmax.pop_back();
            }
            leftmax.push_back(i);
            testmax[i] = a[leftmax.front()];
        }
        for(int i = 1; i <= n; ++ i)
        {
            while(!leftmin.empty() && leftmin.front() <= i - k)
            {
                leftmin.pop_front();
            }
            while(!leftmin.empty() && a[leftmin.back()] >= a[i])
            {
                leftmin.pop_back();
            }
            leftmin.push_back(i);
            testmin[i] = a[leftmin.front()];
        }
        for(int i = k; i <= n; ++ i)
        {
            printf("%d" , testmin[i]);
            if(i != n )
                printf(" ");
            else
                printf("\n");
        }
        for(int i = k; i <= n; ++ i)
        {
            printf("%d" , testmax[i]);
            if(i != n )
                printf(" ");
            else
                printf("\n");
        }
    }
    return 0;
}

下面是1维st的解释。。感觉就是很1般的dp。。。

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int dpmax[1000010];
int dpmin[1000010];
int main()
{
    int n , k;
    while(~scanf("%d%d" , &n , &k))
    {
        for(int i = 1; i <= n ; ++ i)
        {
            scanf("%d" , &dpmax[i]);
            dpmin[i] = dpmax[i];
        }
        for(int i = 1 ; i <= k / 2 ; i = (i << 1))//代表的是区间的长度 - 1 以为自己还要算进来，区间长度为2的时候（i==1）。为什么是2进制呢？我认为，首先是和位运算联系起来，然后就是。当处理好长度1 的是后，我们只能先处理长度2，得到的比如说max（1,2），max（3,4），现在当处理长度3的时候，就是max（处理好的（1，2），3），但是我们已处理好（3,4），这样在处理max（max（1,2），max（3，4））的时候，就把max（1,2,3）处理好了。如果比如说题目给的长度是3，那末就不可以处理长度是2的时候。。由于把4牵扯进来了。。所以，需要知道的长度就是k/2；
        {
            for(int j = 1 ; j + i <= n ; ++ j)//枚举区间的出发点
            {
                dpmax[j] = max(dpmax[j] , dpmax[j + i]);
                dpmin[j] = min(dpmin[j] , dpmin[j + i]);
            }
        }
        int key = (int)(log(k * 1.0) / log(2.0));
        for(int i = 1; i <= n - k + 1; ++ i)
        {
            printf("%d" , min(dpmin[i] , dpmin[i + k - (1 << key)]));//1个代表左端点的值，1个代表右端点的值。画两个相交的圆就知道了。。，对为什么是key。比如我的区间长度是x，那末此时，front + k / 2 ，back - k / 2 , 这两段比较是最好的，但是为了配合上面的方法，我现在已知的是比k / 2小但是最接近k / 2的 2的x次方，那末就能够数学推导出x <= log(k) / log(2) - 1;,此时，由于log(k) / log(2)会有偏差，因而就在两边+1，这样就能够最近似的表示区间了。。
            if(i == n - k + 1)
                printf("\n");
            else
                printf(" ");
        }
        for(int i = 1; i <= n - k + 1 ; ++ i)
        {
            printf("%d" , max(dpmax[i] , dpmax[i + k - (1 << key)]));
            if(i == n - k + 1)
                printf("\n");
            else
                printf(" ");
        }

    }
    return 0;
}

FZU 1894 志愿者提拔

简单的用单调队列摹拟1下就行了。。

#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
char flag[10];
struct mine
{
    int x;
    int me;
    mine(int a, int b)
    {
        x = a;
        me = b;
    }
};
deque<mine>all;
int main()
{
    int T;
    scanf("%d" , &T);
    while(T --)
    {
        scanf("%s" , flag);
        all.clear();
        int cnt = 0;
        int num = 0;
        while(1)
        {
            scanf("%s" ,flag);
            if(flag[0] == 'E')
                break;
            else if(flag[0] == 'C')
            {
                char name[10];
                int test;
                scanf("%s" , name);
                scanf("%d" , &test);
                while(!all.empty() && all.back().me <= test)
                {
                    all.pop_back();
                }
                cnt ++ ;
                all.push_back(mine(cnt , test));
            }
            else if(flag[0] == 'Q')
            {
                if(all.empty())
                    printf("⑴\n");
                else
                    printf("%d\n" , all.front().me);
            }
            else
            {
                num ++;
                while(!all.empty() && all.front().x <= num)
                {
                    all.pop_front();
                }
            }
        }
    }
    return 0;
}

poj 2019 Cornfields
这道题2维的st算法，说白了，就是1维。。
没处理完1个横的，就处理所有的竖的 i，j代表区间长度2的i次，2的j次
我也不是很懂：为什么用deque写1直wa ，但是指针写，就能够很快的过。。。

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int dpmax[255][255][8][8];
int dpmin[255][255][8][8];
int main()
{
    int n, b, k;
    scanf("%d%d%d", &n , &b ,&k);
    for(int i = 0 ; i < 9 ;++ i)
    {
        for(int j = 0 ; j < 9 ; ++ j)
        {
            for(int x = 1 ; x + (1 << i) - 1<= n ; ++ x)
            {
                for(int y = 1; y + (1 << j) - 1 <= n ; ++ y)
                {
                    if(i == 0)
                    {
                        if(j == 0)
                        {
                            scanf("%d", &dpmax[x][y][i][j]);
                            dpmin[x][y][i][j] = dpmax[x][y][i][j];
                        }
                        else
                        {
                            dpmax[x][y][i][j] = max(dpmax[x][y][i][j - 1] , dpmax[x][y + (1 << (j - 1))][i][j - 1]);
                            dpmin[x][y][i][j] = min(dpmin[x][y][i][j - 1] , dpmin[x][y + (1 << (j - 1))][i][j - 1]);
                        }
                    }
                    else
                    {
                        dpmax[x][y][i][j] = max(dpmax[x][y][i - 1][j] , dpmax[x + (1 << (i - 1))][y][i - 1][j]);
                        dpmin[x][y][i][j] = min(dpmin[x][y][i - 1][j] , dpmin[x + (1 << (i - 1))][y][i - 1][j]);
                    }
                }
            }
        }
    }
    int key = (int)(log(b * 1.0) / log(2.0));
    while(k -- )
    {
        int sx , sy;
        scanf("%d%d", &sx , &sy);
        int ex = sx + b - 1;
        int ey = sy + b - 1;
        printf("%d\n", max(max(dpmax[sx][sy][key][key] , dpmax[ex - (1 << key) + 1][ey - (1 << key) + 1][key][key]) , max(dpmax[ex - (1 << key) + 1][sy][key][key] , dpmax[sx][ey - (1 << key) + 1][key][key])) - min(min(dpmin[sx][sy][key][key] , dpmin[ex - (1 << key) + 1][ey - (1 << key) + 1][key][key]) , min(dpmin[ex - (1 << key) + 1][sy][key][key] , dpmin[sx][ey - (1 << key) + 1][key][key])));
    }
    return 0;
}

1个星期的时间。。1半是在忙这个。。我好菜啊。。。。。

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 基于java最短路径算法公交查询系统的设计与实现

下一篇 UVALive 4730 线段树+并查集

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点