来自ppq的毒瘤线段树
Description
有一天喜欢买鞋的ppq和小伙伴来到了某一家球鞋店，球鞋店有n种球鞋，价格分别为ai，ppq在鞋店兜兜转转，发现鞋店老板会偶尔将某段区间内球鞋的价格增加或减少，或者将某双球鞋的价格由价格A修改至价格B，机智的ppq将这些信息记录下来，可是ppq不会数数，所以他向机智的ACMer们求助，请帮助ppq完成以下m次操作，并得到ppq询问的结果。
有以下6种操作：
操作1：鞋店老板将下标位于【L，R】区间的球鞋的价格增加k。（无良老板）
操作2：鞋店老板将下标位于【L，R】区间的球鞋的价格减少k。（良心老板）
操作3： 鞋店老板将下标为pos的球鞋的价格修改为bi
操作4：ppq想买下标位于【L，R】区间内最贵的球鞋，询问他需要花费多少钱
操作5：ppq想买下标位于【L，R】区间内最便宜的球鞋，询问他需要花费多少钱
操作6：ppq想买下标位于【L，R】区间内所有的球鞋，询问他需要花费多少钱
Input
第一行输入n和q（n∈[1,300000],q∈[1,300000]）
接下来一行n个数ai,表示第i种球鞋的价格，(ai∈[0,100000]) (因为可能是限量球鞋所以特别贵，滑稽)
接下来q行操作：
q1 L R k 表示将区间[L,R] 内的球鞋价格增加k元 (k∈[0,100000]，1<=L<R<=n)
q2 L R k 表示将区间[L,R]内的球鞋价格减少k元 (k∈[0,100000],1<=L<R<=n)
q3 pos b表示将第pos双鞋的价格修改为b (pos∈[1,n],b∈[0,1000000],1<=pos<=n)
q4 L R 表示询问区间[L,R]内最贵的球鞋(1<=L<R<=n)
q5 L R 表示询问区间[L,R]内最便宜的球鞋(1<=L<R<=n)
q6 L R表示询问区间[L,R]内球鞋的价格之和(1<=L<R<=n)
Output
输出每次询问的答案（请注意答案可能为负数）
记得push_down ! ! !
ACODE:
//7777777 #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> #include<string> #include<queue> #include<utility> #include<vector> #define lson l , m , rt << 1 #define rson m+1 , r , rt << 1 | 1 #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const double pi = 3.1415926535; const double eps = 1e-6; const int MX = 1e6 + 7; const int maxbit = 18; const double val = pi/180.0; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; ll n,m; struct node { ll sum; ll max; ll min; }t[MX<<2]; ll a[MX<<2]; ll tag[MX<<2]; inline ll ls(ll p){return p << 1;} inline ll rs(ll p){return p << 1|1;} void push_up(ll p) { t[p].min = min(t[ls(p)].min,t[rs(p)].min); t[p].sum = t[ls(p)].sum + t[rs(p)].sum; t[p].max = max(t[ls(p)].max,t[rs(p)].max); } void build(ll p,ll l,ll r) { if(l == r) { t[p].max = a[l]; t[p].min = a[l]; t[p].sum = a[l]; return; } ll mid = (l+r) >> 1; build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p); } inline void f(ll p,ll l,ll r,ll k) { tag[p] = tag[p] + k; t[p].sum = t[p].sum + (r - l + 1)*k; t[p].min =t[p].min+k; t[p].max =t[p].max+k; } inline void push_down(ll p,ll l,ll r) { ll mid = (l+r) >> 1; f(ls(p),l,mid,tag[p]); f(rs(p),mid+1,r,tag[p]); tag[p] = 0; } inline void update1(ll L,ll R,ll l,ll r,ll p,ll k) { //printf("***\n"); if(L<=l&&r <= R) { t[p].sum+=k*(r - l + 1); t[p].max +=k; t[p].min +=k; tag[p]+=k; return; } push_down(p,l,r); ll mid = (l + r) >> 1; if(L <= mid ) update1(L,R,l,mid,ls(p),k); if(R > mid) update1(L,R,mid+1,r,rs(p),k); push_up(p); } inline void update2(ll p,ll l,ll r,ll k,ll tar) { if(r == l) { t[p].min = k; t[p].max = k; t[p].sum = k; return; } ll mid = (l + r) >> 1; push_down(p,l,r); if(tar > mid ) update2(rs(p),mid + 1,r,k,tar); else update2(ls(p),l,mid,k,tar); push_up(p); } ll query1(ll L,ll R,ll l,ll r,ll p) { ll ans = 0; if(L <= l&& r <= R) return t[p].sum; ll mid = (l + r) >> 1; push_down(p,l,r); if(L <= mid) ans +=query1(L,R,l,mid,ls(p)); if(R > mid) ans +=query1(L,R,mid+1,r,rs(p)); return ans; } ll query2(ll L,ll R,ll l,ll r,ll p) { if(L <= l && r <= R) { return t[p].max; } push_down(p,l,r); ll ans = - LINF; ll mid = (l + r) >> 1; if(L <= mid) { ans = max(ans,query2(L,R,l,mid,ls(p))); } if(R > mid) { ans = max(ans,query2(L,R,mid + 1,r,rs(p))); } return ans; } ll query3(ll L,ll R,ll l,ll r,ll p) { if(L <= l && r <= R) return t[p].min; push_down(p,l,r); ll ans = LINF; ll mid = (l + r) >> 1; if(L <= mid) ans = min(ans,query3(L,R,l,mid,ls(p))); if(R > mid) ans = min(ans,query3(L,R,mid+1,r,rs(p))); return ans; } int main(int argc, char const *argv[]) { scanf("%lld%lld",&n,&m); for(int i = 1;i <= n;++i) scanf("%lld",&a[i]); char op[4]; ll L,R,k,pos; build(1,1,n); while(m--) { scanf(" %s",op); if(op[1] == '1') { scanf("%lld%lld%lld",&L,&R,&k); update1(L,R,1,n,1,k); } else if(op[1] == '2') { scanf("%lld%lld%lld",&L,&R,&k); k = -k; update1(L,R,1,n,1,k); } else if(op[1] == '3') { scanf("%lld%lld",&pos,&k); update2(1,1,n,k,pos); } else if(op[1] == '4') { scanf("%lld%lld",&L,&R); printf("%lld\n",query2(L,R,1,n,1)); } else if(op[1] == '5') { scanf("%lld%lld",&L,&R); printf("%lld\n",query3(L,R,1,n,1)); } else{ scanf("%lld%lld",&L,&R); printf("%lld\n",query1(L,R,1,n,1)); } } return 0; }
以后千万不能带个错误的线段树板子了