前缀和-Big Water Problem （牛客）

　　　　链接：https://ac.nowcoder.com/acm/problem/15164

题目描述

给一个数列，会有多次询问，对于每一次询问，会有两种操作：

1：给定两个整数x, y, 然后在原数组的第x位置上加y；

2：给定两个整数l，r，然后输出数组从第l位加到第r位数字的和并换行

输入描述:

第一行有两个整数n, m（1 <= n, m <= 100000）代表数列的长度和询问的次数
第二行n个数字，对于第i个数字a[i]，(0<=a[i]<=100000)。
接下来m行，每一行有三个整数f, x, y。第一个整数f是1或者是2，代表操作类型，如果是1，接下来两个数x,y代表第x的位置上加y，如果是2，则求x到y的和，保证数据合法。

输出描述:

输出每次求和的结果并换行

示例1

输入

复制

10 2

1 2 3 4 5 6 7 8 9 10

1 1 9

2 1 10

输出

复制

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<int,int> pr;

inline int read() {int x=,f=;char c=getchar();while(c!='-'&&(c<''||c>''))c=getchar();if(c=='-')f=-,c=getchar();while(c>=''&&c<='')x=x*+c-'',c=getchar();return f*x;}

const int maxn = 1e6+;

const int inf = 0x3f3f3f3f;

const int mod = 1e8+;

int a[maxn];

int sum[maxn];

int x[maxn];

int y[maxn];

int z[maxn];

int main()

{

    int n,m;

    cin>>n>>m;

    for(int i=;i<=n;i++){

        cin>>a[i];

    }

    sum[]=;

    for(int i=;i<=n;i++){

        sum[i]=sum[i-]+a[i];

    }

    int f,u,v;

    int k=;

    while(m--){

        ll ans=;

        scanf("%d%d%d",&f,&u,&v);

        if(f==){

            y[k]=u;

            z[k]=v;

            k++;

        }

        if(f==){

            for(int i=;i<k;i++){

                if(y[i]<=v&&y[i]>=u){

                    ans+=z[i];

                }

            }

            ans+=sum[v]-sum[u-];

            cout<<ans<<endl;

        }

    }

    return ;

}

巴特西

前缀和-Big Water Problem （牛客）

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章