t0ur1st

题目描述：

有n个格子，从左到右放成一排，编号为1-n。共有m次操作，有3种操作类型：1.修改一个格子的权值；2.求连续一段格子权值和；3.求连续一段格子的最大值。对于每个2、3操作输出你所求出的结果。

输入描述：

第一行2个整数n，m（1 <= n，m <= 100000）。接下来一行n个整数表示n个格子的初始权值。接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。（0 <= 格子权值 <= 10000）。

输出描述：

有若干行，行数等于p=2或3的操作总数。每行1个整数，对应了每个p=2或3操作的结果。

输入样例：

4 3
1 2 3 4
2 1 3
1 4 3
3 1 4

输出样例：

6
3

解题思路：

⽤结构体来构造⼀棵线段树，当p=1时从上到下更新这个线段树的值，当p=2的时候搜索对 应区间内的总和，当p=3的时候搜索对应区间的最⼤值。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
const int maxn = 1000001;
struct node
{
    int l,r,maxvalue,sum;
}a[maxn];
void init(int left,int right,int i)    //初始化
{
    a[i].l = left;
    a[i].r = right;
    a[i].maxvalue = 0;
    a[i].sum = 0;
    if(left != right)
    {
        int mid = (left+right)/2;
        init(left,mid,2*i);
        init(mid+1,right,2*i+1);
    }
}
void insert(int i,int x,int y)  //修改格子x的权值为y
{
    if(a[i].l == a[i].r)
    {
        a[i].maxvalue = y;
        a[i].sum = y;
        return;
    }
    int mid = (a[i].l+a[i].r)/2;
    if(x <= mid)
    {
        insert(2*i,x,y);
    }
    else
    {
        insert(2*i+1,x,y);
    }
    a[i].maxvalue = max(a[2*i].maxvalue,a[2*i+1].maxvalue);
    a[i].sum = a[2*i].sum + a[2*i+1].sum;
}
int findSum(int i,int x,int y)  //求区间[x,y]内格子权值和
{
    if(x==a[i].l && y==a[i].r)
    {
        return a[i].sum;
    }
    int mid = (a[i].l+a[i].r)/2;
    if(y <= mid)
    {
        return findSum(2*i,x,y);
    }
    else if(x > mid)
    {
        return findSum(2*i+1,x,y);
    }
    else
    {
        return findSum(2*i,x,mid)+findSum(2*i+1,mid+1,y);
    }
}
int findMax(int i,int x,int y)  //求区间[x,y]内格子最大的权值
{
    if(x==a[i].l && y==a[i].r)
    {
        return a[i].maxvalue;
    }
    int mid = (a[i].l+a[i].r)/2;
    if(y <= mid)
    {
        return findMax(2*i,x,y);
    }
    else if(x > mid)
    {
        return findMax(2*i+1,x,y);
    }
    else
    {
        return max(findMax(2*i,x,mid),findMax(2*i+1,mid+1,y));
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    init(1,n,1);
    int value;  //n个格子的初始权值
    Up(i,1,n)
    {
        cin >> value;
        insert(1,i,value);
    }
    Up(i,1,m)
    {
        int p,x,y;
        cin >> p >> x >> y;
        switch(p)
        {
            case 1: insert(1,x,y); break;
            case 2: cout << findSum(1,x,y) << endl; break;
            case 3: cout << findMax(1,x,y) << endl; break;
            default: break;
        }
    }
    return 0;
}