【题目分析】

二维线段树模板题目。

简直就是无比的暴力。时间复杂度为两个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);
}
}
}

  

最新文章

  1. 一个App完成入门篇(六)- 完成通讯录页面
  2. Web jquery表格组件 JQGrid 的使用 - 4.JQGrid参数、ColModel API、事件及方法
  3. 使用MacBook Air的4项基本技巧
  4. 使用spring-data-solr做solr客户端
  5. 理解RxJava:(四)Reactive Android
  6. JQuery知识快览之二—事件
  7. 数据库索引&lt;一&gt; 索引结构表结构
  8. osg轮廓特效 【转】
  9. Unity3D TestTool Part _1
  10. 2015-J. PUMA
  11. c# 串口发送接收数据
  12. 嵌入式C语言之---模块化编程
  13. Python函数式编程初级学习
  14. c# json处理(转)
  15. 在Linux下安装eclipse
  16. 关于 Expression is not assignable 错误
  17. vue中mixins的使用
  18. org.jsoup.HttpStatusException: HTTP error fetching URL. Status=403
  19. WP8.1学习系列(第二十一章)——本地应用数据
  20. 树莓派发射FM波——搭建私人小电台

热门文章

  1. How to install Eclipse?
  2. webpack 使用流程
  3. CAD交互绘制圆形批注(网页版)
  4. StringMVCWeb接受前台值的几种方式
  5. pseudogene|鉴定功能基因|expressed se|quence tag
  6. Java创建图片文件缩略图
  7. Bootstrap历练实例:警告样式按钮
  8. shell脚本,alias别名命令用法。
  9. NoSQL 之 Morphia 操作 MongoDB
  10. Python学习记录1