UVA11992FastMatrixOperations一次开多棵线段树

1 #include
2 using namespace std;
3 const int maxn=4e5+7;
4 const int N=550;
5 struct node{
6 int l,r,sum,lazy1,lazy2,mi,mx;
7 }tree[22][maxn*4];
8 int n,m,t;
9 int opt,xx,yy,xxx,yyy,v;
10 int ans1,ans2,ans3;
11 void pushdown(int id,int now){
12 if(tree[id][now].lazy1!=-1){
13 tree[id][now<<1].sum=(tree[id][now<<1].r-tree[id][now<<1].l+1)*tree[id][now].lazy1;
14 tree[id][now<<1|1].sum=(tree[id][now<<1|1].r-tree[id][now<<1|1].l+1)*tree[id][now].lazy1;
15 tree[id][now<<1].mi=tree[id][now].lazy1;
16 tree[id][now<<1].mx=tree[id][now].lazy1;
17 tree[id][now<<1|1].mi=tree[id][now].lazy1;
18 tree[id][now<<1|1].mx=tree[id][now].lazy1;
19 tree[id][now<<1].lazy1=tree[id][now].lazy1;
20 tree[id][now<<1|1].lazy1=tree[id][now].lazy1;
21 tree[id][now<<1].lazy2=tree[id][now<<1|1].lazy2=0;
22 tree[id][now].lazy1=-1;
23 }
24 if(tree[id][now].lazy2){
25 tree[id][now<<1].sum+=(tree[id][now<<1].r-tree[id][now<<1].l+1)*tree[id][now].lazy2;
26 tree[id][now<<1|1].sum+=(tree[id][now<<1|1].r-tree[id][now<<1|1].l+1)*tree[id][now].lazy2;
27 tree[id][now<<1].mi+=tree[id][now].lazy2;
28 tree[id][now<<1].mx+=tree[id][now].lazy2;
29 tree[id][now<<1|1].mi+=tree[id][now].lazy2;
30 tree[id][now<<1|1].mx+=tree[id][now].lazy2;
31 tree[id][now<<1].lazy2+=tree[id][now].lazy2;
32 tree[id][now<<1|1].lazy2+=tree[id][now].lazy2;
33 tree[id][now].lazy2=0;
34 }
35 }
36 void pushup(int id,int now){
37 tree[id][now].sum=tree[id][now<<1].sum+tree[id][now<<1|1].sum;
38 tree[id][now].mi=min(tree[id][now<<1].mi,tree[id][now<<1|1].mi);
39 tree[id][now].mx=max(tree[id][now<<1].mx,tree[id][now<<1|1].mx);
40 }
41 void build(int id,int now,int l,int r){
42 tree[id][now].l=l,tree[id][now].r=r,tree[id][now].lazy1=-1;
43 if(l==r) return;
44 int mid=(l+r)>>1;
45 build(id,now<<1,l,mid);
46 build(id,now<<1|1,mid+1,r);
47 pushup(id,now);
48 }
49 void update1(int id,int now,int l,int r,int v){
50 if(tree[id][now].l>=l&&tree[id][now].r<=r){
51 tree[id][now].sum=(tree[id][now].r-tree[id][now].l+1)*v;
52 tree[id][now].mi=v;
53 tree[id][now].mx=v;
54 tree[id][now].lazy1=v;
55 tree[id][now].lazy2=0;
56 return;
57 }
58 pushdown(id,now);
59 int mid=(tree[id][now].l+tree[id][now].r)>>1;
60 if(l<=mid) update1(id,now<<1,l,r,v);
61 if(r>mid) update1(id,now<<1|1,l,r,v);
62 pushup(id,now);
63 }
64 void update2(int id,int now,int l,int r,int v){
65 if(tree[id][now].l>=l&&tree[id][now].r<=r){
66 tree[id][now].sum+=(tree[id][now].r-tree[id][now].l+1)*v;
67 tree[id][now].mi+=v;
68 tree[id][now].mx+=v;
69 tree[id][now].lazy2+=v;
70 return;
71 }
72 pushdown(id,now);
73 int mid=(tree[id][now].l+tree[id][now].r)>>1;
74 if(l<=mid) update2(id,now<<1,l,r,v);
75 if(r>mid) update2(id,now<<1|1,l,r,v);
76 pushup(id,now);
77 }
78 int querymax(int id,int now,int l,int r){
79 if(tree[id][now].l>=l&&tree[id][now].r<=r) return tree[id][now].mx;
80 pushdown(id,now);
81 int mid=(tree[id][now].l+tree[id][now].r)>>1;
82 int val=-0x3f3f3f3f;
83 if(l<=mid) val=max(val,querymax(id,now<<1,l,r));
84 if(r>mid) val=max(val,querymax(id,now<<1|1,l,r));
85 return val;
86 }
87 int querymin(int id,int now,int l,int r){
88 if(tree[id][now].l>=l&&tree[id][now].r<=r) return tree[id][now].mi;
89 pushdown(id,now);
90 int mid=(tree[id][now].l+tree[id][now].r)>>1;
91 int val=0x3f3f3f3f;
92 if(l<=mid) val=min(val,querymin(id,now<<1,l,r));
93 if(r>mid) val=min(val,querymin(id,now<<1|1,l,r));
94 return val;
95 }
96 int querysum(int id,int now,int l,int r){
97 if(tree[id][now].l>=l&&tree[id][now].r<=r) return tree[id][now].sum;
98 pushdown(id,now);
99 int mid=(tree[id][now].l+tree[id][now].r)>>1;
100 int val=0;
101 if(l<=mid) val+=querysum(id,now<<1,l,r);
102 if(r>mid) val+=querysum(id,now<<1|1,l,r);
103 return val;
104 }
105 int main(){
106 while(scanf("%d%d%d",&n,&m,&t)!=EOF){
107 memset(tree,0,sizeof(tree));
108 for(int i=1;i<=n;i++) build(i,1,1,m);
109 for(int i=1;i<=t;i++){
110 scanf("%d",&opt);
111 if(opt==1){
112 scanf("%d%d%d%d%d",&xx,&yy,&xxx,&yyy,&v);
113 for(int i=xx;i<=xxx;i++) update2(i,1,yy,yyy,v);
114 }
115 if(opt==2){
116 scanf("%d%d%d%d%d",&xx,&yy,&xxx,&yyy,&v);
117 for(int i=xx;i<=xxx;i++) update1(i,1,yy,yyy,v);
118 }
119 if(opt==3){
120 ans1=0,ans2=0x3f3f3f3f,ans3=-0x3f3f3f3f;
121 scanf("%d%d%d%d",&xx,&yy,&xxx,&yyy);
122 for(int i=xx;i<=xxx;i++) ans1+=querysum(i,1,yy,yyy);
123 for(int i=xx;i<=xxx;i++) ans2=min(ans2,querymin(i,1,yy,yyy));
124 for(int i=xx;i<=xxx;i++) ans3=max(ans3,querymax(i,1,yy,yyy));
125 printf("%d %d %d\n",ans1,ans2,ans3);
126 }
127 }
128 }
129 return 0;
130 }