鏈接:Miku
------------------
沒有UVa賬號唉
-------------------
卡了蒟蒻一天，因為漏掉了懶標記的下放，
線段樹的巨大碼量，為bug提供了絕佳的掩護
寫完后，我哭了
人間的喜悅就這么簡單吧
---------------------
對于一個矩陣，有兩個操作，子矩陣加v或者子矩陣變為v
詢問子矩陣最大值，最小值和和
-------------------------
最簡單的想法是線段樹，不過太難實作了（對于本蒟蒻），所以說還是可以用一維線段樹做的
這矩陣雖然很長，但是不寬，我們完全可以把每一行首位相接，然后拼成一維的
--------------------------
修改 兩個操作，區間賦值比區間加有限度要高，而且區間賦值了之后就沒必要加了，所以說
直接把加變為零就可以了
----------------------------
查詢 三個分別查就可以了
--------------------------------
#include<iostream> #include<cstdio> using namespace std; int n,m; const int maxnn=1e7+9; long long sum[maxnn],lazyadd[maxnn],lazychange[maxnn]; int x,y,f; int q,xx,yy; long long maxn[maxnn],minn[maxnn]; long long k; int s; long long ans,ans1,ans2; void pushdown(int x,int l,int r){ if(lazychange[x]!=0){//很顯然的修改 int mid=(l+r)>>1; lazyadd[x<<1]=0; lazyadd[x<<1|1]=0; lazychange[x<<1|1]=lazychange[x<<1]=lazychange[x]; sum[x<<1]=(mid-l+1)*lazychange[x]; sum[x<<1|1]=(r-mid)*lazychange[x]; maxn[x<<1]=lazychange[x]; maxn[x<<1|1]=lazychange[x]; minn[x<<1]=lazychange[x]; minn[x<<1|1]=lazychange[x]; lazychange[x]=0; } if (lazyadd[x] != 0){ int mid=(l+r)>>1; lazyadd[x<<1]+=lazyadd[x]; sum[x<<1]+=lazyadd[x]*(mid-l+1); lazyadd[x<<1|1]+=lazyadd[x]; sum[x<<1|1]+=lazyadd[x]*(r-mid); maxn[x<<1]+=lazyadd[x]; maxn[x<<1|1]+=lazyadd[x]; minn[x<<1]+=lazyadd[x]; minn[x<<1|1]+=lazyadd[x]; lazyadd[x]=0; } return ; } void pushup(int x){ sum[x]=sum[x<<1]+sum[x<<1|1]; maxn[x]=max(maxn[x<<1],maxn[x<<1|1]); minn[x]=min(minn[x<<1],minn[x<<1|1]); return ; } void update1(int x,int l,int r,int L,int R,long long d){ if(L<=l&&r<=R){ lazyadd[x]+=d; sum[x]+=d*(r-l+1); maxn[x]+=d; minn[x]+=d; return ; } int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) update1(x<<1,l,mid,L,R,d); if(R>mid) update1(x<<1|1,mid+1,r,L,R,d); pushup(x); } void update3(int x,int l,int r,int L,int R,long long d){ if(L<=l&&r<=R){ lazyadd[x]=0;//記得賦值為0 lazychange[x]=d; maxn[x]=d; minn[x]=d; sum[x]=d*(r-l+1); return ; } int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) update3(x<<1,l,mid,L,R,d); if(R>mid) update3(x<<1|1,mid+1,r,L,R,d); pushup(x); } long long query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ return sum[x]; } long long ans=0; int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) ans+=query(x<<1,l,mid,L,R); if(R>mid) ans+=query(x<<1|1,mid+1,r,L,R); return ans; } long long query2(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ return maxn[x]; } long long ans=0; int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) ans=max(query2(x<<1,l,mid,L,R),ans); if(R>mid) ans=max(ans,query2(x<<1|1,mid+1,r,L,R)); return ans; } long long query3(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ return minn[x]; } long long ans=0x7f7f7f7f; int mid=(l+r)>>1; pushdown(x,l,r); if(L<=mid) ans=min(ans,query3(x<<1,l,mid,L,R)); if(R>mid) ans=min(ans,query3(x<<1|1,mid+1,r,L,R)); return ans; } int main(){ scanf("%d%d%d",&n,&m,&q); s=n*m; for(int i=1;i<=q;++i){ scanf("%d",&f); if(f==1){ scanf("%d%d%d%d%lld",&x,&y,&xx,&yy,&k);//一操作 for(int j=x-1;j<xx;++j){ update1(1,1,s,y+j*m,yy+j*m,k); } } if(f==2){ scanf("%d%d%d%d%lld",&x,&y,&xx,&yy,&k);//二操作 for(int j=x-1;j<xx;++j){ update3(1,1,s,y+j*m,yy+j*m,k); } } if(f==3){ scanf("%d%d%d%d",&x,&y,&xx,&yy);//查詢時間 ans=0; for(int j=x-1;j<xx;++j){ ans+=query(1,1,s,y+j*m,yy+j*m); } printf("%lld ",ans); ans=0x7f7f7f;//先是最小值 for(int j=x-1;j<xx;++j){ ans=min(ans,query3(1,1,s,y+j*m,yy+j*m)); } printf("%lld ",ans); ans=0; for(int j=x-1;j<xx;++j){ ans=max(ans,query2(1,1,s,y+j*m,yy+j*m)); } printf("%lld\n",ans); } } return 0; }Ac
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205312.html
標籤：其他
上一篇：區間操作---樹狀陣列&&線段樹
下一篇：靜態順序表操作