hdu4267---A Simple Problem with Integers(线段树) - c++编程基础

TOP

hdu4267---A Simple Problem with Integers(线段树)

2015-07-20 17:15:21 来源: 作者: 【大中小】浏览:2次

Tags：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: zchao1995@gmail.com 
    > 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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：ZOJ 3640 Help Me Escape 概率dp	下一篇：c++多线程与POSIX多线程性能比较

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: