蓝桥杯操作格子（线段树的更新）

一时失言乱红尘 2022-06-13 11:22 149阅读 0赞

##  ##

## 操作格子 ##

## Description ##

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

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

1.修改一个格子的权值，

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

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

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

## Input ##

多组测试数据

第一行2个整数n，m。

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

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

## Output ##

每组测试数据输出有若干行，行数等于p=2或3的操作总数。

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

## Sample Input ![copy.gif][] ##

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

##     ##

## Sample Output ##

6
    3

## HINT ##

数据规模与约定

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

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

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

题解：

线段树的基础操作。。。我居然因为一个脑残问题检查了一个晚上，以此警记

代码：

#include<stdio.h>
    #include<cstring>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    using namespace std;
    struct node
    {
        int l,r;
        int s;
        int maxx;
    };
    node t[4*100005];//线段树数组大小为数据范围的4倍(多了一部分子节点)
    int n,m;
    int a[100005];
    void Build(int l,int r,int num)//递归建树
    {
        t[num].l=l;
        t[num].r=r;
        if(l==r)
        {
            t[num].maxx=a[l];//注意。。是a[l]不是a[num]..因为这个问题出错了一晚上
            t[num].s=a[l];
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
        t[num].maxx=max(t[num*2].maxx,t[num*2+1].maxx);//初始化区间最大值
        t[num].s=t[num*2].s+t[num*2+1].s;//初始化区间和
    }
    void adjust(int num,int p,int x)//调整下标p的值为x
    {
        if(t[num].l==p&&t[num].r==p)//找到节点修改
        {
            t[num].s=x;
            t[num].maxx=x;
            return;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(p<=mid)//下标p在区间的左侧，搜左子树
            adjust(num*2,p,x);
        else
            adjust(num*2+1,p,x);
        t[num].s=t[num*2].s+t[num*2+1].s;//更新数据
        t[num].maxx=max(t[num*2].maxx,t[num*2+1].maxx);
    }
    int Getmaxx(int l,int r,int num)//求区间的最大值
    {
        if(t[num].l==l&&t[num].r==r)//找到该区间，返回
        {
            return t[num].maxx;
        }
        int mid=(t[num].r+t[num].l)/2;
        if(r<=mid)//要搜索的区间在大区间的左侧
            return Getmaxx(l,r,num*2);
        else if(l>mid)//要搜索的区间在大区间的右侧
            return Getmaxx(l,r,num*2+1);
        else//要搜索的区间在中间，分成两段！！重点理解
        return max(Getmaxx(l,mid,num*2),Getmaxx(mid+1,r,num*2+1));
    }
    int Getsum(int l,int r,int num)//获得区间和
    {
        if(t[num].l==l&&t[num].r==r)
        {
            return t[num].s;
        }
        int mid=(t[num].r+t[num].l)/2;
        if(r<=mid)//要搜索的区间在大区间的左侧
            return Getsum(l,r,num*2);
        else if(l>mid)//要搜索的区间在大区间的右侧
            return Getsum(l,r,num*2+1);
        elseelse//要搜索的区间在中间，分成两段
            return Getsum(l,mid,num*2)+Getsum(mid+1,r,num*2+1);
    }
    int main()
    {
        int i,j,k,x,c,d;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            for(i=1;i<=n;i++)
                scanf("%d",&a[i]);
            Build(1,n,1);//建树
            for(i=1;i<=m;i++)
            {
                scanf("%d",&x);
                if(x==1)
                {
                    scanf("%d%d",&c,&d);
                    adjust(1,c,d);
                }
                else if(x==2)
                {
                    scanf("%d%d",&c,&d);
                    printf("%d\n",Getsum(c,d,1));
                }
                else
                {
                    scanf("%d%d",&c,&d);
                    printf("%d\n",Getmaxx(c,d,1));
                }
            }
        }
        return 0;
    }

[copy.gif]: http://acm.wust.edu.cn/image/copy.gif