HDU 4267 A Simple Problem with Integers

方法参考http://blog.csdn.net/acm_cxlove/article/details/7854526

题目：给出n个数，每次将一段区间内满足(i-l)%k==0 （r>=i>=l） 的数ai增加c
http://acm.hdu.edu.cn/showproblem.php?pid=4267
比较容易往线段树上想的。但是由于更新的是一些离散的点，比较麻烦
可以考虑这些点的共性，总是隔几个，更新一个，那我们把区间内的数关于k的余数分组
这样每次更新的都是其中的一组，而且是连续的。
由于 K比较小，这是本题的突破口，那么关于k的余数情况，最多只有55种。
即如果k=1，则分为1组，k=2分为2组……
一开始傻叉了打算维护55棵线段树，其实也是可以的，更新只需要1棵，查询是10棵，还是可以接受的。
不过只需要在线段树结点维护这55种情况即可。
不过内存比较紧，要把所有的情况压缩一下，不能开10*10的空间。
同样更新只需要一个，最终统计的话，需要遍历所有的K，也就是最多是10.

自己太水了，有些技巧的线段树现在还是想不出，知识量太少了

 

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> # define MAX 51111 # define ll(x) x << 1 # define rr(x) x << 1 | 1 using namespace std;struct node {int l,r,sum,mid;int add[55]; //关于k的余数情况，最多只有55种 }tree[MAX*4]; int a[MAX],n,cnt[11][11];void build (int l,int r,int num) {tree[num].l = l;tree[num].r = r;tree[num].mid = (l + r) >> 1;memset(tree[num].add,0,sizeof(tree[num].add));tree[num].sum = 0;if(l == r)return ;build(l,tree[num].mid ,ll(num));build(tree[num].mid + 1,r,rr(num)); }void up(int num) {tree[num].sum = tree[ll(num)].sum + tree[rr(num)].sum; }void down(int num) {if(tree[num].sum != 0) {tree[ll(num)].sum += tree[num].sum;tree[rr(num)].sum += tree[num].sum;tree[num].sum = 0;for(int i=0; i<55; i++) {tree[ll(num)].add[i] += tree[num].add[i];tree[rr(num)].add[i] += tree[num].add[i];tree[num].add[i] = 0;}} }void update(int l,int r,int num,int mod,int j, int dsum) {if(l <= tree[num].l && r >= tree[num].r) {tree[num].add[cnt[mod][j]] += dsum;tree[num].sum += dsum;return ;}down(num);if(r <= tree[num].mid ) update (l,r,ll(num),mod,j,dsum);else if(l > tree[num].mid) update(l,r,rr(num),mod,j,dsum);else {update(l,tree[num].mid,ll(num),mod,j,dsum);update(tree[num].mid+1,r,rr(num),mod,j,dsum);}up(num); }int query(int num,int j) {if(tree[num].l == tree[num].r) {int tmp = a[tree[num].l];for(int i=1; i<=10; i++) tmp += tree[num].add[cnt[i][j%i]] ;return tmp;}down(num);if(j <= tree[num].mid) return query(ll(num),j);else return query(rr(num),j); }int main() {int i,m;int p,q,r,s,t;int tmp = 0;for(i=1; i<=10; i++)for(int j=0; j<i; j++) cnt[i][j] = tmp++;while(cin >> n) {for(i=1; i<=n; i++) {scanf("%d",&a[i]);}build(1,n,1);cin >> m;for(i=1; i<=m; i++) {scanf("%d",&p);if(p == 2) {scanf("%d",&q);printf("%d\n",query(1,q));}else {scanf("%d%d%d%d",&q,&r,&s,&t);update(q,r,1,s,q % s,t);}}}return 0; }

 

 

总结

以上是生活随笔为你收集整理的HDU 4267 A Simple Problem with Integers的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。