分块与根号分治
在树状数组中提到过一个根号时间复杂度的前缀和方法
我们将它按照线段树的结构构建的优雅一点:
每
查询到整块的内容,直接
散块最多有两个(开头一个结尾一个,中间都是整块),数量
查询总复杂度就是
当修改的时候,修改涉及到整块的时候,直接整块一起改,然后记录下来,零散的位置再一个一个改,也是
void update(int l,int r,int k)
{
if(b[l]==b[r])//如果位于同一块
{
for(int i=l;i<=r;++i) a[i]+=k;
return;
}
for(int i=l;i<=br[b[l]];++i) a[i]+=k;
for(int i=r;i>=bl[b[r]];--i) a[i]+=k;//左右两边的零散部分
for(int i=b[l]+1;i<=b[r]-1;++i)//整块的
{
ans[i]+=(br[i]-bl[i]+1)*k;
tag[i]+=k;//记录一下这块加了k,之后作为零散部分的时候要用
}
}
int query(int l,int r)
{
int sum=0;
if(b[l]==b[r])//如果位于同一块
{
for(int i=l;i<=r;++i) sum+=a[i]+tag[b[i]];
return sum;
}
for(int i=l;i<=br[b[l]];++i) sum+=a[i]+tag[b[l]];
for(int i=r;i>=bl[b[r]];--i) sum+=a[i]+tag[b[r]];//左右两边的零散部分
for(int i=b[l]+1;i<=b[r]-1;++i) sum+=ans[i];//整块的
return sum;
}
int cnt=sqrt(n)+1;//块大小
for(int i=1;i<=n;++i)
{
b[i]=(i-1)/cnt+1;//第i个数字属于哪一块,i/cnt上取整数。
sum[b[i]]+=a[i];//求块的和
if(!bl[b[i]]) bl[b[i]]=i;//bl[i]和br[i] 是第 i 块的左右端点
br[b[i]]=i;//第b[i]块的左右端点。
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
分块算法本质上还是根号平衡。
它相比线段树和树状数组的优点在于,信息不需要加减性,不需要可加性,信息的维护全靠暴力。
例题:模板题
维护区间加法,区间
区间加法可以对每个块暴力,如果是散块则直接对整个块的所有数字排序。
查询可以对每个块排序后数列二分答案。
这样修改和查询都是
所以总时间复杂度就是
根号分治
分块本质是暴力算法中基于数据的平衡
有
还是按
每个块记录信息:从第
这个每一块的处理其实是
for(int i=r;i>=l;--i)//第i块范围是$l~r$
{
if(i+a[i]>r) b[i]=1,c[i]=i+a[i];
else
{
b[i]=b[i+a[i]]+1,c[i]=c[i+a[i]];
}
}
2
3
4
5
6
7
8
查询的时候,就可以一块一块的跳了。
修改的时候只要改当前所在块里的所有信息了行了,因为每个点只记录到自己块内能飞到哪里。
不用管什么是哈希冲突,直接读题。
给定一个长度为
第一种:给两个数字
第二种:改变某个位置上数字的值。
如果
如果
值域分块
给定序列,数字范围在
鉴于下标不满一整块的位置可以直接暴力求,所以默认查询只需要求整块范围内的答案。
将数字也按
开
对于
现在要找下标位置第
设
如果查询的下标位于相邻块或者值域位于相邻块,则直接暴力
否则,先将不在一整块的数字进行处理(对
然后用数组查询下标位于
最后查询下标位于散块且值域位于整块的数字有没有遗漏,这里计算种类数的时候要再次在
(经过实践,这样会超空间,由于
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
#define lowbit(i) ((i)&(-i))
const int inf=1e18;
const int N=1e5+10;
int f[504][504];
int g[201][201][201];
int b[N],c[N];
int bl[N],br[N],cl[N],cr[N];
void solve()
{
int n,m;
cin>>n>>m;
vector<vector<int> > pos(N);
vector<int> a(n+1);
int cnt=500;
for(int i=1;i<=n;++i)
{
cin>>a[i];
pos[a[i]].emplace_back(i);
b[i]=(i-1)/cnt+1;
if(!bl[b[i]]) bl[b[i]]=i;
br[b[i]]=i;
}
for(int i=1;i<=100000;++i)
{
c[i]=(i-1)/cnt+1;
if(!cl[c[i]]) cl[c[i]]=i;
cr[c[i]]=i;
}
vector<int> col(N);
for(int i=1;i<=n;++i)
{
++f[b[i]][c[a[i]]];
}
for(int k=1;k<=c[100000];++k)
for(int i=2;i<=b[n];++i)
f[i][k]+=f[i-1][k];
for(int l=1;l<=b[n];++l)
{
for(int r=l;r<=b[n];++r)
{
for(int i=bl[r];i<=br[r];++i)
{
int x=c[a[i]];
++col[a[i]];
if(col[a[i]]==1) ++g[l][r][x];
}
}
for(int r=l+1;r<=b[n];++r)
for(int k=1;k<=c[100000];++k)
g[l][r][k]+=g[l][r-1][k];
for(int r=l;r<=b[n];++r)
{
for(int i=bl[r];i<=br[r];++i)
{
--col[a[i]];
}
}
}
// int tot=0;
while(m--)
{
// if(++tot==30) return;
int l,r,ql,qr;
cin>>l>>r>>ql>>qr;
int ans1=0,ans2=0;
if(b[l]+1>=b[r])
{
for(int i=l;i<=r;++i)
{
if(ql<=a[i]&&a[i]<=qr)
{
++ans1;
++col[a[i]];
if(col[a[i]]==1) ++ans2;
}
}
cout<<ans1<<' '<<ans2<<'\n';
for(int i=l;i<=r;++i)
{
if(ql<=a[i]&&a[i]<=qr)
{
--col[a[i]];
}
}
continue;
}
else if(c[ql]+1>=c[qr])
{
for(int x=ql;x<=qr;++x)
{
int t1=lower_bound(pos[x].begin(),pos[x].end(),l)-pos[x].begin();
int t2=upper_bound(pos[x].begin(),pos[x].end(),r)-pos[x].begin();
ans1+=t2-t1;
ans2+=(t2>t1);
}
cout<<ans1<<' '<<ans2<<'\n';
}
else
{
//零散数字
for(int x=ql;x<=cr[c[ql]];++x)
{
int t1=lower_bound(pos[x].begin(),pos[x].end(),l)-pos[x].begin();
int t2=upper_bound(pos[x].begin(),pos[x].end(),r)-pos[x].begin();
ans1+=t2-t1;
ans2+=(t2>t1);
}
for(int x=qr;x>=cl[c[qr]];--x)
{
int t1=lower_bound(pos[x].begin(),pos[x].end(),l)-pos[x].begin();
int t2=upper_bound(pos[x].begin(),pos[x].end(),r)-pos[x].begin();
ans1+=t2-t1;
ans2+=(t2>t1);
}
// cout<<ans2<<endl;
for(int k=c[ql]+1;k<=c[qr]-1;++k)
{
ans1+=f[b[r]-1][k]-f[b[l]][k];
ans2+=g[b[l]+1][b[r]-1][k];
}
// cout<<ans1<<endl;
// cout<<ans2<<endl;
//零散位置
for(int i=l;i<=br[b[l]];++i)
{
if(cl[c[ql]+1]<=a[i]&&a[i]<=cr[c[qr]-1])
{
int x=a[i];
++ans1;
++col[a[i]];
if(col[a[i]]==1)
{
int t1=lower_bound(pos[x].begin(),pos[x].end(),bl[b[l]+1])-pos[x].begin();
int t2=upper_bound(pos[x].begin(),pos[x].end(),br[b[r]-1])-pos[x].begin();
if(t2<=t1) ++ans2;
}
}
}
for(int i=r;i>=bl[b[r]];--i)
{
if(cl[c[ql]+1]<=a[i]&&a[i]<=cr[c[qr]-1])
{
int x=a[i];
++ans1;
++col[a[i]];
if(col[a[i]]==1)
{
int t1=lower_bound(pos[x].begin(),pos[x].end(),bl[b[l]+1])-pos[x].begin();
int t2=upper_bound(pos[x].begin(),pos[x].end(),br[b[r]-1])-pos[x].begin();
if(t2<=t1) ++ans2;
}
}
}
for(int i=l;i<=br[b[l]];++i)
{
if(cl[c[ql]+1]<=a[i]&&a[i]<=cr[c[qr]-1])
{
--col[a[i]];
}
}
for(int i=r;i>=bl[b[r]];--i)
{
if(cl[c[ql]+1]<=a[i]&&a[i]<=cr[c[qr]-1])
{
--col[a[i]];
}
}
cout<<ans1<<' '<<ans2<<'\n';
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T=1; //cin>>T;
while(T--) solve();
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185