问题描述

有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

.修改一个格子的权值，

.求连续一段格子权值和，

.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

输入格式

第一行2个整数n，m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。

输出格式

有若干行，行数等于p=2或3的操作总数。

每行1个整数，对应了每个p=2或3操作的结果。

样例输入

样例输出

数据规模与约定

对于20%的数据n <= ，m <= 。

对于50%的数据n <= ，m <= 。

对于100%的数据1 <= n <= ，m <= ， <= 格子权值 <= 。

 #include <stdio.h>

 #define MAX(X,Y) (X)>(Y)?(X):(Y)

 struct node

 {

     int l,r,max,sum;

 }a[];

 //初始化线段树

 void init(int l,int r,int index)

 {

     int mid;

     a[index].l = l;

     a[index].r = r;

     a[index].max = ;

     a[index].sum = ;

     if (l != r)

     {

         mid = (l+r)/;

         init(l,mid,*index);

         init(mid+,r,*index+);

     }

     return ;

 }

 //更新对应点的权值

 void update(int old,int date,int index)

 {

     int mid;

     if (old>=a[index].l && old<=a[index].r)//更新点所在区间的信息

     {

         a[index].max = date;//更新点所在区间的最大值

         a[index].sum = date;//更新点所在区间的和

     }

     if (a[index].l == a[index].r)

         return ;

     mid = (a[index].l + a[index].r)/;

     if (old <= mid)

         update(old,date,*index);

     else

         update(old,date,*index+);

     a[index].sum = a[*index].sum + a[*index+].sum;

     a[index].max = MAX(a[*index].max,a[*index+].max);

     return ;

 }

 //查找区间的最大值

 int find_max(int l,int r,int index)

 {

     int mid;

     if (l==a[index].l && r==a[index].r)

         return a[index].max;

     mid = (a[index].l + a[index].r)/;

     if (l > mid)

         return find_max(l,r,*index+);

     else if (r <= mid)

         return find_max(l,r,*index);

     else

         return MAX(find_max(l,mid,*index),find_max(mid+,r,*index+));

 }

 //求区间和

 int find_sum(int l,int r,int index)

 {

     int mid;

     if (l==a[index].l && r==a[index].r)

         return a[index].sum;

     mid = (a[index].l + a[index].r)/;

     if (l > mid)

         return find_sum(l,r,*index+);

     else if(r <= mid)

         return find_sum(l,r,*index);

     else

         return find_sum(l,mid,*index)+find_sum(mid+,r,*index+);

 }

 int main(void)

 {

     int i;

     int n,m,date,x,y;

     scanf("%d%d",&n,&m);

     init(,n,);

     for (i= ; i<=n ; i ++)

     {

         scanf("%d",&date);

         update(i,date,);//将i替换为date

     }        

     while (m--)

     {

         scanf("%d%d%d",&date,&x,&y);

         switch(date)

         {

             case :

                 update(x,y,);break;//将x替换为y

             case :

                 printf("%d\n",find_sum(x,y,));break;//区间[x,y]的权值和

             case :

                 printf("%d\n",find_max(x,y,));break;//区间[x,y]的最大权值

             default:break;

         }

     }

     return ;

 }