操作格子

发表于 | 分类于 | 阅读次数:

问题描述

有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。

花了一天学了线段树，还不是很熟，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int sum,l,r,max;
}node[300001];
int find_ans(int x,int y,int i,bool ismax)//返回区间[x,y]的最大值或和
{
    if(x==node[i].l&&y==node[i].r)
        return ismax?node[i].max:node[i].sum;
    int mid=(node[i].l+node[i].r)/2;
    if(x>mid)
        return find_ans(x,y,2*i+1,ismax);
    else if(y<=mid)
        return find_ans(x,y,2*i,ismax);
    else 
        return ismax?max(find_ans(x,mid,2*i,ismax),find_ans(mid+1,y,2*i+1,ismax)):find_ans(x,mid,2*i,ismax)+find_ans(mid+1,y,2*i+1,ismax);
}
void modify(int i,int x,int data)//将data替换线段树的x位置的值，并更新区间最大值和区间和
{
    if(x==node[i].l&&x==node[i].r)
    {
        node[i].sum=data;
        node[i].max=data;
        return;
    }
    else
    {
        int mid=(node[i].l+node[i].r)/2;
        if(x>mid)
            modify(2*i+1,x,data);
        else
            modify(2*i,x,data);
        node[i].max=max(node[i*2].max,node[i*2+1].max);
        node[i].sum=node[i*2].sum+node[i*2+1].sum;
    }
}
void insert(int i,int x,int data)  //将data插入到线段树的x位置
{
    node[i].sum+=data;
    node[i].max=max(data,node[i].max);
    if(node[i].l==node[i].r)
        return;
    int mid=(node[i].l+node[i].r)/2;
    if(x>mid)
        insert(2*i+1,x,data);
    else
        insert(2*i,x,data);
}
void init(int l,int r,int i)//初始化线段树
{
    node[i].l=l;
    node[i].r=r;
    node[i].max=0;
    node[i].sum=0;
    if(l!=r)
    {
        int mid=(l+r)/2;
        init(l,mid,2*i);
        init(mid+1,r,2*i+1);
    }
}
void solve();
int main()
{
    solve();
    return 0;
}
void solve()
{   
    int i,n,m,t,x,y;
    scanf("%d %d",&n,&m);
    init(1,n,1);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&t);
        insert(1,i,t);
    }
    while(m--)
    {
        scanf("%d %d %d",&t,&x,&y);
        if(t==1)
            modify(1,x,y);
        else
            cout<<find_ans(x,y,1,t==3)<<endl;
    }
}

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。