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
|
#include <cstdlib> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; ll seg[400005]={0},tag[400005]={0},_v,sum[400005],loc[400005]; int _a,_b,m,n,siz; pair<int,ll> Nulll; void (int id){ if(seg[id<<1]>seg[id<<1|1]) seg[id]=seg[id<<1],loc[id]=loc[id<<1]; else seg[id]=seg[id<<1|1],loc[id]=loc[id<<1|1]; sum[id]=sum[id<<1]+sum[id<<1|1]; } void build_seg(){ for(siz=1;siz<n;siz<<=1); int i; for(i=siz;i<siz+n;i++) scanf("%lld",&seg[i]), tag[i]=0,sum[i]=seg[i],loc[i]=i-siz+1; for(;i<(siz<<1);i++) seg[i]=sum[i]=tag[i]=loc[i]=0; for(i=siz-1;i>=1;i--) maintain(i); } void pushdown(int id,ll len){ if(!tag[id])return ; seg[id<<1]+=tag[id],seg[id<<1|1]+=tag[id]; tag[id<<1]+=tag[id],tag[id<<1|1]+=tag[id]; sum[id<<1]+=tag[id]*(len>>1),sum[id<<1|1]+=tag[id]*(len>>1); tag[id]=0; } void update(int id,int l,int r){ if(l>_b||r<_a)return ; if(l>=_a&&r<=_b){ seg[id]+=_v,tag[id]+=_v,sum[id]+=(r-l+1)*_v; return ; } pushdown(id,(ll)(r-l+1)); update(id<<1,l,(l+r)>>1); update(id<<1|1,(l+r+1)>>1,r); maintain(id); } pair<int,ll> query_p(int id,int l,int r){ pair<int,ll> P,p1; P.first=P.second=-1; if(l>_b||r<_a)return Nulll; if(l>=_a&&r<=_b){ P.first=loc[id],P.second=seg[id]; return P; } pushdown(id,(ll)(r-l+1)); p1=query_p(id<<1,l,(l+r)>>1); if(p1.second>P.second)P=p1; p1=query_p(id<<1|1,(l+r+1)>>1,r); if(p1.second>P.second)P=p1; return P; } ll query(int id,int l,int r){ if(l>_b||r<_a)return 0; if(l>=_a&&r<=_b)return sum[id]; pushdown(id,(ll)(r-l+1)); return query(id<<1,l,(l+r)>>1)+query(id<<1|1,(l+r+1)>>1,r); } void init(){ scanf("%d%d",&n,&m); build_seg(); Nulll.first=-1,Nulll.second=-1; } void solve(){ for(int i=0;i<m;i++){ int typ,_c,_d; scanf("%d",&typ); if(typ==1) scanf("%d%d",&_a,&_b), printf("%lldn",query(1,1,siz)); else if(typ==2){ scanf("%d%d%lld",&_c,&_d,&_v); ll Mod=_v; pair<int,ll> P; for(;;){ _a=_c,_b=_d; P=query_p(1,1,siz); if(P.second<Mod)break; _a=_b=P.first,_v=P.second%Mod-P.second; update(1,1,siz); } }else{ scanf("%d%lld",&_a,&_v), _b=_a,_v-=query(1,1,siz),update(1,1,siz); } } } int main(){ init(); solve(); return 0; }
|
近期评论