首页 > 代码库 > hdu 4267 A Simple Problem with Integers
hdu 4267 A Simple Problem with Integers
题目链接：hdu 4267 A Simple Problem with Integers
类似于题目：hdu 1556 Color the ball 的技巧实现树状数组的段更新点查询。
由于该题对于段的更新并不是连续的，从而可以构造多个树状数组。因为$k \in [1,10] $，从而可以把更新划分为如下类型：
1,2,3,4,5...
-------------
1,3,5,7,9...
2,4,6,8,10...
-------------
1,4,7,10,13...
2,5,8,11,14...
3,6,9,12,15...
-------------
...
一共55棵树状数组。对于每一种更新，相应的更新该类型对应的树状数组。
在查询时，同样寻找符合该查询类型的树状数组并最终加上初始值即可完成。
代码如下：
1 #include <cstdlib> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define MAXN 50005 6 using namespace std; 7 int bit[12][12][MAXN]; 8 int arr[MAXN]; 9 int N;10 int lowbit(int x)11 {12 return x&(-x);13 }14 int query(int a, int b, int l)15 {16 int sum = 0; 17 while( l > 0 )18 {19 sum += bit[a][b][l];20 l -= lowbit(l);21 }22 return sum;23 }24 void add(int a, int b, int l, int x)25 {26 while( l <= N )27 {28 bit[a][b][l] += x;29 l += lowbit(l);30 }31 }32 int main(int argc, char *argv[])33 {34 while(scanf("%d", &N)!= EOF)35 {36 memset(bit, 0, sizeof(bit));37 for( int i = 1 ; i <= N ; i++ )38 {39 scanf("%d", &arr[i]);40 }41 int Q;42 scanf("%d", &Q);43 for( int i = 0 ; i < Q ; i++ )44 {45 int ty;46 scanf("%d", &ty);47 if( ty == 1 )48 {49 int a, b, k, c;50 scanf("%d%d%d%d", &a, &b, &k, &c);51 add(k, a%k, a, c);52 add(k, a%k, b+1, -c);53 }54 if( ty == 2 )55 {56 int l;57 scanf("%d", &l);58 int ans = arr[l];59 for( int i = 1 ; i <= 10 ; i++ )60 {61 ans += query(i, l%i, l);62 }63 printf ( "%d\n", ans ); 64 }65 }66 }67 return 0;68 }
hdu 4267 A Simple Problem with Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。