当前位置:首页 > > 充电吧
[导读]问题描述 有n个格子,从左到右放成一排,编号为1-n。 共有m次操作,有3种操作类型: 1.修改一个格子的权值, 2.求连续一段格子权值和, 3.求连续一段格子的最大值。 对于每个2、3

问题描述

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

共有m次操作,有3种操作类型:

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

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

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操作的结果。

样例输入 4 3
1 2 3 4
2 1 3
1 4 3
3 1 4 样例输出 6
3 数据规模与约定

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

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

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

自己感觉这个问题有点像士兵杀敌问题,当初自己想到了树状数组,但是在求最值问题似乎不能成功,后来只能用到线段树,代码自己不会写,java的更不会,先用C语言尝试了下,做了半天没有成功,编译成功的代码是基于数据结构专题--线段树,感谢你。

#include 
#include 
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 4000000;
int MAX[maxn<<2];
int sum[maxn<<2];
void PushUP(int rt)
{
    MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt) {
    if (l == r) {
        scanf("%d",&MAX[rt]);
        sum[rt]=MAX[rt];
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt)
{
    if (l == r)
    {
        MAX[rt] = sc;
        sum[rt] = sc;
        return ;
    }
    int m = (l + r) >> 1;
    if (p <= m)
    update(p , sc , lson);
    else
    update(p , sc , rson);
    PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
    if (L <= l && r <= R) {
        return MAX[rt];
    }
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret = max(ret , query(L , R , lson));
    if (R > m) ret = max(ret , query(L , R , rson));
    return ret;
}
int querysum(int L,int R,int l,int r,int rt)
{
    if( L <= l && r <= R )
    {
        return sum[rt];
    }
    int m = ( l + r ) >> 1;
    int ans=0;
    if(L<=m )
        ans+=querysum(L,R,lson);
    if(R>m)
        ans+=querysum(L,R,rson);

    return ans;
}
int main()
{
   int n , m;
   int s_val,ss_val;
   FILE *fp;
    scanf("%d%d",&n,&m);
    {
        build(1 , n , 1);
        while (m --)
        {
            int op;
            int a , b;
            scanf("%d %d %d",&op,&a,&b);
            if (op==1)
            {
                 update(a , b , 1 , n , 1);
            }
            else if(op==2)
            {
                    printf("%dn",querysum(a,b,1,n,1));
            }
            else if(op==3)
            {
                    printf("%dn",query(a,b,1,n,1));
            }
        }
    }
    return 0;
}










本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

LED驱动电源的输入包括高压工频交流(即市电)、低压直流、高压直流、低压高频交流(如电子变压器的输出)等。

关键字: 驱动电源

在工业自动化蓬勃发展的当下,工业电机作为核心动力设备,其驱动电源的性能直接关系到整个系统的稳定性和可靠性。其中,反电动势抑制与过流保护是驱动电源设计中至关重要的两个环节,集成化方案的设计成为提升电机驱动性能的关键。

关键字: 工业电机 驱动电源

LED 驱动电源作为 LED 照明系统的 “心脏”,其稳定性直接决定了整个照明设备的使用寿命。然而,在实际应用中,LED 驱动电源易损坏的问题却十分常见,不仅增加了维护成本,还影响了用户体验。要解决这一问题,需从设计、生...

关键字: 驱动电源 照明系统 散热

根据LED驱动电源的公式,电感内电流波动大小和电感值成反比,输出纹波和输出电容值成反比。所以加大电感值和输出电容值可以减小纹波。

关键字: LED 设计 驱动电源

电动汽车(EV)作为新能源汽车的重要代表,正逐渐成为全球汽车产业的重要发展方向。电动汽车的核心技术之一是电机驱动控制系统,而绝缘栅双极型晶体管(IGBT)作为电机驱动系统中的关键元件,其性能直接影响到电动汽车的动力性能和...

关键字: 电动汽车 新能源 驱动电源

在现代城市建设中,街道及停车场照明作为基础设施的重要组成部分,其质量和效率直接关系到城市的公共安全、居民生活质量和能源利用效率。随着科技的进步,高亮度白光发光二极管(LED)因其独特的优势逐渐取代传统光源,成为大功率区域...

关键字: 发光二极管 驱动电源 LED

LED通用照明设计工程师会遇到许多挑战,如功率密度、功率因数校正(PFC)、空间受限和可靠性等。

关键字: LED 驱动电源 功率因数校正

在LED照明技术日益普及的今天,LED驱动电源的电磁干扰(EMI)问题成为了一个不可忽视的挑战。电磁干扰不仅会影响LED灯具的正常工作,还可能对周围电子设备造成不利影响,甚至引发系统故障。因此,采取有效的硬件措施来解决L...

关键字: LED照明技术 电磁干扰 驱动电源

开关电源具有效率高的特性,而且开关电源的变压器体积比串联稳压型电源的要小得多,电源电路比较整洁,整机重量也有所下降,所以,现在的LED驱动电源

关键字: LED 驱动电源 开关电源

LED驱动电源是把电源供应转换为特定的电压电流以驱动LED发光的电压转换器,通常情况下:LED驱动电源的输入包括高压工频交流(即市电)、低压直流、高压直流、低压高频交流(如电子变压器的输出)等。

关键字: LED 隧道灯 驱动电源
关闭