acwing 242. 一个简单的整数问题

2021-01-19 09:12

阅读：590

标签：span printf 地址 com typedef iostream stream 差分 ret

地址 https://www.acwing.com/problem/content/248/

给定长度为N的数列A，然后输入M行操作指令。

第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。

第二类指令形如“Q X”，表示询问数列中第x个数的值。

对于每个询问，输出一个整数表示答案。

输入格式

第一行包含两个整数N和M。

第二行包含N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$1 \leq N, M \leq 10^{5}$

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

输出样例：

区间修改单点询问利用差分的树状数组

#include 
#include 
#include 


using namespace std;

const int N = 100010;

typedef long long ll;
typedef long long LL;

int n, m;
int a[N];
ll tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c)
{
    for (int i = x; i  c;
}


ll sum(int x)
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i "%d", &a[i]);

    for (int i = 1; i 1]);

    while (m--) {
        char op[2];
        int l, r, d;
        scanf("%s%d",op,&l);

        if (*op == ‘C‘) {
            scanf("%d%d", &r, &d);
            add(l, d); add(r + 1, -d);
        }
        else {
            printf("%lld\n",sum(l));
        }
    }

    return 0;
}

acwing 242. 一个简单的整数问题

标签：span printf 地址 com typedef iostream stream 差分 ret

原文地址：https://www.cnblogs.com/itdef/p/12163355.html

上一篇：Win10企业版精简版缺少mstsc远程桌面的解决

下一篇：wpf及mvvmlight学习备忘

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：acwing 242. 一个简单的整数问题
文章链接：http://soscw.com/index.php/essay/44011.html

亲，登录后才可以留言！

acwing 242. 一个简单的整数问题

输入格式

输出格式

数据范围

输入样例：

输出样例：

评论

热门文章

推荐文章

最新文章

置顶文章