【分块+树状数组】codechef November Challenge 2014 .Chef and Churu

https://www.codechef.com/problems/FNCS

【题意】

【思路】

把n个函数分成√n块，预处理出每块中各个点(n个)被块中函数(√n个)覆盖的次数
查询时求前缀和，对于整块的分块求和，剩下右边不构成完整的一个块的树状数组求和
预处理：计算每个块中，序列中的第i个点被块中函数覆盖的次数，求出每个块内前缀的和（O(n√n)）；对于每个点，更新树状数组（nlogn）
单点修改：对于块状数组，因为已经知道了每个点被覆盖的次数，所以维护很简单（O(√n)）;对于树状数组，直接单点更新（O(logn)）;然后把a[pos]本身的值更新为x
查询：计算前缀和，求x到y之间的函数和就是计算cal(y)-cal(x-1)。对于前缀和，对于整块的直接求和（O(√n)），对于最右边剩下的树状数组查询区间和（最多√n个函数，每个函数logn,所以复杂度为√nlogn）
综上，时间复杂度为O(n√nlogn)
注意要爆long long,1e5*1e5*1e9=1e19,long long 的最大值为9223372036854775807，9e18多一点

【Accepted】

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<cmath>
  6 #include<algorithm> 
  7 
  8 using namespace std;
  9 typedef unsigned long long ull;
 10 const int maxn=1e5+2;
 11 int n,m;
 12 int a[maxn];
 13 int belong[maxn];
 14 int l[400];
 15 int r[400];
 16 ull sum[maxn];
 17 ull tree[maxn];
 18 int vis[400][maxn];
 19 struct Node
 20 {
 21     int l;
 22     int r;
 23 }q[maxn];
 24 
 25 void init()
 26 {
 27     for(int i=1;i<=n;i++)
 28     {
 29         tree[i]=0ull;    
 30     }    
 31 }
 32 
 33 int lowbit(int x)
 34 {
 35     return x&(-x);
 36 }
 37 void add(int k,int x)
 38 {
 39     while(k<=n)
 40     {
 41         tree[k]+=1ull*x;
 42         k+=lowbit(k);
 43     }
 44 }
 45 
 46 ull query(int k)
 47 {
 48     ull res=0ull;
 49     while(k)
 50     {
 51         res+=tree[k];
 52         k-=lowbit(k);
 53     }
 54     return res;
 55  } 
 56 ull query(int l,int r)
 57 {
 58     return query(r)-query(l-1);
 59  } 
 60 ull cal(int x)
 61 {
 62     if(x<1)
 63     {
 64         return 0;
 65     }
 66     int b=belong[x];
 67     ull res=0ull;
 68     for(int i=1;i<b;i++)
 69     {
 70         res+=sum[i];
 71     }
 72     for(int i=l[b];i<=x;i++)
 73     {
 74         res+=query(q[i].l,q[i].r);
 75     }
 76     return res;
 77 }
 78 ull cal(int x,int y)
 79 {
 80     return cal(y)-cal(x-1);
 81 }
 82 int main()
 83 {
 84         scanf("%d",&n);
 85         init();
 86         for(int i=1;i<=n;i++)
 87         {
 88             scanf("%d",&a[i]);                        
 89             add(i,a[i]);
 90         }
 91         int block=sqrt(n);
 92         for(int i=1;i<=n;i++)
 93         {
 94             scanf("%d%d",&q[i].l,&q[i].r);    
 95             belong[i]=(i-1)/block+1;
 96         }    
 97         int cnt=n/block;
 98         if(n%block)
 99         {
100             cnt++;
101         }
102         for(int i=1;i<=cnt;i++)
103         {
104             l[i]=(i-1)*block+1;
105             r[i]=i*block;
106         }    
107         r[cnt]=n;
108         for(int i=1;i<=cnt;i++)
109         {
110             for(int k=l[i];k<=r[i];k++)
111             {
112                 vis[i][q[k].l]++;
113                 vis[i][q[k].r+1]--;
114             }
115             for(int k=1;k<=n;k++)
116             {
117                 vis[i][k]+=vis[i][k-1];
118                 sum[i]+=1ull*vis[i][k]*a[k];
119             }
120         } 
121         scanf("%d",&m);
122         while(m--)
123         {
124             int op;
125             scanf("%d",&op);
126             if(op==1)
127             {
128                 int pos,x;
129                 scanf("%d%d",&pos,&x);
130                 for(int i=1;i<=cnt;i++)
131                 {
132                     sum[i]+=1ull*vis[i][pos]*(x-a[pos]); 
133                 }
134                 add(pos,x-a[pos]);
135                 a[pos]=x;
136             }
137             else
138             {
139                 int x,y;
140                 scanf("%d%d",&x,&y);
141                 ull ans=cal(x,y); 
142                 printf("%llu
",ans);
143             }
144         }
145     
146     return 0;
147 }

分块+树状数组