https://blog.csdn.net/keepcoral/article/details/80743559

数列分块入门 1

[分块]入门题目 随笔 第1张

[分块]入门题目 随笔 第2张

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

正确解法：

简单分块，然后区间之外的暴力，区间之内的 lazy 数组标记。

[分块]入门题目 随笔 第3张 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=50000+100;
15 const int M=5000+10;
16 const double PI=acos(-1.0);
17 int n;
18 ll a[N],lazy[10000];
19 int op,l,r,c;
20 vector<ll>buck[10000];
21 int main()
22 {
23     scanf("%d",&n);
24     int b=sqrt(n),m=n;
25     //cout<<b<<endl;
26     for(int i=0;i<n;i++)
27     {
28         scanf("%d",&a[i]);
29         buck[i%b].push_back(a[i]);
30     }
31     while(m--)
32     {
33         scanf("%d %d %d %d",&op,&l,&r,&c);
34         if(op==0)
35         {
36             if(l>0)    l--;
37             while(l<r && l%b!=0)    a[l++]+=c;
38             while(l<r && r%b!=0)    a[--r]+=c;
39             while(l<r)
40             {
41                 int kk=l/b;
42                 lazy[kk]+=c;
43                 l+=b;
44             }
45         }
46         else
47         {
48             r--;
49             printf("%d\n",a[r]+lazy[r/b]);
50         }
51     }
52 
53 
54     return 0;
55 }
View Code

 

 数列分块入门 2

[分块]入门题目 随笔 第5张

[分块]入门题目 随笔 第6张

正确解法：

把所有都存进数组vector里面， 然后排序，如果改变一个分块里面的部分值，就再次对块进行更新。

[分块]入门题目 随笔 第7张 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=50000+100;
15 const int M=5000+10;
16 const double PI=acos(-1.0);
17 int n;
18 ll a[N],lazy[10000];
19 int blo[N];
20 int op,l,r,c,b;
21 vector<ll>buck[10000];
22 void reset(int x)
23 {
24     buck[x].clear();
25     for(int i=(x-1)*b+1;i<=min(x*b,n);i++)
26         buck[x].push_back(a[i]);
27     sort(buck[x].begin(),buck[x].end());
28 }
29 void add(int l,int r,int c)
30 {
31     for(int i=l;i<=min(blo[l]*b,r);i++)
32         a[i]+=c;
33     reset(blo[l]);
34     if(blo[l]!=blo[r])
35     {
36         for(int i=(blo[r]-1)*b+1;i<=r;i++)
37             a[i]+=c;
38         reset(blo[r]);
39     }
40     for(int i=blo[l]+1;i<=blo[r]-1;i++)
41         lazy[i]+=c;
42 }
43 int query(int l,int r,int c)
44 {
45     int ans=0;
46     for(int i=l;i<=min(blo[l]*b,r);i++)
47         if(a[i]+lazy[blo[l]]<c) ans++;
48     if(blo[l]!=blo[r])
49     {
50         for(int i=(blo[r]-1)*b+1;i<=r;i++)
51             if(a[i]+lazy[blo[r]]<c) ans++;
52     }
53     for(int i=blo[l]+1;i<=blo[r]-1;i++)
54         ans+=lower_bound(buck[i].begin(),buck[i].end(),c-lazy[i])-buck[i].begin();
55     return ans;
56 }
57 int main()
58 {
59     scanf("%d",&n);
60     b=sqrt(n);
61     for(int i=1;i<=n;i++)
62     {
63         scanf("%lld",&a[i]);
64         blo[i]=(i-1)/b+1;
65         buck[blo[i]].push_back(a[i]);
66     }
67     for(int i=1;i<=blo[n];i++)
68         sort(buck[i].begin(),buck[i].end());
69     for(int i=1;i<=n;i++)
70     {
71         scanf("%d %d %d %d",&op,&l,&r,&c);
72         if(op==0)   add(l,r,c);
73         else
74             printf("%d\n",query(l,r,c*c));
75     }
76 
77 
78     return 0;
79 }
View Code

 

数列分块入门 3

[分块]入门题目 随笔 第9张

