首页 > ACM题库 > HDU-杭电 > HDU 4267-A Simple Problem with Integers-树状数组-[解题报告]HOJ
2015
05-23

HDU 4267-A Simple Problem with Integers-树状数组-[解题报告]HOJ

A Simple Problem with Integers

问题描述 :

Let A1, A2, … , AN be N elements. You need to deal with two kinds of operations. One type of operation is to add a given number to a few numbers in a given interval. The other is to query the value of some element.

输入:

There are a lot of test cases.
The first line contains an integer N. (1 <= N <= 50000)
The second line contains N numbers which are the initial values of A1, A2, … , AN. (-10,000,000 <= the initial value of Ai <= 10,000,000)
The third line contains an integer Q. (1 <= Q <= 50000)
Each of the following Q lines represents an operation.
"1 a b k c" means adding c to each of Ai which satisfies a <= i <= b and (i – a) % k == 0. (1 <= a <= b <= N, 1 <= k <= 10, -1,000 <= c <= 1,000)
"2 a" means querying the value of Aa. (1 <= a <= N)

输出:

There are a lot of test cases.
The first line contains an integer N. (1 <= N <= 50000)
The second line contains N numbers which are the initial values of A1, A2, … , AN. (-10,000,000 <= the initial value of Ai <= 10,000,000)
The third line contains an integer Q. (1 <= Q <= 50000)
Each of the following Q lines represents an operation.
"1 a b k c" means adding c to each of Ai which satisfies a <= i <= b and (i – a) % k == 0. (1 <= a <= b <= N, 1 <= k <= 10, -1,000 <= c <= 1,000)
"2 a" means querying the value of Aa. (1 <= a <= N)

样例输入:

4 
1 1 1 1
14
2 1
2 2
2 3
2 4
1 2 3 1 2
2 1 
2 2
2 3
2 4
1 1 4 2 1
2 1
2 2
2 3
2 4

样例输出:

1
1
1
1
1
3
3
1
2
3
4
1

http://acm.hdu.edu.cn/showproblem.php?pid=4267

又学到了一点

区间更新 单点查值得树状数组

代码:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
int n;
int num[50005];
int tree[50005][11][11];
int lowbit(int x)
{
    return x&(-x);
}
int update(int mod,int ans,int last,int add)
{
    while(last>0)
    {
        tree[last][mod][ans]+=add;
        last-=lowbit(last);
    }
    //printf("last==%d\n",sign);
    //for(int i=1;i<=10;i++)
    //printf("%d ",tree[i][mod][ans]);
   // printf("~~\n");
}
int solve(int x)
{
    int sum=0;
    int signs=x;
        for(int i=1;i<=10;i++)
        {
            int x=signs;
            while(x<=n)
            {
                sum+=tree[x][i][signs%i];
                x+=lowbit(x);
            }
        }
    return sum;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
        int query;
        scanf("%d",&query);
        while(query--)
        {
            int q;
            scanf("%d",&q);
            if(q==1)
            {
                int left,right,mod,add;
                scanf("%d%d%d%d",&left,&right,&mod,&add);
                update(mod,left%mod,right,add);
                update(mod,left%mod,left-1,-add);
            }
            else
            {
                int x;
                scanf("%d",&x);
                printf("%d\n",solve(x)+num[x]);
            }
        }
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/talak/article/details/7974469