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);
   else
   ans += 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
" ,aa[a] + query(1 ,n ,1 ,a));
         }
      }
   }
   return 0;
}

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

相关推荐