首页 > 代码库 > UVA 11297 Census ——二维线段树
UVA 11297 Census ——二维线段树
【题目分析】
二维线段树模板题目。
简直就是无比的暴力。时间复杂度为两个log。
标记的更新方式比较奇特,空间复杂度为N^2。
模板题目。
【代码】
#include <cstdio> #include <cstring> //#include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define maxn 505 #define inf 0x3f3f3f3f #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) void Finout() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif } int Getint() { int x=0,f=1; char ch=getchar(); while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int mx[maxn<<2][maxn<<2],mn[maxn<<2][maxn<<2],rt[maxn<<2],ma[maxn][maxn],n; int x,y,c,tot=0,x1,x2,y1,y2; void pushup(int rt,int o) { mx[rt][o]=max(mx[rt][o<<1],mx[rt][o<<1|1]); mn[rt][o]=min(mn[rt][o<<1],mn[rt][o<<1|1]); } void update(int rt,int o,int l,int r) { // printf("update %d %d %d %d\n",rt,o,l,r); if (l==r) { mx[rt][o]=max(mx[rt<<1][o],mx[rt<<1|1][o]); mn[rt][o]=min(mn[rt<<1][o],mn[rt<<1|1][o]); return; } int mid=l+r>>1; if (y<=mid) update(rt,o<<1,l,mid); else update(rt,o<<1|1,mid+1,r); pushup(rt,o); } void push(int rt,int o,int l,int r) { if (l==r) { mx[rt][o]=mn[rt][o]=c; return ; } int mid=l+r>>1; if (y<=mid) push(rt,o<<1,l,mid); else push(rt,o<<1|1,mid+1,r); pushup(rt,o); } void modi(int o,int l,int r) { if (l==r){push(o,1,1,n);return;} int mid=l+r>>1; if (x<=mid) modi(o<<1,l,mid); else modi(o<<1|1,mid+1,r); update(o,1,1,n); } char opt[11];int amx,amn,q; void queryy(int rt,int o,int l,int r) { // printf("queryy %d %d %d %d\n",rt,o,l,r); if (y1<=l&&r<=y2) { amx=max(amx,mx[rt][o]); amn=min(amn,mn[rt][o]); return ; } int mid=l+r>>1; if (y1<=mid) queryy(rt,o<<1,l,mid); if (y2>mid) queryy(rt,o<<1|1,mid+1,r); } void queryx(int o,int l,int r) { // printf("query x %d %d %d\n",o,l,r); if (x1<=l&&r<=x2){ return queryy(o,1,1,n); } int mid=l+r>>1; if (x1<=mid) queryx(o<<1,l,mid); if (x2>mid) queryx(o<<1|1,mid+1,r); } int main() { memset(mx,-0x3f,sizeof mx); memset(mn, 0x3f,sizeof mn); Finout(); n=Getint(); F(i,1,n) F(j,1,n) { x=i;y=j; c=ma[i][j]=Getint(); modi(1,1,n); } // cout<<mx[1][1]<<" "<<mn[1][1]<<endl; q=Getint(); F(i,1,q) { scanf("%s",opt); if (opt[0]==‘c‘) { x=Getint(); y=Getint(); c=Getint(); modi(1,1,n); } else { x1=Getint(); y1=Getint(); x2=Getint(); y2=Getint(); amx=-inf,amn=inf; queryx(1,1,n); printf("%d %d\n",amx,amn); } } }
UVA 11297 Census ——二维线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。