Lightoj 1112 - Curious Robin Hood 【单点改动 + 单点、 区间查询】【树状数组 水题】

1112 - Curious Robin Hood

PDF (English)

Statistics

Forum

Time Limit: 1 second(s)

Memory Limit: 64 MB

Robin Hood likes to loot rich people since he helps the poor people with this money. Instead of keeping all the money together he does another trick. He keeps n sacks where he keeps this money. The sacks are numbered from 0 to n-1 .

Now each time he can he can do one of the three tasks.

1)                  Give all the money of the i ^th sack to the poor, leaving the sack empty.

2)                  Add new amount (given in input) in the i ^th sack.

3)                  Find the total amount of money from i ^th sack to j ^th sack.

Since he is not a programmer, he seeks your help.

Input

Input starts with an integer T (≤ 5) , denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 10 ⁵ ) and q (1 ≤ q ≤ 50000) . The next line contains n space separated integers in the range [0, 1000] . The i ^th integer
denotes the initial amount of money in the i ^th sack (0 ≤ i < n) .

Each of the next q lines contains a task in one of the following form:

1 i Give all the money of the i ^th (0 ≤ i < n) sack to the poor .

2 i v Add money v (1 ≤ v ≤ 1000) to the i ^th (0 ≤ i < n) sack.

3 i j Find the total amount of money from i ^th sack to j ^th sack (0 ≤ i ≤ j < n) .

Output

For each test case, print the case number first. If the query type is 1 , then print the amount of money given to the poor. If the query type is 3 , print the total amount from i ^th to j ^th sack.

Sample Input	Output for Sample Input
1 5 6 3 2 1 4 5 1 4 2 3 4 3 0 3 1 2 3 0 4 1 1	Case 1: 5 14 1 13 2

Notes

Dataset is huge, use faster I/O methods.

题意：给你N个数和M次查询，查询分三种

一，1 i   表示查询i处的值。并把 i 处的值变为0。

二，2 i v 表示将 i 处 值添加 v。

三，3 x y 查询 区间[x, y]的值。

水题。直接用树状数组就能够了，不是必需用线段树。

AC代码：注意下标是从0開始到N-1的

#include <cstdio>

#include <cstring>

#include <queue>

#include <stack>

#include <vector>

#include <cmath>

#include <cstdlib>

#include <algorithm>

#define MAXN 100000+10

#define MAXM 60000+10

#define INF 1000000

#define eps 1e-8

using namespace std;

int N, M;

int C[MAXN<<1];

int k = 1;

int lowbit(int x)

{

    return x & (-x);

}

int sum(int x)

{

    int s = 0;

    while(x > 0)

    {

        s += C[x];

        x -= lowbit(x);

    }

    return s;

}

void update(int x, int d)

{

    while(x <= N)

    {

        C[x] += d;

        x += lowbit(x);

    }

}

void solve()

{

    int x, y, d, op;

    printf("Case %d:\n", k++);

    while(M--)

    {

        scanf("%d", &op);

        if(op == 1)

        {

            scanf("%d", &x);

            x++;

            printf("%d\n", sum(x) - sum(x-1));

            int t = sum(x) - sum(x-1);

            update(x, -t);

        }

        else if(op == 2)

        {

            scanf("%d%d", &x, &d);

            x++;

            update(x, d);

        }

        else

        {

            scanf("%d%d", &x, &y);

            x++, y++;

            printf("%d\n", sum(y) - sum(x-1));

        }

    }

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d%d", &N, &M);

        memset(C, 0, sizeof(C));

        int a;

        for(int i = 1; i <= N; i++)

        {

            scanf("%d", &a);

            update(i, a);

        }

        solve();

    }

    return 0;

}