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

正文索引 [隐藏]

题目描述:

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