Lightoj1081【500棵线段树维护】

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=5e2+10;

const int INF=0x3f3f3f3f;

struct SegT{

    int left;

    int right;

    int w;

};

SegT q[N][N*4];

int dp[N];

int a[N][N];

void Build(int temp,int num,int L,int R)

{

    q[temp][num].left=L;

    q[temp][num].right=R;

    if(L==R)

    {

        q[temp][num].w=a[temp][L];

        return;

    }

    int mid=(L+R)/2;

    Build(temp,2*num,L,mid);

    Build(temp,2*num+1,mid+1,R);

    q[temp][num].w=max(q[temp][2*num].w,q[temp][2*num+1].w);

}

int query(int temp,int num,int s,int t)

{

    if(q[temp][num].left>=s&&q[temp][num].right<=t)

        return q[temp][num].w;

    int mid=(q[temp][num].left+q[temp][num].right)/2;

    if(mid>=t)

        return query(temp,2*num,s,t);

    else if(mid<s)

        return query(temp,2*num+1,s,t);

    else

        return max(query(temp,2*num,s,mid),query(temp,2*num+1,mid+1,t));

}

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        int n,q;

        scanf("%d%d",&n,&q);

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                scanf("%d",&a[i][j]);

        for(int i=1;i<=n;i++)

            Build(i , 1, 1, n);

        int ans,x1,y1,s;

        int x2,y2;

        printf("Case %d:\n",cas++);

        while(q--)

        {

            scanf("%d%d%d",&x1,&y1,&s);

            x2=x1+s-1;

            y2=y1+s-1;

            ans=-INF;

            for(int i=x1;i<=x2;i++)

                ans=max(query(i,1,y1,y2),ans);

            printf("%d\n",ans);

        }

    }

    return 0;

}
巴特西

Lightoj1081【500棵线段树维护】

最新文章

热门文章
