POJ 2019 Cornfields 二维线段树的初始化与最值查询

发布时间:2017-7-9 7:34:55编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 2019 Cornfields 二维线段树的初始化与最值查询 ",主要涉及到POJ 2019 Cornfields 二维线段树的初始化与最值查询 方面的内容,对于POJ 2019 Cornfields 二维线段树的初始化与最值查询 感兴趣的同学可以参考一下。

模板到不行。。

连更新都没有。。

。存个模板。

理解留到小结的时候再写。

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#include <cmath>#include <stack>#include <map>#pragma comment(linker, "/STACK:1024000000");#define EPS (1e-8)#define LL long long#define ULL unsigned long long#define _LL __int64#define _INF 0x3f3f3f3f#define Mod 9999991#define lowbit(x) (x&(-x))using namespace std;struct N{    int Min,Max;}st[1200][1200];int num[310][310];void Init_Y(int s1,int s2,int l,int r,int t,int b){    if(t == b)    {        if(l == r)        {            st[s1][s2].Max = num[l][t];            st[s1][s2].Min = num[l][t];        }        else        {            st[s1][s2].Max = max(st[s1<<1][s2].Max,st[s1<<1|1][s2].Max);            st[s1][s2].Min = min(st[s1<<1][s2].Min,st[s1<<1|1][s2].Min);        }        return ;    }    int mid = (t+b)>>1;    Init_Y(s1,s2<<1,l,r,t,mid);    Init_Y(s1,s2<<1|1,l,r,mid+1,b);    st[s1][s2].Max = max(st[s1][s2<<1].Max,st[s1][s2<<1|1].Max);    st[s1][s2].Min = min(st[s1][s2<<1].Min,st[s1][s2<<1|1].Min);}void Init_X(int s1,int s2,int l,int r,int t,int b){    if(l != r)    {        int mid = (l+r)>>1;        Init_X(s1<<1,s2,l,mid,t,b);        Init_X(s1<<1|1,s2,mid+1,r,t,b);    }    Init_Y(s1,s2,l,r,t,b);}N Query_Y(int s1,int s2,int L,int R,int T,int B,int l,int r,int t,int b){    if(T == t && B == b)        return st[s1][s2];    int mid = (T+B)>>1;    if(b <= mid)        return Query_Y(s1,s2<<1,L,R,T,mid,l,r,t,b);    else if(mid < t)        return Query_Y(s1,s2<<1|1,L,R,mid+1,B,l,r,t,b);    N temp,t1,t2;    t1 = Query_Y(s1,s2<<1,L,R,T,mid,l,r,t,mid);    t2 = Query_Y(s1,s2<<1|1,L,R,mid+1,B,l,r,mid+1,b);    temp.Max = max(t1.Max,t2.Max);    temp.Min = min(t1.Min,t2.Min);    return temp;}N Query_X(int s1,int s2,int L,int R,int T,int B,int l,int r,int t,int b){    if(L == l && R == r)    {        return Query_Y(s1,s2,L,R,T,B,l,r,t,b);    }    int mid = (L+R)>>1;    if(r <= mid)        return Query_X(s1<<1,s2,L,mid,T,B,l,r,t,b);    else if(mid < l)        return Query_X(s1<<1|1,s2,mid+1,R,T,B,l,r,t,b);    N temp,t1,t2;    t1 = Query_X(s1<<1,s2,L,mid,T,B,l,mid,t,b);    t2 = Query_X(s1<<1|1,s2,mid+1,R,T,B,mid+1,r,t,b);    temp.Max = max(t1.Max,t2.Max);    temp.Min = min(t1.Min,t2.Min);    return temp;}int main(){    int n,m,k,b,i,j,x,y;    scanf("%d %d %d",&n,&b,&k);    for(i = 1;i <= n; ++i)    {        for(j = 1;j <= n; ++j)        {            scanf("%d",&num[i][j]);        }    }    Init_X(1,1,1,n,1,n);    while(k--)    {        scanf("%d %d",&x,&y);        N temp = Query_X(1,1,1,n,1,n,x,min(n,x+b-1),y,min(n,y+b-1));        printf("%d\n",temp.Max-temp.Min);    }


上一篇:CSS学习笔记

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款