1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
| #include<stack> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=1e5;
int n,m; int Ia[N+3];
struct NODE{ int val,Vl,Vr; NODE(int _val=0,int _Vl=0,int _Vr=0):val(_val),Vl(_Vl),Vr(_Vr){} }; bool operator <(const NODE Pa,const NODE Pb){return Pa.val<Pb.val;} bool operator >(const NODE Pa,const NODE Pb){return Pa.val>Pb.val;} NODE operator +(const NODE Pa,const NODE Pb){return NODE(Pa.val+Pb.val,Pa.Vl,Pb.Vr);} NODE operator *(const NODE Pa,const int Pb){return NODE(Pa.val*Pb,Pa.Vl,Pa.Vr);} NODE operator *=(NODE &Pa,const int Pb){Pa.val*=Pb;return Pa;} struct RESULT{ NODE mid,lef,rig,sum; RESULT(NODE _m,NODE _l,NODE _r,NODE _s):mid(_m),lef(_l),rig(_r),sum(_s){} }; struct SEGTREE{ NODE Emx[N*4],EmxL[N*4],EmxR[N*4],Emn[N*4],EmnL[N*4],EmnR[N*4],Esum[N*4]; bool Zrev[N*4]; void GetRev(int u){ swap(Emx[u],Emn[u]);swap(EmxL[u],EmnL[u]);swap(EmxR[u],EmnR[u]); Emx[u]*=-1;Emn[u]*=-1;EmxL[u]*=-1;EmnL[u]*=-1;EmxR[u]*=-1;EmnR[u]*=-1; Esum[u]*=-1; } void PushUp(int u){ Emx[u]=max(max(Emx[u<<1],Emx[u<<1|1]),EmxR[u<<1]+EmxL[u<<1|1]); Emn[u]=min(min(Emn[u<<1],Emn[u<<1|1]),EmnR[u<<1]+EmnL[u<<1|1]); EmxL[u]=max(EmxL[u<<1],Esum[u<<1]+EmxL[u<<1|1]); EmnL[u]=min(EmnL[u<<1],Esum[u<<1]+EmnL[u<<1|1]); EmxR[u]=max(EmxR[u<<1|1],EmxR[u<<1]+Esum[u<<1|1]); EmnR[u]=min(EmnR[u<<1|1],EmnR[u<<1]+Esum[u<<1|1]); Esum[u]=Esum[u<<1]+Esum[u<<1|1]; } void PushDown(int u,int Vl,int Vr){ if(Vl<Vr && Zrev[u]){ GetRev(u<<1);Zrev[u<<1]=!Zrev[u<<1]; GetRev(u<<1|1);Zrev[u<<1|1]=!Zrev[u<<1|1]; } Zrev[u]=false; } void Build(int u,int Vl,int Vr){ if(Vl==Vr){ Emn[u]=EmnL[u]=EmnR[u]=Emx[u]=EmxL[u]=EmxR[u]=Esum[u]=NODE(Ia[Vl],Vl,Vl); return; } int Vm=(Vl+Vr)>>1; Build(u<<1,Vl,Vm);Build(u<<1|1,Vm+1,Vr); PushUp(u); } void Modify(int u,int Vl,int Vr,int Upos,int Uval){ if(Vr<Upos || Upos<Vl) return; if(Vl==Vr){ Emn[u]=EmnL[u]=EmnR[u]=Emx[u]=EmxL[u]=EmxR[u]=Esum[u]=NODE(Uval,Upos,Upos); return; } PushDown(u,Vl,Vr); int Vm=(Vl+Vr)>>1; Modify(u<<1,Vl,Vm,Upos,Uval);Modify(u<<1|1,Vm+1,Vr,Upos,Uval); PushUp(u); } void Reverse(int u,int Vl,int Vr,int Ul,int Ur){ if(Vr<Ul || Ur<Vl) return; if(Ul<=Vl && Vr<=Ur){ Zrev[u]=!Zrev[u]; GetRev(u); return; } PushDown(u,Vl,Vr); int Vm=(Vl+Vr)>>1; Reverse(u<<1,Vl,Vm,Ul,Ur); Reverse(u<<1|1,Vm+1,Vr,Ul,Ur); PushUp(u); } RESULT Query(int u,int Vl,int Vr,int Ul,int Ur){ if(Ul<=Vl && Vr<=Ur) return RESULT(Emx[u],EmxL[u],EmxR[u],Esum[u]); PushDown(u,Vl,Vr); int Vm=(Vl+Vr)>>1; if(Ur<Vm+1) return Query(u<<1,Vl,Vm,Ul,Ur); if(Vm<Ul) return Query(u<<1|1,Vm+1,Vr,Ul,Ur); RESULT Rl=Query(u<<1,Vl,Vm,Ul,Ur),Rr=Query(u<<1|1,Vm+1,Vr,Ul,Ur); return RESULT(max(max(Rl.mid,Rr.mid),Rl.rig+Rr.lef),max(Rl.lef,Rl.sum+Rr.lef),max(Rr.rig,Rl.rig+Rr.sum),Rl.sum+Rr.sum); } }seg;
stack< pair<int,int> > Sclr; int main(){
scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&Ia[i]); scanf("%d",&m); seg.Build(1,1,n); while(m--){ int Iopt;scanf("%d",&Iopt); if(Iopt){ int Il,Ir,Ik,Vans=0;scanf("%d%d%d",&Il,&Ir,&Ik); while(Ik--){ RESULT Rr=seg.Query(1,1,n,Il,Ir); NODE fRr=max(Rr.mid,max(Rr.lef,Rr.rig)); if(fRr.val<0) break; Sclr.push(make_pair(fRr.Vl,fRr.Vr)); Vans+=fRr.val; seg.Reverse(1,1,n,fRr.Vl,fRr.Vr); } printf("%d\n",Vans); while(!Sclr.empty()){ seg.Reverse(1,1,n,Sclr.top().first,Sclr.top().second); Sclr.pop(); } } else{ int Ipos,Ival;scanf("%d%d",&Ipos,&Ival); seg.Modify(1,1,n,Ipos,Ival); } } return 0; }
|