首页 > 代码库 > 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); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。