您當前位置：首頁 > php開源 > php教程 > 單調棧/單調隊列/RMQ

單調棧/單調隊列/RMQ

來源：程序員人生發布時間：2016-06-07 08:18:28 閱讀次數：2424次

在上上周的交友大會中，隊長大人提到了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關注

欄目熱點

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

單調棧/單調隊列/RMQ