浅谈分块——入门

浅谈分块——入门前言在学会分块之前,觉得分块是一个很深奥的东西,很玄学。但其实分块的作用也很广泛,也非常简单,在这里分享一下。分块的定义与分块的基本性质分块,顾名思义,就是将一个数组分成一些小块。而分块有一个基本性质,就是块的大小不会影响答案,只对时间有一定影响。一般有以下三种分块方式:No.1:固定

大家好,欢迎来到IT知识分享网。浅谈分块——入门"

前言

  在学会分块之前,觉得分块是一个很深奥的东西,很玄学。但其实分块的作用也很广泛,也非常简单,在这里分享一下。

分块的定义与分块的基本性质

  分块,顾名思义,就是将一个数组分成一些小块。

       而分块有一个基本性质,就是块的大小不会影响答案,只对时间有一定影响。

       一般有以下三种分块方式:

       No.1: 固定长度分块。

       No.2 : 长度为sqrt(n)

       No.3 : 每块随机长度。

      常用的话一般选择No.1或No.2。

分块

    如果选择No.2的分块方式的话,我们定义以下几个变量:

        

1 block = (int)sqrt(n) //块的长度
2 
3 sum = n / block;
4 if (n % block) sum++;//块数
5 
6 p[i] = (i - 1) / block + 1;//第i个元素在第几块中

  这几个变量十分有用,在后文中会讲到。

       以上是分块的初始化。

       下面我们来讲对于查询怎么对付,

       对于区间查询,有三种情况:

       1:询问区间[x,y]中x不是块的左边界,y也不是块的右边界。

       2:询问区间[x,y]中x不是块的左边界,y也是块的右边界。

       3:询问区间[x,y]中x是块的左边界,y也不是块的右边界。

       我们发现,对于比较普通的1情况可以把询问区间分成3个部分:

       左边多出来的、中间的k块、右边多出来的。

       可以发现,对于一块来说查询是O(1)的(因为我可以预处理每一块的值)

       对于多出来的边角料部分总和不足2*sqrt(n),基于这个时间复杂度,我们可以进行暴力求解。

       所以可以发现对于1操作查询的总复杂度(一共有n次操作)为O(n*sqrt(n))。

       对于2、3情况,我们可以将这些情况当成1情况来处理。

       代码展示:

       

 1 for (int i = x; i <= min(y,p[x] * block); i++)//处理左边角料
 2 //do something
 3 
 4  for (int i = (p[y] - 1) * block + 1; i <= y; i++)//处理右边角料
 5  //do something
 6 
 7 for(int i = p[x] + 1; i <= p[y] - 1; i++)//处理中间k块
 8  //do something
 9 
10 //这里特别注意一下,对于一个块的左边界,我们可以求出上一个块的右边界(p[x] - 1)*block,+1后就是这个块的左边界。

      现在我们来讲一下修改操作。

      跟查询操作一样,我们也可以分成3部分,对于边角料暴力修改a[i],对于一块,我们修改这一块的值A[p[i]]

      总时间复杂度为O(n*sqrt(n))。

      代码展示:

      

for (int i = x; i <= min(y,p[x] * block); i++)//处理左边角料
  change(a[i]);

for (int i = (p[y] - 1) * block + 1; i <= y; i++)//处理右边角料
  change(a[i])

for(int i = p[x] + 1; i <= p[y] - 1; i++)//处理中间k块
  change(A[i]);//这里的i已经是块号了,所以修改的是A[i],与讲解的不太一样

      对于预处理,我们发现即使每个块暴力进行对于A[i]的预处理,时间复杂度也只有O(n),

      所以预处理就块内暴力求解。

      代码展示:

      

void work(int x,int y,int t)
{
    int st = 0;
    for (int i = x; i <= y; i++)
         //do something with st
     A[t] = st;
}

for (int i = 1; i <= sum; i++)//一共sum块
  work((p[i] - 1) * block + 1,p[i] * block,i);//传入块的左右边界和编号

