hdu4267线段树段更新,点查找,55棵线段树.

题意:
     给你N个数,q组操作,操作有两种,查询和改变,查询就是查询当前的这个数上有多少,更改是给你a b k c,每次从a到b,每隔k的数更改一次,之间的数不更改,就相当于跳着更新.

思路:(别人的)

             (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种
    其实每一个数字必然在这55种情况中的10种,对于每次更新就是更新这个数组在这55种情况中的1种,而查询就是查询这个数字的10种情况的和,数组num[t][key],t是线段树上的点,key是这55中情况中的一种,对于每一个点a ,key = a % k + k * (k - 1) / 2 ,这样相当于我们直接建了55棵树,对于每个区间更新的时候,我们直接可以用线段树的短更新,

比如1--5,k = 2,我们直接找到 key = 1 % 2 + 2 * (2 - 1) / 2 = 2,则可以确定的是在第二课树上,我们把所有1--5的在第二棵树上的都更新看下上面发现第2课树上没有2,4我们也更新了num[2][2] ,num[4][2],虽然更新了,但在查找的时候永远不可能查找的到的,同时它把操作变成了连续的,这样就可以用线段树的 段更新点查找模板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棵线段树.的全部内容，希望文章能够帮你解决所遇到的问题。

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