首页 > 代码库 > UVA 11992 Fast Matrix Operations
UVA 11992 Fast Matrix Operations
线段树
1 #include <iostream> 2 using namespace std; 3 4 const int maxn = 1000005; 5 const int INF = 1000000009; 6 7 struct node { 8 int sum,ma,mi; 9 int addv,setv; 10 void init (int nsum,int nma,int nmi,int naddv,int nsetv){ 11 sum=nsum;ma=nma;mi=nmi; 12 addv=naddv;setv=nsetv; 13 } 14 }tree[30][maxn*2]; 15 16 int r,c,m; 17 18 void init (){ 19 for (int i=1;i<=r;i++){ 20 for (int j=1;j<=c*2;j++){ 21 tree[i][j].init (0,0,0,0,-1); 22 } 23 tree[i][1].setv=0; 24 } 25 } 26 27 //int sum[30][maxn],ma[30][maxn],mi[30][maxn]; 28 //int addv[30][maxn],setv[30][maxn]; 29 30 void maintain (int o,int l,int r,int i){ 31 int lc=o<<1,rc=(o<<1)+1; 32 if (r>l){ 33 tree[i][o].sum=tree[i][lc].sum+tree[i][rc].sum; 34 tree[i][o].mi=min (tree[i][lc].mi,tree[i][rc].mi); 35 tree[i][o].ma=max (tree[i][lc].ma,tree[i][rc].ma); 36 } 37 if (tree[i][o].setv!=-1){ 38 tree[i][o].mi=tree[i][o].setv; 39 tree[i][o].ma=tree[i][o].setv; 40 tree[i][o].sum=tree[i][o].setv*(r-l+1); 41 } 42 if (tree[i][o].addv){ 43 tree[i][o].mi+=tree[i][o].addv; 44 tree[i][o].ma+=tree[i][o].addv; 45 tree[i][o].sum+=tree[i][o].addv*(r-l+1); 46 } 47 } 48 49 void pushdown (int o,int i){ 50 int lc=o<<1,rc=(o<<1)+1; 51 if (tree[i][o].setv!=-1){ 52 tree[i][lc].setv=tree[i][rc].setv=tree[i][o].setv; 53 tree[i][lc].addv=tree[i][rc].addv=0; 54 tree[i][o].setv=-1; 55 } 56 if (tree[i][o].addv>0){ 57 tree[i][lc].addv+=tree[i][o].addv; 58 tree[i][rc].addv+=tree[i][o].addv; 59 tree[i][o].addv=0; 60 } 61 } 62 63 void add (int o,int l,int r,int x1,int x2,int i,int v){ 64 int m=l+(r-l)/2,lc=o<<1,rc=(o<<1)+1; 65 if (x1<=l&&r<=x2){ 66 tree[i][o].addv+=v; 67 } 68 else { 69 pushdown (o,i); 70 if (x1<=m) add (lc,l,m,x1,x2,i,v);else maintain (lc,l,m,i); 71 if (m<x2) add (rc,m+1,r,x1,x2,i,v);else maintain (rc,m+1,r,i); 72 } 73 maintain (o,l,r,i); 74 return ; 75 } 76 77 void set (int o,int l,int r,int x1,int x2,int i,int v){ 78 int m=l+(r-l)/2; 79 int lc=o<<1,rc=(o<<1)+1; 80 if (x1<=l&&r<=x2){ 81 tree[i][o].setv=v; 82 tree[i][o].addv=0; 83 } 84 else { 85 pushdown (o,i); 86 if (x1<=m) set (lc,l,m,x1,x2,i,v);else maintain (lc,l,m,i); 87 if (m<x2) set (rc,m+1,r,x1,x2,i,v);else maintain (rc,m+1,r,i); 88 } 89 maintain (o,l,r,i); 90 return ; 91 } 92 int sum,ma,mi; 93 int query (int o,int l,int r,int x1,int x2,int i,int addv){ 94 int m=l+(r-l)/2,lc=o<<1,rc=(o<<1)+1; 95 if (tree[i][o].setv!=-1){ 96 int x=tree[i][o].setv+addv+tree[i][o].addv; 97 sum+=x*(min(r,x2)-max(l,x1)+1); 98 mi=min (mi,x); 99 ma=max (ma,x);100 addv=0;101 }102 else if (x1<=l&&r<=x2){103 sum+=tree[i][o].sum+addv*(r-l+1);104 mi=min (mi,tree[i][o].mi+addv);105 ma=max (ma,tree[i][o].ma+addv);106 }107 else {108 if (x1<=m) query (lc,l,m,x1,x2,i,addv+tree[i][o].addv);109 if (x2>m) query (rc,m+1,r,x1,x2,i,addv+tree[i][o].addv);110 }111 }112 113 int main (){114 while (cin>>r>>c>>m){115 init ();116 while (m--){117 int f,x1,x2,y1,y2,v;118 cin>>f>>x1>>y1>>x2>>y2;119 if (f==1){120 cin>>v;121 for (int i=x1;i<=x2;i++)122 add (1,1,c,y1,y2,i,v);123 }124 else if (f==2){125 cin>>v;126 for (int i=x1;i<=x2;i++)127 set (1,1,c,y1,y2,i,v);128 }129 else if (f==3){130 sum=0;ma=-INF;mi=INF;131 for (int i=x1;i<=x2;i++)132 query (1,1,c,y1,y2,i,0);133 cout<<sum<<" "<<mi<<" "<<ma<<endl;134 }135 }136 }137 return 0;138 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。