UVA 11992-多棵线段树

81 阅读 0 评论 54 点赞

我是靠谱客的博主温婉太阳，最近开发中收集的这篇文章主要介绍UVA 11992-多棵线段树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给出一个R*C的矩阵，行数不超过20行，每行元素不超过10^6个。

支持三种操作：

1.子矩阵所有元素+v;

2.子矩阵所有元素设置为v；

3,.查询子矩阵元素中最大值最小值及元素和；

分析：建立20+棵线段树。比较裸的线段树了，就是操作略多，写起来稍微麻烦点，特别注意set标记和add标记的顺序。pushdown的时候优先考虑set标记，等set好了，清除本结点add标记，set标记也要清除。估计这题独立打出来的话单点更新和区间成端更新基础知识就已经很牢固了吧。昨天晚上调到两点愣是没检查出错误，结果是建树的时候，set标记被打成了0，add被打成了-1，我了个大擦啊，今早十点起来刚发现错了。。。已A，难道这才是传说中的吐血AC？

/****************************
* author:crazy_石头
* date：2014/04/21
* time:1322 ms
* algorithm:多棵线段树
* Pro：UVA 11992
***************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std; #define INF INT_MAX #define eps 1e-8 #define A system("pause") #define rep(i,h,n) for(int i=(h);i<=(n);i++) #define ms(a,b) memset((a),(b),sizeof(a)) #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn=100000+5; const int maxm=30; int Max[maxm][maxn<<2],Min[maxm][maxn<<2],sum[maxm][maxn<<2],add[maxm][maxn<<2],set[maxm][maxn<<2]; int m,n,q,Minm,Maxm,ret,L,R,v; inline void build(int id,int l,int r,int rt) { add[id][rt]=0; set[id][rt]=-1; if(l==r) { sum[id][rt]=Min[id][rt]=Max[id][rt]=0; return ; } int m=(l+r)>>1; build(id,lson); build(id,rson); } inline void pushup(int id,int rt)//id表示第几棵树，rt是当前树的根结点； { sum[id][rt]=sum[id][rt<<1]+sum[id][rt<<1|1]; Max[id][rt]=std::max(Max[id][rt<<1],Max[id][rt<<1|1]); Min[id][rt]=std::min(Min[id][rt<<1],Min[id][rt<<1|1]); } inline void pushdown(int id,int l,int r,int rt) { if(set[id][rt]>0)//有add还有set，优先考虑set标记，有set的话该结点注意清除原来的add标记； { set[id][rt<<1]=set[id][rt<<1|1]=set[id][rt]; add[id][rt<<1]=add[id][rt<<1|1]=0;//清除add标记； int m=(l+r)>>1; sum[id][rt<<1]=set[id][rt]*(m-l+1); sum[id][rt<<1|1]=set[id][rt]*(r-m); Min[id][rt<<1]=Min[id][rt<<1|1]=set[id][rt]; Max[id][rt<<1]=Max[id][rt<<1|1]=set[id][rt]; set[id][rt]=-1;//清除本结点set标记； } if(add[id][rt]) { add[id][rt<<1]+=add[id][rt]; add[id][rt<<1|1]+=add[id][rt]; int m=(l+r)>>1; sum[id][rt<<1]+=(m-l+1)*add[id][rt]; sum[id][rt<<1|1]+=(r-m)*add[id][rt]; Min[id][rt<<1]+=add[id][rt]; Min[id][rt<<1|1]+=add[id][rt]; Max[id][rt<<1]+=add[id][rt]; Max[id][rt<<1|1]+=add[id][rt]; add[id][rt]=0;//清除本结点add标记； } } inline void update(int id,int ok,int v,int L,int R,int l,int r,int rt) {//ok表示要操作的类型，v是增减及设定的值，[L,R]是操作区间； if(L<=l&&r<=R) { if(ok==1)//进行add操作； { add[id][rt]+=v; sum[id][rt]+=v*(r-l+1); Min[id][rt]+=v; Max[id][rt]+=v; } if(ok==0) { add[id][rt]=0;//set和add同时存在时优先考虑set，add要请0，最后注意当前结点的标记是向下传的，清除set标记； set[id][rt]=v; sum[id][rt]=(r-l+1)*v; Min[id][rt]=Max[id][rt]=v; } return ; } pushdown(id,l,r,rt);//注意pushdown，标记下传； int m=(l+r)>>1; if(L<=m) update(id,ok,v,L,R,lson); if(R>m) update(id,ok,v,L,R,rson); pushup(id,rt); } inline void query(int id,int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { ret+=sum[id][rt]; //cout<<"ret="<
<
>1; if(L<=m) query(id,L,R,lson); if(R>m) query(id,L,R,rson); } int main() { while(~scanf("%d%d%d",&m,&n,&q)) { rep(i,1,m) build(i,1,n,1); int t,x1,y1,x2,y2; while(q--) { scanf("%d",&t); if(t==1) { scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v); rep(i,x1,x2) update(i,1,v,y1,y2,1,n,1); }//add操作； else if(t==2) { scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v); rep(i,x1,x2) update(i,0,v,y1,y2,1,n,1); }//set操作 else if(t==3) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); ret=0; Minm=INF; Maxm=-1; rep(i,x1,x2) { query(i,y1,y2,1,n,1); } printf("%d %d %dn",ret,Minm,Maxm); } } } //A; return 0; }