Sneakers
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
输出每次询问的答案（请注意答案可能为负数）
Sample Input 1
3 9
1 2 3
q4 1 3
q1 1 3 1
q5 1 3
q2 1 3 1
q6 1 3
q3 1 5
q4 1 3
q5 1 3
q6 1 3
Sample Output 1
3
2
6
5
2
10
Source
2019年集训队选拔赛
思路：线段树的思路，就是多种操作融合在了一起
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <queue>
#define MAXN 300010
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
long long l,r;
long long add;
long long sum;
long long mx;
long long mn;
}tree[MAXN<<2];
long long _max,_min,_ans;
void pushup(long long index)
{
tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum;
tree[index].mx = max(tree[index<<1].mx,tree[index<<1|1].mx);
tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}
void pushdown(long long index)
{
if(tree[index].add){
tree[index<<1].sum += (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add;
tree[index<<1|1].sum +=(tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add;
tree[index<<1].mx += tree[index].add;
tree[index<<1|1].mx += tree[index].add;
tree[index<<1].mn += tree[index].add;
tree[index<<1|1].mn += tree[index].add;
tree[index<<1].add += tree[index].add;
tree[index<<1|1].add += tree[index].add;
tree[index].add = 0;
}
}
void build(long long l,long long r,long long index)
{
tree[index].l = l;
tree[index].r = r;
tree[index].add = 0;
if(l == r)
{
scanf("%lld",&tree[index].sum);
tree[index].mn = tree[index].mx = tree[index].sum;
return ;
}
long long mid = (l+r)>>1;
build(l,mid,index<<1);
build(mid+1,r,index<<1|1);
pushup(index);
}
void updata(long long l,long long r,long long index,long long val){
if(l <= tree[index].l && r >= tree[index].r)
{
tree[index].sum += (tree[index].r-tree[index].l+1)*val;
tree[index].mn += val;
tree[index].mx += val;
tree[index].add += val;
return ;
}
pushdown(index);
long long mid = (tree[index].l+tree[index].r)>>1;
if(l <= mid)
{
updata(l,r,index<<1,val);
}
if(r > mid)
{
updata(l,r,index<<1|1,val);
}
pushup(index);
}
long long query_max(long long l,long long r,long long index)
{
if(l <= tree[index].l && r >= tree[index].r)
{
return tree[index].mx;
}
pushdown(index);
long long mid = (tree[index].l+tree[index].r)>>1;
long long ans = 0;
long long Max = -inf;
long long Min = inf;
if(l <= mid)
{
// ans += query_max(l,r,index<<1);
Max = max(query_max(l,r,index<<1),Max);
// Min = min(query_max(l,r,index<<1),Min);
}
if(r > mid)
{
// ans += query_max(l,r,index<<1|1);
Max = max(query_max(l,r,index<<1|1),Max);
// Min = min(query_max(l,r,index<<1|1),Min);
}
//return ans;
return Max;
//return Min;
}
long long query_add(long long l,long long r,long long index){
if(l <= tree[index].l && r >= tree[index].r)
{
return tree[index].sum;
}
pushdown(index);
long long mid = (tree[index].l+tree[index].r)>>1;
long long ans = 0;
long long Max = -inf;
long long Min = inf;
if(l <= mid)
{
ans += query_add(l,r,index<<1);
// Max = max(query_add(l,r,index<<1),Max);
// Min = min(query_add(l,r,index<<1),Min);
}
if(r > mid)
{
ans += query_add(l,r,index<<1|1);
// Max = max(query_add(l,r,index<<1|1),Max);
// Min = min(query_add(l,r,index<<1|1),Min);
}
return ans;
}
long long query_min(long long l,long long r,long long index)
{
if(l <= tree[index].l && r >= tree[index].r)
{
return tree[index].mn;
}
pushdown(index);
long long mid = (tree[index].l+tree[index].r)>>1;
long long ans = 0;
long long Max = -inf;
long long Min = inf;
if(l <= mid)
{
// ans += query_min(l,r,index<<1);
// Max = max(query_min(l,r,index<<1),Max);
Min = min(query_min(l,r,index<<1),Min);
}
if(r > mid)
{
// ans += query_min(l,r,index<<1|1);
// Max = max(query_min(l,r,index<<1|1),Max);
Min = min(query_min(l,r,index<<1|1),Min);
}
return Min;
}
int main()
{
long long n,m,x,y,z;
char q[10];
while(~scanf("%lld%lld",&n,&m))
{
build(1,n,1);
while(m--)
{
scanf("%s",q);
if(q[1] == '6')
{
scanf("%lld %lld",&x,&y);
printf("%lld
",query_add(x,y,1));
}
else if(q[1] == '1')
{
scanf("%lld %lld %lld",&x,&y,&z);
updata(x,y,1,z);
}
else if(q[1] == '3')
{
scanf("%lld %lld",&x,&y);
long long kk = query_add(x,x,1);
updata(x,x,1,y - kk);
}
else if(q[1] == '4')
{
scanf("%lld %lld",&x,&y);
printf("%lld
",query_max(x,y,1));
}
else if(q[1] == '5')
{
scanf("%lld %lld",&x,&y);
printf("%lld
",query_min(x,y,1));
}
else if(q[1] == '2')
{
scanf("%lld %lld %lld",&x,&y,&z);
updata(x,y,1,-z);
}
}
}
return 0;
}