数据结构 — 分块 （学习历程） 连载中......
分类:
IT文章
•
2022-07-19 17:59:14
- 区间加法 单点查值
- 把每m个元素分为一块，共有n/m块，每次区间加的操作会涉及O(n/m)个整块，以及区间两侧两个不完整的块中至多2m个元素。
- 我们给每个块设置一个加法标记 atage（记录这个块中元素一起加了多少），每次操作对每个整块直接O(1)标记，而不完整的块由于元素比较少，暴力修改元素的值。每次询问时返回元素的值加上其所在块的加法标记。
- 这样每次操作的复杂度是O(n/m)+O(m)，根据均值不等式，当m取√n时总复杂度最低。
![]()
1 #include<cstdio>
2 #include<cmath>
3 #include<algorithm>
4 using namespace std;
5 int bl[50010]; //bl[i]代表第 i个数位于哪个块
6 int atag[50010]; //存储每个块内 操作加值的和
7 int block,n,a[50010];
8 int read(){
9 int x=0,f=1;
10 char c=getchar();
11 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} //注意大括号不能省
12 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
13 return x*f;
14 }
15 void add(int l,int r,int c){
16 for(int i=l;i<=min(bl[l]*block,r);i++) a[i]+=c; //区间覆盖的左半块
17 if(bl[l]!=bl[r]){ //不在同一个块时
18 for(int i=(bl[r]-1)*block+1;i<=r;i++) a[i]+=c; //区间覆盖的右半块
19 }
20 for(int i=bl[l]+1;i<=bl[r]-1;i++) atag[i]+=c; //中间的整块整块处理
21 }
22 int main()
23 {
24 n=read();
25 block=sqrt(n); //每个块的大小
26 for(int i=1;i<=n;i++) a[i]=read();
27 for(int i=1;i<=n;i++) bl[i]=(i-1)/block+1; //分块
28 //比如 block=2 那么1 2是属于第一个块的,3 4属于第二个块 这样处理刚好能满足需求
29 for(int i=1;i<=n;i++){
30 int opt=read(),l=read(),r=read(),c=read();
31 if(opt==0) add(l,r,c);
32 else printf("%d
",a[r]+atag[bl[r]]);
33 }
34 return 0;
35 }
View Code
2. 区间加法 询问区间内小于x的元素个数 (vector 块内排序 lower_bound)
![]()
1 #include<cstdio>
2 #include<vector>
3 #include<cmath>
4 #include<algorithm>
5 #define N 50010
6 using namespace std;
7 int a[N],bl[N],atage[N],n,block;
8 vector <int > v[N]; //动态数组
9 int read(){
10 int x=0,f=1;
11 char c=getchar();
12 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
13 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
14 return x*f;
15 }
16 void reset(int x){
17 v[x].clear(); //清除x块内元素
18 for(int i=(x-1)*block+1;i<=x*block;i++) v[x].push_back(a[i]);
19 //(x-1)*block+1 表示第 x-1块内的末元素+1,也就是第 x块的第一个元素
20 // x*block 表示 第 x块的末元素
21 sort(v[x].begin(),v[x].end());
22 }
23 void add(int l,int r,int c){
24 for(int i=l;i<=min(bl[l]*block,r);i++) a[i]+=c; //最左边的(半)块
25 reset(bl[l]); //a[i]的值改变 容器里的值也要更新
26 if(bl[l]!=bl[r]){
27 for(int i=(bl[r]-1)*block+1;i<=r;i++) a[i]+=c; //最右边的(半)块
28 reset(bl[r]);
29 }
30 for(int i=bl[l]+1;i<=bl[r]-1;i++) atage[i]+=c; //中间的整块整块处理
31 }
32 void ask(int l,int r,int c){
33 int sum=0;
34 for(int i=l;i<=min(bl[l]*block,r);i++) if(a[i]+atage[bl[i]]<c) sum++;
35 if(bl[l]!=bl[r]){
36 for(int i=(bl[r]-1)*block+1;i<=r;i++) if(a[i]+atage[bl[i]]<c) sum++;
37 }
38 for(int i=bl[l]+1;i<=bl[r]-1;i++){
39 int x=lower_bound(v[i].begin(),v[i].end(),c-atage[i])-v[i].begin();
40 sum+=x;
41 }
42 printf("%d
",sum);
43 }
44 int main()
45 {
46 n=read();
47 block=sqrt(n);
48 for(int i=1;i<=n;i++) a[i]=read();
49 for(int i=1;i<=n;i++){
50 bl[i]=(i-1)/block+1;
51 v[bl[i]].push_back(a[i]);
52 }
53 for(int i=1;i<=bl[n];i++) sort(v[i].begin(),v[i].end()); //块内排序
54 for(int i=1;i<=n;i++){
55 int opt=read(),l=read(),r=read(),c=read();
56 if(opt==0) add(l,r,c);
57 else ask(l,r,c*c);
58 }
59 return 0;
60 }
View Code
3. 区间加法 询问区间内小于某个值x的前驱（比其小的最大元素 (set lower_bound)
![]()
1 #include<cstdio>
2 #include<algorithm>
3 #include<set>
4 #define N 100010
5 using namespace std;
6 int read(){
7 int x=0,f=1; char c=getchar();
8 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
9 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
10 return x*f;
11 }
12 int n,blo;
13 int v[N],bl[N],atag[N];
14 set <int > st[110];
15 void add(int l,int r,int c){
16 for(int i=l;i<=min(r,bl[l]*blo);i++){
17 st[bl[l]].erase(v[i]);
18 v[i]+=c;
19 st[bl[l]].insert(v[i]);
20 }
21 if(bl[l]!=bl[r]){
22 for(int i=(bl[r]-1)*blo+1;i<=r;i++){
23 st[bl[r]].erase(v[i]);
24 v[i]+=c;
25 st[bl[r]].insert(v[i]);
26 }
27 }
28 for(int i=bl[l]+1;i<=bl[r]-1;i++)
29 atag[i]+=c;
30 }
31 int ask(int l,int r,int c){
32 int ans=-1;
33 for(int i=l;i<=min(r,bl[l]*blo);i++){
34 int val=v[i]+atag[bl[l]];
35 if(val<c) ans=max(val,ans);
36 }
37 if(bl[l]!=bl[r]){
38 for(int i=(bl[r]-1)*blo+1;i<=r;i++){
39 int val=v[i]+atag[bl[r]];
40 if(val<c) ans=max(val,ans);
41 }
42 }
43 for(int i=bl[l]+1;i<=bl[r]-1;i++){
44 int x=c-atag[i];
45 set <int > ::iterator it=st[i].lower_bound(x);
46 if(it==st[i].begin()) continue;
47 --it;
48 ans=max(ans,*it+atag[i]);
49 }
50 return ans;
51 }
52 int main()
53 {
54 n=read(),blo=1000;
55 for(int i=1;i<=n;i++) v[i]=read();
56 for(int i=1;i<=n;i++){
57 bl[i]=(i-1)/blo+1;
58 st[bl[i]].insert(v[i]);
59 }
60 for(int i=1;i<=n;i++){
61 int opt=read(),a=read(),b=read(),c=read();
62 if(opt==0) add(a,b,c);
63 else printf("%d
",ask(a,b,c));
64 }
65 return 0;
66 }
View Code
4. 区间加法 区间求和
![]()
1 #include<cstdio>
2 #include<cmath>
3 #include<algorithm>
4 #define N 50010
5 #define ll long long //真的不开 long long 见祖宗 T^T
6 using namespace std;
7 ll read(){
8 ll x=0,f=1; char c=getchar();
9 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
10 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
11 return x*f;
12 }
13 int n,blo,bl[N];
14 ll a[N],sum[N],atag[N]; // 不能开小
15 void add(int l,int r,int c){
16 for(int i=l;i<=min(bl[l]*blo,r);i++)
17 a[i]+=c,sum[bl[l]]+=c;
18 if(bl[l]!=bl[r]){
19 for(int i=(bl[r]-1)*blo+1;i<=r;i++)
20 a[i]+=c,sum[bl[r]]+=c;
21 }
22 for(int i=bl[l]+1;i<=bl[r]-1;i++)
23 atag[i]+=c;
24 }
25 ll ask(int l,int r){
26 ll ans=0;
27 for(int i=l;i<=min(bl[l]*blo,r);i++)
28 ans+=a[i]+atag[bl[l]];
29 if(bl[l]!=bl[r]){
30 for(int i=(bl[r]-1)*blo+1;i<=r;i++)
31 ans+=a[i]+atag[bl[r]];
32 }
33 for(int i=bl[l]+1;i<=bl[r]-1;i++)
34 ans+=sum[i]+atag[i]*blo;
35 return ans;
36 }
37 int main(){
38 n=read(),blo=sqrt(n);
39 for(int i=1;i<=n;i++) a[i]=read();
40 for(int i=1;i<=n;i++){
41 bl[i]=(i-1)/blo+1;
42 sum[bl[i]]+=a[i];
43 }
44 for(int i=1;i<=n;i++){
45 int opt=read(),l=read(),r=read(),c=read();
46 if(opt==0) add(l,r,c);
47 else printf("%d
",ask(l,r)%(c+1));
48 }
49 return 0;
50 }
View Code
5. 区间求和 区间开方
![]()
1 #include<cstdio>
2 #include<cmath>
3 #include<algorithm>
4 #define N 50010
5 #define ll long long
6 using namespace std;
7 ll read(){
8 ll x=0,f=1; char c=getchar();
9 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
10 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
11 return x*f;
12 }
13 int n,blo;
14 int bl[N],a[N],sum[N],flag[N];
15 void solve_sqrt(int x){
16 if(flag[x]) return ;
17 flag[x]=1;
18 sum[x]=0;
19 for(int i=(x-1)*blo+1;i<=x*blo;i++){
20 a[i]=sqrt(a[i]),sum[x]+=a[i];
21 if(a[i]>1) flag[x]=0;
22 }
23 }
24 void add(int l,int r,int c){
25 for(int i=l;i<=min(r,bl[l]*blo);i++){
26 sum[bl[l]]-=a[i];
27 a[i]=sqrt(a[i]);
28 sum[bl[l]]+=a[i];
29 }
30 if(bl[l]!=bl[r]){
31 for(int i=(bl[r]-1)*blo+1;i<=r;i++){
32 sum[bl[r]]-=a[i];
33 a[i]=sqrt(a[i]);
34 sum[bl[r]]+=a[i];
35 }
36 }
37 for(int i=bl[l]+1;i<=bl[r]-1;i++)
38 solve_sqrt(i);
39 }
40 int ask(int l,int r){
41 int ans=0;
42 for(int i=l;i<=min(bl[l]*blo,r);i++)
43 ans+=a[i];
44 if(bl[l]!=bl[r]){
45 for(int i=(bl[r]-1)*blo+1;i<=r;i++)
46 ans+=a[i];
47 }
48 for(int i=bl[l]+1;i<=bl[r]-1;i++)
49 ans+=sum[i];
50 return ans;
51 }
52 int main()
53 {
54 n=read(),blo=sqrt(n);
55 for(int i=1;i<=n;i++){
56 a[i]=read();
57 bl[i]=(i-1)/blo+1;
58 sum[bl[i]]+=a[i];
59 }
60 for(int i=1;i<=n;i++){
61 int opt=read(),l=read(),r=read(),c=read();
62 if(opt==0) add(l,r,c);
63 else printf("%d
",ask(l,r));
64 }
65 return 0;
66 }
View Code
6. 单点插入，单点询问
![]()
1 #include<cstdio>
2 #include<cmath>
3 #define re register
4 #define in inline
5 #define ll long long
6 #define N 1010
7 using namespace std;
8 in int read(){
9 int x=0,f=1; char c=getchar();
10 while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
12 return x*f;
13 }
14
15 int n,m,blo;
16 int new_point; //新增点数计数器
17 int a[N][N]; //a[i][j]记录第i块的第j个数
18 int b[N][N];
19 int len[N]; //len[i]记录第i块的个数
20
21 void rebuild(){
22 int x=0,t=0;
23 int k=m/blo; //m 新总长
24 if(m%blo!=0) k++;
25 m+=blo; new_point=0;
26 blo=sqrt(m);
27 for(int i=1;i<=k;i++)
28 for(int j=1;j<=len[i];j++){
29 x++;
30 int bl=(x-1)/blo+1;
31 b[bl][++t]=a[i][j];
32 if(t>=blo) t=0;
33 }
34 k=m/blo;
35 if(!m%blo) k++;
36 for(int i=1;i<k;i++){
37 len[i]=blo;
38 for(int j=1;j<=len[i];j++) a[i][j]=b[i][j];
39 }
40 if(!m%blo) len[k]=blo;
41 else len[k]=m-blo*blo;
42 for(int j=1;j<=len[k];j++) a[k][j]=b[k][j];
43 }
44
45 int main()
46 {
47 n=read(),m=n;
48 blo=sqrt(n);
49 for(re int i=1;i<=n;i++){
50 int x=read(),bl=(i-1)/blo+1;
51 a[bl][++len[bl]]=x;
52 }
53 for(re int i=1;i<=n;i++){
54 int opt=read(),l=read(),r=read(),c=read();
55 if(!opt){
56 new_point++;
57
58 int x=0,t;
59 for(t=1;t<=blo;t++){ //暴力找l的位置
60 if(x+len[t]>=l) break;
61 x+=len[t];
62 }
63
64 len[t]++,l-=x; //暴力插点
65 for(int i=len[t];i>l;i--) a[t][i]=a[t][i-1];
66 a[t][l]=r;
67
68 if(new_point>=blo) rebuild(); //重新分块
69 }
70 else {
71 re int x=0,t;
72 for(t=1;t<=blo;t++){
73 if(x+len[t]>=r) break;
74 else x+=len[t];
75 }
76 printf("%d
",a[t][r-x]);
77 }
78 }
79 return 0;
80 }
View Code
7. 区间乘法 区间加法 单点询问
![]()
1 #include<cstdio>
2 #include<cmath>
3 #include<algorithm>
4 #define N 100010
5 #define mod 10007
6 #define ll long long
7 using namespace std;
8 ll read(){
9 ll x=0,f=1; char c=getchar();
10 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
12 return x*f;
13 }
14 int n,blo;
15 int a[N],bl[N],atag[N],mtag[N];
16 void reset(int x){
17 for(int i=(x-1)*blo+1;i<=min(n,x*blo);i++) //注意与n取min
18 a[i]=(a[i]*mtag[x]+atag[x])%mod;
19 atag[x]=0,mtag[x]=1;
20 }
21 void solve(int opt,int l,int r,int c){
22 reset(bl[l]); //乘法优先级
23 for(int i=l;i<=min(r,bl[l]*blo);i++){
24 if(opt==0) a[i]+=c;
25 else a[i]*=c;
26 a[i]%=mod;
27 }
28 if(bl[l]!=bl[r]){
29 reset(bl[r]); //乘法优先级
30 for(int i=(bl[r]-1)*blo+1;i<=r;i++){
31 if(opt==0) a[i]+=c;
32 else a[i]*=c;
33 a[i]%=mod;
34 }
35 }
36 for(int i=bl[l]+1;i<=bl[r]-1;i++){
37 if(opt==0) atag[i]=(atag[i]+c)%mod;
38 else{
39 atag[i]=(atag[i]*c)%mod; // 注意
40 mtag[i]=(mtag[i]*c)%mod;
41 }
42 }
43 }
44 int main()
45 {
46 n=read(),blo=sqrt(n);
47 for(int i=1;i<=n;i++){
48 a[i]=read();
49 bl[i]=(i-1)/blo+1;
50 }
51 for(int i=1;i<=bl[n];i++) mtag[i]=1; //初始化mtag
52 for(int i=1;i<=n;i++){
53 int opt=read(),l=read(),r=read(),c=read();
54 if(opt==2) printf("%d
",(a[r]*mtag[bl[r]]+atag[bl[r]])%mod);
55 else solve(opt,l,r,c);
56 }
57 return 0;
58 }
View Code
8. 区间询问等于一个数c的元素，并将这个区间的所有元素改为c
![]()
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<algorithm>
5 #define N 100010
6 #define ll long long
7 using namespace std;
8 ll read(){
9 ll x=0,f=1; char c=getchar();
10 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
12 return x*f;
13 }
14 int n,blo;
15 int a[N],bl[N],tag[N];
16 void reset(int x){
17 if(tag[x]==-1) return ;
18 for(int i=(x-1)*blo+1;i<=x*blo;i++)
19 a[i]=tag[x];
20 tag[x]=-1;
21 }
22 int solve(int l,int r,int c){
23 int ans=0;
24 reset(bl[l]);
25 for(int i=l;i<=min(r,bl[l]*blo);i++){
26 if(a[i]!=c) a[i]=c;
27 else ans++;
28 }
29 if(bl[l]!=bl[r]){
30 reset(bl[r]);
31 for(int i=(bl[r]-1)*blo+1;i<=r;i++)
32 if(a[i]!=c) a[i]=c;
33 else ans++;
34 }
35 for(int i=bl[l]+1;i<=bl[r]-1;i++){
36 if(tag[i]!=-1){
37 if(tag[i]==c) ans+=blo;
38 else tag[i]=c;
39 }
40 else{
41 for(int j=(i-1)*blo+1;j<=i*blo;j++)
42 if(a[j]!=c) a[j]=c;
43 else ans++;
44 tag[i]=c;
45 }
46 }
47 return ans;
48 }
49 int main()
50 {
51 memset(tag,-1,sizeof(tag));
52 n=read(),blo=sqrt(n);
53 for(int i=1;i<=n;i++){
54 a[i]=read();
55 bl[i]=(i-1)/blo+1;
56 }
57 for(int i=1;i<=n;i++){
58 int l=read(),r=read(),c=read();
59 printf("%d
",solve(l,r,c));
60 }
61 return 0;
62 }
View Code
9. 区间的最小众数 [ 未AC 88分 ]
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <cmath>
5 #include <map>
6 #include <vector>
7 using namespace std;
8 int pos[110000], v[110000], cnt[110000], a[110000];
9 int id, n, N;
10 int f[510][510]; //块i到j之间的最小众数的id
11 map<int, int> m; //记录每个数的id
12 vector<int> b[51000]; //记录每个数出现的第一个位置
13 void dp(int x) {
14 memset(cnt, 0, sizeof(cnt));
15 int maxx = 0, ss = 0; //最大的id及最大的值
16 for (int i = (x - 1) * N + 1; i <= n; i++) {
17 int cc = ++cnt[a[i]]; //统计每个数出现的个数
18 if (cc > ss || cc == ss && v[a[i]] < v[maxx]) {
19 ss = cc;
20 maxx = a[i];
21 }
22 f[x][pos[i]] = maxx;
23 }
24 }
25 int along(int l, int r, int x) // ask how long
26 {
27 int ans = upper_bound(b[x].begin(), b[x].end(), r) -
28 lower_bound(b[x].begin(), b[x].end(), l); //求l到r在x块的长度（r的后继-l的前驱)
29 return ans;
30 }
31 int solve(int x, int y) {
32 int ss = 0, maxx = 0;
33 //完整的块
34 maxx = f[pos[x] + 1][pos[y] - 1];
35 ss = along(x, y, maxx);
36 //不完整的块
37 for (int i = x; i <= min(pos[x] * N, y); i++) {
38 int cc = along(x, y, a[i]);
39 if (cc > ss || cc == ss && v[a[i]] < v[maxx]) {
40 ss = cc;
41 maxx = a[i];
42 }
43 }
44 if (pos[x] != pos[y]) {
45 for (int i = (pos[y] - 1) * N + 1; i <= y; i++) {
46 int cc = along(x, y, a[i]);
47 if (cc > ss || cc == ss && v[a[i]] < v[maxx]) {
48 ss = cc;
49 maxx = a[i];
50 }
51 }
52 }
53 return maxx;
54 }
55 int main() {
56 scanf("%d", &n);
57 N = sqrt(n);
58 for (int i = 1; i <= n; i++) {
59 scanf("%d", &a[i]);
60 pos[i] = (i - 1) / N + 1;
61 if (m[a[i]] == 0) {
62 m[a[i]] = ++id; // a[i]是第几个出现的
63 v[id] = a[i];
64 }
65 a[i] = m[a[i]]; //强制重新编号
66 b[a[i]].push_back(i); //记录每一个出现的位置
67 }
68 for (int i = 1; i <= pos[n]; i++) dp(i);
69 for (int i = 1; i <= n; i++) {
70 int x, y;
71 scanf("%d%d", &x, &y);
72 if (x > y)
73 swap(x, y);
74 printf("%d
", v[solve(x, y)]);
75 }
76 return 0;
77 }
View Code