[分块]入门题目 随笔 第10张

正确解法：

这个需要找相对应的元素，而不是元素个数，就用到了set。

[分块]入门题目 随笔 第11张 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=100000+100;
15 const int M=5000+10;
16 const double PI=acos(-1.0);
17 int n;
18 ll a[N],lazy[10000];
19 int blo[N];
20 int op,l,r,c,m;
21 set<ll>buck[10000];
22 void reset(int x)
23 {
24     buck[x].clear();
25     for(int i=(x-1)*m+1;i<=min(x*m,n);i++)
26         buck[x].insert(a[i]);
27 }
28 void add(int l,int r,int c)
29 {
30     for(int i=l;i<=min(blo[l]*m,r);i++)
31         a[i]+=c;
32     reset(blo[l]);
33     if(blo[l]!=blo[r])
34     {
35         for(int i=(blo[r]-1)*m+1;i<=r;i++)
36             a[i]+=c;
37         reset(blo[r]);
38     }
39     for(int i=blo[l]+1;i<=blo[r]-1;i++)
40         lazy[i]+=c;
41 }
42 ll query(int l,int r,int c)
43 {
44     ll kk=-1;
45     for(int i=l;i<=min(blo[l]*m,r);i++)
46         if(a[i]+lazy[blo[l]]<c)
47             kk=max(kk,a[i]+lazy[blo[l]]);
48     if(blo[l]!=blo[r])
49     {
50         for(int i=(blo[r]-1)*m+1;i<=r;i++)
51             if(a[i]+lazy[blo[r]]<c)
52                 kk=max(kk,a[i]+lazy[blo[r]]);
53     }
54     for(int i=blo[l]+1;i<=blo[r]-1;i++)
55     {
56         set<ll>::iterator it;
57         it=buck[i].lower_bound(c-lazy[i]);
58         if(it==buck[i].begin()) continue;
59         it--;
60         kk=max(kk,(*it)+lazy[i]);
61     }
62     return kk;
63 }
64 int main()
65 {
66     scanf("%d",&n);
67     m=sqrt(n);
68     for(int i=1;i<=n;i++)
69     {
70         scanf("%lld",&a[i]);
71         blo[i]=(i-1)/m+1;
72         buck[blo[i]].insert(a[i]);
73     }
74     for(int i=1;i<=n;i++)
75     {
76         scanf("%d %d %d %d",&op,&l,&r,&c);
77         if(op==0)   add(l,r,c);
78         else
79             printf("%lld\n",query(l,r,c));
80     }
81 
82 
83     return 0;
84 }
View Code

 

数列分块入门 4

[分块]入门题目 随笔 第13张

[分块]入门题目 随笔 第14张

正确解法：

开一个sum数组就好了，注意的是 整个块相加是 sum[i]+lazy[i]*m；

[分块]入门题目 随笔 第15张 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=100000+100;
15 const int M=5000+10;
16 const double PI=acos(-1.0);
17 int n;
18 ll a[N],lazy[10000],sum[10000];
19 int blo[N];
20 int op,l,r,c,m;
21 set<ll>buck[10000];
22 void reset(int x)
23 {
24     buck[x].clear();
25     for(int i=(x-1)*m+1;i<=min(x*m,n);i++)
26         buck[x].insert(a[i]);
27 }
28 void add(int l,int r,int c)
29 {
30     for(int i=l;i<=min(blo[l]*m,r);i++)
31         a[i]+=c;
32     sum[blo[l]]+=(min(blo[l]*m,r)-l+1)*c;
33     //reset(blo[l]);
34     if(blo[l]!=blo[r])
35     {
36         for(int i=(blo[r]-1)*m+1;i<=r;i++)
37             a[i]+=c;
38         sum[blo[r]]+=(r-(blo[r]-1)*m)*c;
39         //reset(blo[r]);
40     }
41     for(int i=blo[l]+1;i<=blo[r]-1;i++)
42         lazy[i]+=c;
43 }
44 ll query(int l,int r,int c)
45 {
46     ll ans=0;
47     for(int i=l;i<=min(blo[l]*m,r);i++)
48         ans+=(a[i]+lazy[blo[l]])%c;
49     ans%=c;
50     if(blo[l]!=blo[r])
51     {
52         for(int i=(blo[r]-1)*m+1;i<=r;i++)
53             ans+=(a[i]+lazy[blo[r]])%c;
54         ans%=c;
55     }
56     for(int i=blo[l]+1;i<=blo[r]-1;i++)
57     {
58         ans+=(sum[i]+lazy[i]*m)%c;
59         ans%=c;
60     }
61     return ans;
62 }
63 int main()
64 {
65     scanf("%d",&n);
66     m=sqrt(n);
67     for(int i=1;i<=n;i++)
68     {
69         scanf("%lld",&a[i]);
70         blo[i]=(i-1)/m+1;
71         buck[blo[i]].insert(a[i]);
72         sum[blo[i]]+=a[i];
73     }
74     for(int i=1;i<=n;i++)
75     {
76         scanf("%d %d %d %d",&op,&l,&r,&c);
77         if(op==0)   add(l,r,c);
78         else
79             printf("%lld\n",query(l,r,c+1));
80     }
81 
82 
83     return 0;
84 }
View Code

 

