首页 > > 程序设计 > C/C++ >

bzoj4216 -- 分块

2018-06-17 22:47:14来源：未知阅读 ()

如果没有内存限制，显然树状数组就可以了。

有了内存限制，我们使用分块。

因为没有修改操作，所以可以每16个数分一个块。

时间复杂度O(16*n)

注意不要用using namespace std，会占用1M不到的内存

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #define ll long long
 6 #define N 500001
 7 #define M 31251
 8 inline void Read(int& x){
 9     char c=getchar(),b=1;
10     for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
11     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=getchar());x*=b;
12 }
13 inline void Read(bool& x){
14     char c=getchar();
15     for(;c<'0'||c>'9';c=getchar());
16     for(x=0;c>='0'&&c<='1';x=c-48,c=getchar());
17 }
18 char ss[30];
19 int Len;
20 inline void Print(ll x){
21     if(x<0)putchar('-'),x=-x;
22     if(x==0)putchar(48);
23     for(Len=0;x;x/=10)ss[++Len]=x%10;
24     while(Len)putchar(ss[Len--]+48);putchar('\n');
25 }
26 ll Sum[M],Ans;
27 int a[N],Cnt,s,n,m,x,y,i,t;
28 bool f;
29 inline void Query(int l,int r){
30     if(l>>4>=(r>>4)-1){
31         for(;l<=r;l++)Ans+=a[l];
32         return;
33     }
34     Ans+=Sum[(r>>4)-1]-Sum[l>>4];
35     for(i=l;i>>4==l>>4&&i<=n;i++)Ans+=a[i];
36     for(i=r;i>>4==r>>4&&i;i--)Ans+=a[i];
37 }
38 int main(){
39     Read(n);Read(m);Read(f);
40     for(i=1;i<=n;i++)Read(a[i]),Sum[i>>4]+=a[i];
41     for(i=1;i<=n>>4;i++)Sum[i]+=Sum[i-1];
42     while(m--){
43         Read(x);Read(y);
44         if(f){
45             if(Ans<0)Ans=-Ans;
46             x=(Ans^x)%n+1;y=(Ans^y)%n+1;
47             if(x>y)t=x,x=y,y=t;
48         }
49         Ans=0;Query(x,y);
50         Print(Ans);
51     }
52     return 0;
53 }