首页 > 代码库 > Fast Matrix Operations
Fast Matrix Operations
uva11992:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3143
题意：给你n*m的矩阵初始化的时候矩阵里面的元素全部是0，对于这个矩阵有3中操作。
1 x1 y1 x2 y2 v 把（x1 y1 x2 y2）子矩阵 里面的元素全部加上v
2 x1 y1 x2 y2 v 把（x1 y1 x2 y2）子矩阵 里面的元素全部置成v
3 x1 y1 x2 y2 求（x1 y1 x2 y2）子矩阵的和，以及最小值和最大值
题解：很明显是二维线段树维护，并且题目中的n不超过20.打20棵线段树就可以解决。这里的置成v，可以看成是*0+v，加上v可以看成*1+v；
线段树维护一个mul乘数，add加数，sum总和，minn最小值，maxn最大值。注意pushdown时候对子节点先*后加。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=100002; 7 struct SegTree{ 8 int l,r; 9 int add,mul; 10 int sum,minn,maxn; 11 void init(){ 12 add=0;mul=1; 13 } 14 inline int mid(){ 15 return (l+r)>> 1; 16 } 17 inline int len(){ 18 return r-l+1; 19 } 20 void to_mul(int m){//每次*一个数，那么之前add的数此时也要*这个数 21 sum *=m; 22 minn*=m; 23 maxn*=m; 24 mul *= m; 25 add *= m; 26 } 27 void to_add(int a){ 28 minn+=a; 29 maxn+=a; 30 sum +=a* len(); 31 add +=a; 32 } 33 }T[23][N*4]; 34 void pushdown(int num,int rt){//这里一定要注意 35 T[num][rt<<1].to_mul(T[num][rt].mul); 36 T[num][rt<<1|1].to_mul(T[num][rt].mul); 37 T[num][rt<<1].to_add(T[num][rt].add); 38 T[num][rt<<1|1].to_add(T[num][rt].add); 39 T[num][rt].init(); 40 } 41 void pushup(int num,int rt){ 42 T[num][rt].sum=T[num][rt<<1].sum+T[num][rt<<1|1].sum; 43 T[num][rt].maxn=max(T[num][rt<<1].maxn,T[num][rt<<1|1].maxn); 44 T[num][rt].minn=min(T[num][rt<<1].minn,T[num][rt<<1|1].minn); 45 } 46 void build(int num,int rt,int l,int r){ 47 T[num][rt].l=l; 48 T[num][rt].r=r; 49 T[num][rt].minn=T[num][rt].maxn=T[num][rt].sum=0; 50 T[num][rt].init(); 51 if(l==r){ 52 return; 53 } 54 int mid=T[num][rt].mid(); 55 build(num,rt<<1,l,mid); 56 build(num,rt<<1|1,mid+1,r); 57 pushup(num,rt); 58 } 59 void update(int num,int rt,int l,int r,int mul,int add){ 60 if(T[num][rt].l==l&&T[num][rt].r==r){ 61 T[num][rt].to_mul(mul); 62 T[num][rt].to_add(add); 63 return; 64 } 65 pushdown(num,rt); 66 int mid=T[num][rt].mid(); 67 if(mid>=r)update(num,rt<<1,l,r,mul,add); 68 else if(mid<l)update(num,rt<<1|1,l,r,mul,add); 69 else { 70 update(num,rt<<1,l,mid,mul,add); 71 update(num,rt<<1|1,mid+1,r,mul,add); 72 } 73 pushup(num,rt); 74 } 75 SegTree query(int num,int rt,int l,int r){ 76 if(T[num][rt].l==l&&T[num][rt].r==r) 77 return T[num][rt]; 78 pushdown(num,rt); 79 int mid=T[num][rt].mid(); 80 if(mid>=r)return query(num,rt<<1,l,r); 81 else if(mid<l)return query(num,rt<<1|1,l,r); 82 else{ 83 SegTree t1=query(num,rt<<1,l,mid); 84 SegTree t2=query(num,rt<<1|1,mid+1,r); 85 SegTree t; 86 t.maxn=max(t1.maxn,t2.maxn); 87 t.minn=min(t1.minn,t2.minn); 88 t.sum=t1.sum+t2.sum; 89 return t; 90 } 91 } 92 int n,m,r; 93 int x1,y1,x2,y2,val,type; 94 int main(){ 95 while(~scanf("%d%d%d",&r,&n,&m)){ 96 for(int i=1;i<=r;i++) 97 build(i,1,1,n); 98 for(int i=1;i<=m;i++){ 99 scanf("%d%d%d%d%d",&type,&x1,&y1,&x2,&y2);100 if(type==1){101 scanf("%d",&val);102 for(int i=x1;i<=x2;i++)103 update(i,1,y1,y2,1,val);104 }105 else if(type==2){106 scanf("%d",&val);107 for(int i=x1;i<=x2;i++)108 update(i,1,y1,y2,0,val);109 }110 else {111 int sum=0,minn=1000000002,maxn=0;112 SegTree ans;113 for(int i=x1;i<=x2;i++){114 ans=query(i,1,y1,y2);115 sum+=ans.sum;116 minn=min(minn,ans.minn);117 maxn=max(maxn,ans.maxn);118 }119 printf("%d %d %d\n",sum,minn,maxn);120 }121 }122 }123 124 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。