程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu4267---A Simple Problem with Integers(線段樹)

hdu4267---A Simple Problem with Integers(線段樹)

編輯：C++入門知識

hdu4267---A Simple Problem with Integers(線段樹)

Problem Description
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.

Input
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)

Output
For each test case, output several lines to answer all query operations.

Sample Input

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

Sample Output

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

Source
2012 ACM/ICPC Asia Regional Changchun Online

Recommend
liuyiding | We have carefully selected several similar problems for you: 4276 4274 4273 4272 4270

k<=10, 模k為b的情況一共是55種,所以維護55顆線段樹(或者說55個延遲標記)即可,內存卡的有點緊.

/*************************************************************************
    > File Name: hdu4267.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年02月25日 星期三 18時37分15秒
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair  PLL;

const int N = 50005;
struct node
{
    int l, r;
    int sum;
    int add[55];
}tree[N << 2];

void build (int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;
    for (int i = 0; i < 55; ++i)
    {
        tree[p].add[i] = 0;
    }
    if (l == r)
    {
        scanf("%d", &tree[p].sum);
        return;
    }
    int mid = (l + r) >> 1;
    build (p << 1, l, mid);
    build (p << 1 | 1, mid + 1, r);
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

void pushdown (int p)
{
    int k = 1;
    int b = -1;
    for (int i = 1; i <= 55; ++i)
    {
        if (i > (2 * k + (k - 1) * (k - 2) / 2 - 1))
        {
            ++k;
            b = 0;
        }
        else
        {
            ++b;
        }
        if (tree[p].add[i - 1]) 
        {
            tree[p << 1].add[i - 1] += tree[p].add[i - 1];
            tree[p << 1 | 1].add[i - 1] += tree[p].add[i - 1];
            int m = (tree[p << 1].r - b) / k + 1;
            if (tree[p << 1].l - 1 - b >= 0)
            {
                m -= (tree[p << 1].l - 1 - b) / k + 1;
            }
            tree[p << 1].sum += m * tree[p].add[i - 1];
//          printf("區間[%d,%d] 模%d為%d的有%d個\n", tree[p << 1].l, tree[p << 1].r, k, b, m);
            m = (tree[p << 1 | 1].r - b) / k + 1;
            if ((tree[p << 1 | 1].l - 1 - b) >= 0)
            {
                m -= (tree[p << 1 | 1].l - 1 - b) / k + 1;
            }
            tree[p << 1 | 1].sum += m * tree[p].add[i - 1];
            tree[p].add[i - 1] = 0;
//          printf("區間[%d, %d] 模%d為%d的有%d個\n", tree[p << 1 | 1].l, tree[p << 1 | 1].r, k, b, m);
        }
    }
}

void update (int p, int l, int r, int k, int b, int c)
{
    if (l == tree[p].l && tree[p].r == r)
    {
        int m = (tree[p].r - b) / k + 1;
        if (tree[p].l - 1 - b >= 0)
        {
            m -= (tree[p].l - 1 - b) / k + 1;
        }
        tree[p].sum += m * c;
        int id = k + (k - 1) * (k - 2) / 2 + b - 1;
        tree[p].add[id] += c;
//      printf("區間[%d, %d]模%d為%d的有%d個\n", l, r, k, b, m);
        return;
    }
    pushdown (p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (r <= mid)
    {
        update (p << 1, l, r, k, b, c);
    }
    else if (l > mid)
    {
        update (p << 1 | 1, l, r, k, b, c);
    }
    else
    {
        update (p << 1, l, mid, k, b, c);
        update (p << 1 | 1, mid + 1, r, k, b, c);
    }
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

int query (int p, int pos)
{
    if (tree[p].l == tree[p].r)
    {
        return tree[p].sum;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    pushdown (p);
    if (pos <= mid)
    {
        return query (p << 1, pos);
    }
    else
    {
        return query (p << 1 | 1, pos);
    }
}

int main ()
{
    int n;
    while (~scanf("%d", &n))
    {
        build (1, 1, n);
        int m;
        int op, l, r, k, c;
        scanf("%d", &m);
        while (m--)
        {
            scanf("%d", &op);
            if (op == 2)
            {
                scanf("%d", &l);
                printf("%d\n", query (1, l));
            }
            else
            {
                scanf("%d%d%d%d", &l, &r, &k, &c);
                update (1, l, r, k, l % k, c);
            }
        }
    }
    return 0;
}