几种常用的(入门)模板

  1:区间加法,单点求和。(loj6277)

   预处理时求得每个块内的和,修改时对于边角料暴力修改值。

    对于中间的k块,修改加法标记addtag[i],表示第i个块加上了addtag[i]。

    对于询问,我们要记下对于一个块一共加上了多少(记在addtag里),最后输出a[i] + addtag[p[i]]

    完整代码展示:

    

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int block,sum,Ans[50005],p[50005],n,m,Add[50005];
 5 int a[50005];
 6 inline void work(int as,int bs,int x)
 7 {
 8     int st = 0;
 9     for (int i = as; i <= bs; i++)
10       st += a[i];
11     Ans[x] = st;
12 }
13 inline int read(){
14    int s=0,w=1;
15    char ch=getchar();
16    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
17    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
18    return s*w;
19 }
20 signed main(){
21     scanf("%lld",&n);
22     block = (int)sqrt(n);
23     sum = n / block;
24     if (n % block) sum++;
25     for (int i = 1; i <= n; i++)
26     {
27         //scanf("%lld",&a[i]);
28         a[i] = read();
29         p[i] = (i - 1) / block + 1;
30     }
31     for (int i = 1; i <= sum; i++)
32        work((i - 1) * block + 1,i * block,i);//预处理块内和
33     for (int i = 1; i <= n; i++)
34     {
35         int x,y,st = 0,op,k,mp,io;
36         op = read();
37         if (op == 1)
38         {
39           mp = read();
40           x = read();
41           io = read();
42           printf("%lld\n",a[x] + Add[p[x]]);//输出对于a[i]加上了多少
43        } else
44        {
45              x = read();
46              y = read();
47              k = read();
48              for (int j = x; j <= min(p[x] * block,y); j++)
49                a[j] += k;
50              if (p[x] != p[y])
51                for (int j = (p[y] - 1) * block + 1; j <= y; j++)
52                  a[j] += k;
53            for (int j = p[x] + 1; j <= p[y] - 1; j++)
54              Add[j] += k;//这里直接修改加法标记
55        }
56     }
57     return 0;
58 } 

 

2:区间加法,区间求和。(loj6280)

 

 

  预处理时求得每个块内的和,修改时对于边角料暴力修改值,修改了a[i]的值,也要把a[i]所在块的值修改。

    对于中间的k块,修改加法标记addtag[i],表示第i个块加上了addtag[i]。

    对于询问,我们要记下对于一个块一共加上了多少(记在addtag里),对于边角料同上一个模板一样,暴力+a[i]+addtag[p[i]]

    对于中间的k块加上A[i],因为其中有block个数,所以要+block个addtag[i]

    完整代码展示:

    

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 const long long inf = 66666666233;
 5 int block,sum,Ans[3000005],p[3000005],n,m,Add[3000005];
 6 int a[3000005];
 7 void work(int as,int bs,int x)
 8 {
 9     int st = 0;
10     for (int i = as; i <= bs; i++)
11       st += a[i];
12     Ans[x] = st;
13 }
14 signed main(){
15     scanf("%lld",&n);
16     block = (int)sqrt(n);
17     sum = n / block;
18     if (n % block) sum++;
19     for (int i = 1; i <= n; i++)
20     {
21         scanf("%lld",&a[i]);
22         p[i] = (i - 1) / block + 1;
23     }
24     for (int i = 1; i <= sum; i++)
25        work((i - 1) * block + 1,i * block,i);
26     for (int i = 1; i <= n; i++)
27     {
28         int x,y,st = 0,op,k;
29         scanf("%lld",&op);
30         if (op == 1)
31         {
32           scanf("%lld%lld%lld",&x,&y,&k);
33           for (int j = x; j <= y; j)
34           if ((j - 1) % block || (p[j] * block > y))
35             {     
36                 st +=  Add[p[j]] + a[j];
37                 j++;
38           } else
39           {
40               st += Ans[p[j]] + Add[p[j]] * ((p[j] * block) - ((p[j] - 1) * block + 1) + 1);//加上block个Add[p[j]]
41               j += block;
42           }
43           printf("%lld\n",st % (k + 1));
44        } else
45        {
46              scanf("%lld%lld%lld",&x,&y,&k);
47              for (int j = x; j <= y; j)
48           if ((j - 1) % block || (p[j] * block > y))
49             {     
50                 a[j] += k;
51                 Ans[p[j]] += k;
52                 j++;
53           } else
54           {      
55               Add[p[j]] += k;    
56               j += block;
57           }
58        }
59     }
60     return 0;
61 } 

