poj 2019 Cornfields

题目链接：http://poj.org/problem?id=2019

题目思路：用单调队列做预处理，n^2的复杂度。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int q1[260],q2[260];
int dp1[260][260],dp2[260][260];
int a[260];
int main()
{
    int i,j,n,b,k,x,y;
    while(scanf("%d%d%d",&n,&b,&k)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            int top1=0,tail1=0,top2=0,tail2=0;
            for(j=1;j<=n;j++)
            {
                scanf("%d",&a[j]);
                while(tail1>top1&&a[j]>=a[q1[tail1-1]])
                    tail1--;
                q1[tail1++]=j;
                while(tail2>top2&&a[j]<=a[q2[tail2-1]])
                    tail2--;
                q2[tail2++]=j;
                while(tail1>top1&&j-b+1>q1[top1])
                    top1++;
                while(tail2>top2&&j-b+1>q2[top2])
                    top2++;
                if(j>=b)
                dp1[i][j-b+1]=a[q1[top1]],dp2[i][j-b+1]=a[q2[top2]];
              //  if(j>=b)
           //     printf("i %d j %d dp %d %d\n ",i,j-b+1,dp1[i][j-b+1],dp2[i][j-b+1]);
            }
        }
        for(i=1;i<=n;i++)
        {
            int top1=0,tail1=0,top2=0,tail2=0;
            for(j=1;j<=n;j++)
            {
                while(tail1>top1&&dp1[j][i]>=dp1[q1[tail1-1]][i])
                    tail1--;
                q1[tail1++]=j;
                while(tail2>top2&&dp2[j][i]<=dp2[q2[tail2-1]][i])
                    tail2--;
                q2[tail2++]=j;
                while(tail1>top1&&j-q1[top1]+1>b)
                    top1++;
                while(tail2>top2&&j-q2[top2]+1>b)
                    top2++;
                if(j>=b)
                dp1[j-b+1][i]=dp1[q1[top1]][i],dp2[j-b+1][i]=dp2[q2[top2]][i];
            }
        }
        while(k--)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",dp1[x][y]-dp2[x][y]);
        }
    }

}