专栏首页Don的成长史【蓝桥杯】ALGO-8 操作格子

【蓝桥杯】ALGO-8 操作格子

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/102982426

题目描述:

有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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HBU-DS2018SY-1-1 数组循环左移 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 数字颠倒(C++ reverse的练习)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT乙级】A + B和C

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【每日算法Day 83】邻居小孩一年级就会的乘法表,你会吗?

    给定高度 、宽度 的一张 的乘法表,以及正整数 ,你需要返回表中第 小的数字。

    godweiyang
  • 有关vector的存图用法

    用户7727433
  • LeetCode 7. 整数反转

    假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

    freesan44
  • bitmap算法的PHP实现,快速去重排序,数据压缩储存

    因为电路的逻辑只有0和1两个状态,这里的0和1并不是数字的0和1,0和1是表示两种不同的状态,0表示低电平,1表示高电平。因为计算机是由无数个逻辑电路组成的,只...

    宣言言言
  • 简易却高效的hashmap实现

    我们每天都在使用HashMap,有没有想过,在很多情景下,HashMap做的其实没有特别好,他是一个很通用的k-v数据结构,却不一定在各个小方面都适合.因此我们...

    呼延十
  • 【USACO 1.5】Prime Palindromes

    饶文津
  • 算法笔记(0001) - 【动态规划】图像压缩问题

    在计算机中,常用像素点的灰度值序列{p1,p1,……pn}表示图像。其中整数pi,1<=i<=n,表示像素点i的灰度值。通常灰度值的范围是0-255。因此需要8...

    YINUXY

扫码关注云+社区

领取腾讯云代金券