方法參考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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。