数列分块入门 5

[分块]入门题目 随笔 第17张

[分块]入门题目 随笔 第18张

正确解法：

每个数最终都会变成0或1，我们暴力每个块，若它的最大值小于等于1，就不必再更新，否则就暴力更新。

[分块]入门题目 随笔 第19张 
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=100000+100;
15 const int M=5000+10;
16 const double PI=acos(-1.0);
17 int n;
18 ll a[N],lazy[10000],sum[10000],maxx[10000];
19 int blo[N];
20 int op,l,r,c,m;
21 set<ll>buck[10000];
22 void reset(int x)
23 {
24     buck[x].clear();
25     for(int i=(x-1)*m+1;i<=min(x*m,n);i++)
26         buck[x].insert(a[i]);
27 }
28 void rset(int x)
29 {
30     sum[x]=0;
31     maxx[x]=0;
32     for(int i=(x-1)*m+1;i<=min(x*m,n);i++)
33     {
34         sum[x]+=a[i];
35         maxx[x]=max(maxx[x],a[i]);
36     }
37 }
38 void add(int l,int r,int c)
39 {
40     for(int i=l;i<=min(blo[l]*m,r);i++)
41         a[i]=sqrt(a[i]);
42     rset(blo[l]);
43     //reset(blo[l]);
44     if(blo[l]!=blo[r])
45     {
46         for(int i=(blo[r]-1)*m+1;i<=r;i++)
47             a[i]=sqrt(a[i]);
48         rset(blo[r]);
49         //reset(blo[r]);
50     }
51     for(int i=blo[l]+1;i<=blo[r]-1;i++)
52         if(maxx[i]>1)
53         {
54             for(int j=(i-1)*m+1;j<=i*m;j++)
55                 a[j]=sqrt(a[j]);
56             rset(i);
57         }
58 }
59 ll query(int l,int r,int c)
60 {
61     ll ans=0;
62     for(int i=l;i<=min(blo[l]*m,r);i++)
63         ans+=a[i];
64     if(blo[l]!=blo[r])
65     {
66         for(int i=(blo[r]-1)*m+1;i<=r;i++)
67             ans+=a[i];
68     }
69     for(int i=blo[l]+1;i<=blo[r]-1;i++)
70     {
71         ans+=sum[i];
72     }
73     return ans;
74 }
75 int main()
76 {
77     scanf("%d",&n);
78     m=sqrt(n);
79     for(int i=1;i<=n;i++)
80     {
81         scanf("%lld",&a[i]);
82         blo[i]=(i-1)/m+1;
83         sum[blo[i]]+=a[i];
84         maxx[blo[i]]=2;
85     }
86     for(int i=1;i<=n;i++)
87     {
88         scanf("%d %d %d %d",&op,&l,&r,&c);
89         if(op==0)   add(l,r,c);
90         else
91             printf("%lld\n",query(l,r,c));
92     }
93 
94 
95     return 0;
96 }
View Code

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