3:区间开方,区间求和。(loj6281)

  预处理时求得每个块内的和,修改时对于边角料暴力修改值,修改了a[i]的值,也要把a[i]所在块的值修改。

    对于中间的k块,修改总和A[i],表示第i个块减少了。

    对于询问,我们要记下对于一个块一共加上了多少(记在addtag里),边角料暴力+a[i]

    对于中间的k块加上A[i],输出答案。

    完整代码展示:

    

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int block,sum,Ans[50005],p[50005],n,m,Add[50005],tag[500005];
 5 int a[50005];
 6 inline void work(int as,int bs,int x)
 7 {
 8     int st = 0;
 9     for (int i = as; i <= bs; i++)
10       st += a[i];
11     Add[x] += st;
12     //COp[x] = st;
13 }
14 inline int read(){
15    int s=0,w=1;
16    char ch=getchar();
17    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
18    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
19    return s*w;
20 }
21 void push_down(int x){
22     Add[x]=0;
23     int flag=1;
24     for(int i=(x-1)*block+1;i<=min(n,x*block);i++){
25         a[i]=(int)sqrt(a[i]*1.0);
26         Add[x]+=a[i];
27         if(a[i]!=1) flag=0;
28     }
29     tag[x]=flag;
30 }//这里注意一下,对于中间的块要标记下传,重新更新
31 signed main(){
32     scanf("%lld",&n);
33     block = (int)sqrt(n);
34     sum = n / block;
35     if (n % block) sum++;
36     for (int i = 1; i <= n; i++)
37     {
38         a[i] = read();
39         p[i] = (i - 1) / block + 1;
40     }
41     for (int i = 1; i <= sum; i++)
42        work((i - 1) * block + 1,i * block,i);
43     for (int i = 1; i <= n; i++)
44     {
45         int x,y,st = 0,op,k,mp,io;
46         op = read();
47         if (op == 1)
48         {
49           x = read();
50           y = read();
51           mp = read();
52           for (int j = x; j <= min(p[x] * block,y); j++)
53                st += a[j];
54              if (p[x] != p[y])
55              for (int j = (p[y] - 1) * block + 1; j <= y; j++)
56                 st += a[j];
57           for (int j = p[x] + 1; j <= p[y] - 1; j++)
58              st += Add[j];
59           printf("%d\n",st);
60        } else
61        {
62              x = read();
63              y = read();
64              k = read();
65              for (int j = x; j <= min(p[x] * block,y); j++)
66              {
67                  int uy = a[j];
68                a[j] = (int)sqrt(a[j]);
69                Add[p[j]] -= uy - a[j];//开方就等于减少了sqrt(a[i])
70          }
71              if (p[x] != p[y])
72                for (int j = (p[y] - 1) * block + 1; j <= y; j++)
73                   {
74                       int uy = a[j];
75                     a[j] = (int)sqrt(a[j]);
76                        Add[p[j]] -= uy - a[j];
77                 }
78            for (int j = p[x] + 1; j <= p[y] - 1; j++)
79            if (tag[j] == 0) push_down(j);
80       }
81     }
82     return 0;
83 } 

4:区间加法,区间询问小于c2的数。(loj6278、luoguP4145)

  预处理时对于所有块进行快内排序,将未排序的a数组赋值给tlps,修改时对于边角料暴力修改值,修改tlps[i]的值(如果修改的是a的话,因为排过序,会发现位置不对)。

    对于中间的k块,修改A[i]。

    对于询问,边角料暴力判断

    对于中间的k块(对于a数组)lower_bound c^2 – addtag(因为询问所有a + addtag 等价于 c^2 – addtag),得出这个位置,可以发现,这个位置的前面都是符合要求的。

    完整代码展示:

    

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int block,sum,Ans[50005],p[50005],n,m,Add[50005];
 5 int a[50005],tlps[50005];
 6 inline void work(int as,int bs)
 7 {
 8     for (int i = as; i <= bs; i++)
 9          a[i] = tlps[i];
10     sort(a + as,a + bs + 1); 
11 }
12 signed main(){
13     //freopen("a1.in","r",stdin);
14     //freopen("ate.out","w",stdout);
15     memset(Add,0,sizeof(Add));
16     scanf("%lld",&n);
17     block = (int)sqrt(n);
18     sum = n / block;
19     if (n % block) sum++;
20     for (int i = 1; i <= n; i++)
21     {
22         scanf("%lld",&a[i]);
23         tlps[i] = a[i];//注意要复制一份
24         p[i] = (i - 1) / block + 1;
25     }
26     for (int i = 1; i <= sum; i++)
27        work((i - 1) * block + 1,min(i * block,n));
28     for (int i = 1; i <= n; i++)
29     {
30         int x,y,op,k;
31         scanf("%lld",&op);
32         if (op == 1)
33         {
34           scanf("%lld%lld%lld",&x,&y,&k);
35              k = k * k; 
36              int v = 0;
37              for (int j = x; j <= min(p[x] * block,y); j++)
38              if (tlps[j] + Add[p[x]] < k)
39                v++;
40              if (p[x] != p[y])
41                for (int j = (p[y] - 1) * block + 1; j <= y; j++)
42                  if (tlps[j] + Add[p[y]] < k)
43                    v++;
44           for (int j = p[x] + 1; j <= p[y] - 1; j++)
45             v += lower_bound(a + (j - 1) * block + 1,min(a + n,a + j * block + 1),k - Add[j]) - (a + (j - 1) * block + 1);//二分查询
46           printf("%lld\n",v); 
47         } else
48         {
49              scanf("%lld%lld%lld",&x,&y,&k);
50              for (int j = x; j <= min(p[x] * block,y); j++)
51           {
52                tlps[j] += k;//修改的是原数组
53             //a[j] += k;
54           }
55              work((p[x] - 1) * block + 1,min(n,p[x] * block));
56              if (p[x] != p[y])
57              {
58                for (int j = (p[y] - 1) * block + 1; j <= y; j++)
59             {
60                  tlps[j] += k;
61               //a[j] += k;
62             }
63                work((p[y] - 1) * block + 1,min(n,p[y] * block));
64           }
65           for (int j = p[x] + 1; j <= p[y] - 1; j++)
66             Add[j] += k;
67         } 
68     }
69     return 0;
70 }

 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30758.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信