UVA11992 Fast Matrix Operations 一次开多棵线段树

朱雀 2023-06-04 08:00 40阅读 0赞

[**题目链接**][Link 1]

**刘汝佳书上的题目，可以把矩形的每一行都开一棵线段树，最多也就20棵，空间也炸不了。然后就是线段树操作了。**

**注意：下传的时候最大，最小值也要更新。同样注意标记的优先级顺序。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
      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 }

转载于:https://www.cnblogs.com/LJB666/p/11386068.html

[Link 1]: https://www.luogu.org/problem/UVA11992
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/9986927dfcb4440892b7dbf603ae561a.png