Gym The 13th Chinese Northeast Collegiate Programming Contest H. Skyscraper（线段树+差分）

线段树+差分）"/>

Gym The 13th Chinese Northeast Collegiate Programming Contest H. Skyscraper（线段树+差分）

 前置题目：BLOG

const int N=1e5+5;int n,m,_;int i,j,k;ll a[N];ll d[N];struct Node{int l,r;ll sum,plu;#define lson id<<1#define rson id<<1|1}t[N<<2];void push_up(int id)
{t[id].sum=t[lson].sum+t[rson].sum;ll x=t[lson].plu,y=t[rson].plu;if(x<0) x=0;if(y<0) y=0;t[id].plu=x+y;
}void build(int l,int r,int id)
{t[id].l=l,t[id].r=r;t[id].plu=t[id].sum=0;if(l==r) t[id].plu=t[id].sum=d[l];else {int mid=l+r>>1;build(l,mid,lson);build(mid+1,r,rson);push_up(id);}
}ll query_plu(int id,int l,int r)
{if(l>r) return 0;int L=t[id].l,R=t[id].r;if(L>=l && r>=R) return t[id].plu;else{int mid=L+R>>1;ll x=0,y=0;if(mid>=l) x=query_plu(lson,l,r);if(r>=mid+1) y=query_plu(rson,l,r);if(x<0) x=0; if(y<0) y=0;return x+y;}
}ll query_sum(int id,int l,int r)
{if(l>r) return 0;int L=t[id].l,R=t[id].r;if(L>=l && r>=R) return t[id].sum;else{int mid=L+R>>1;ll ans=0;if(mid>=l) ans+=query_sum(lson,l,r);if(r>=mid+1) ans+=query_sum(rson,l,r);return ans;}
}void update(int id,int pos,int c)
{int L=t[id].l,R=t[id].r;if(L==R) t[id].sum+=c,t[id].plu+=c;else{int mid=L+R>>1;if(mid>=pos) update(lson,pos,c);else update(rson,pos,c);push_up(id);}
}int main()
{rush(){sdd(n,m);for(int i=1;i<=n;i++) sll(a[i]);for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1]; d[n+1]=0;build(1,n+1,1);for(int i=1;i<=m;i++){int x,y,opt,c;sddd(opt,x,y);if(opt==1){sd(c);update(1,x,c);update(1,y+1,-c);} else{ll ans=query_sum(1,1,x);//dbg(ans);ans+=query_plu(1,x+1,y);pll(ans);}}}//PAUSE;return 0;
}