題意:
? ? ?給你N個數(shù),q組操作,操作有兩種,查詢和改變,查詢就是查詢當前的這個數(shù)上有多少,更改是給你a b k c,每次從a到b,每隔k的數(shù)更改一次,之間的數(shù)不更改,就相當于跳著更新.

思路:(別人的)

? ? ? ? ? ? ?(i - a) % k == 0 等價于 i % k == a % k 一共有10中情況
? 還有枚舉所有情況中的小情況
? ?(1)1 2 3 4 5 6 7 8 9.....
? ?(2)1 3 5 7 9 11 13 ......
? ? ? 2 4 6 8 10 12 14......
? ?(3)1 4 7 10 13...
? ? ? 2 5 8 11 14...
? ? ? 3 6 9 12 15...
? ? ? 一共1 + 2 +....+ 10 = 55種
? ? 其實每一個數(shù)字必然在這55種情況中的10種,對于每次更新就是更新這個數(shù)組在這55種情況中的1種,而查詢就是查詢這個數(shù)字的10種情況的和,數(shù)組num[t][key],t是線段樹上的點,key是這55中情況中的一種,對于每一個點a ,key = a % k + k * (k - 1) / 2 ,這樣相當于我們直接建了55棵樹,對于每個區(qū)間更新的時候,我們直接可以用線段樹的短更新,

比如1--5,k = 2,我們直接找到 key = 1 % 2 + 2 * (2 - 1) / 2 = 2,則可以確定的是在第二課樹上,我們把所有1--5的在第二棵樹上的都更新看下上面發(fā)現(xiàn)第2課樹上沒有2,4我們也更新了num[2][2] ,num[4][2],雖然更新了,但在查找的時候永遠不可能查找的到的,同時它把操作變成了連續(xù)的,這樣就可以用線段樹的 段更新點查找模板AC了...

#include<stdio.h>

#include<string.h>#define lson l,mid,t<<1 #define rson mid+1,r,t<<1|1 int num[150000][55]; int aa[50000];void update(int l ,int r ,int t , int a ,int b ,int c ,int key) {if(a <= l && r <= b){num[t][key] += c;return ;}int mid = (l + r) >> 1;if(a <= mid)update(lson ,a ,b ,c ,key);if(b > mid)update(rson ,a ,b ,c ,key);return; }int query(int l ,int r ,int t ,int a) {int ans = 0;for(int i = 1 ;i <= 10 ;i ++)ans += num[t][a % i + i * (i-1) / 2];if(l == r)return ans;int mid = (l + r) >> 1;if(a <= mid)ans += query(lson ,a);elseans += query(rson ,a);return ans; }int main () {int n ,q ,qq ,a ,b ,c ,k;while(~scanf("%d" ,&n)){for(int i = 1 ;i <= n ;i ++)scanf("%d" ,&aa[i]);memset(num ,0 ,sizeof(num));scanf("%d" ,&qq);while(qq--){scanf("%d" ,&q);if(q == 1){scanf("%d %d %d %d" ,&a ,&b ,&k ,&c);update(1 ,n ,1 ,a ,b ,c ,a % k + k * (k - 1) / 2);}else{scanf("%d" ,&a);printf("%d\n" ,aa[a] + query(1 ,n ,1 ,a));}}}return 0; }

總結

以上是生活随笔為你收集整理的hdu4267线段树段更新,点查找,55棵线段树.的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。