数列分块入门
写在前面
写得好的暴力叫分块，写得烂的分块叫暴力
警钟敲烂
-
修改时要先将原数组复制一份，否则无法应对边角块的修改。
-
一定要特判 $ l$ 和 $ r $ 属于同一块的情况！111
-
判定是否开最后一块时要看当前的 R[tot] 是否小于 $ n $。
-
在同一块修改后要及时返回。
数列分块入门1
内容涉及区间加和区间求和，普通的分块题。时间复杂度 $O\left ( n\sqrt{n} \right ) $。
#include<iostream>
#include<cmath>
using namespace std;
int n;
int block[250];
int a[50200],b[50222],lazy[250];
int L[250],R[250],tot=0;
void change(int l,int r,int c){
if(b[l]==b[r]){
for(int i=l;i<=r;i++){
a[i]+=c;
}
return ;
}
for(int i=b[l]+1;i<b[r];i++){
lazy[i]+=c;
}
for(int i=l;i<=R[b[l]];i++){
a[i]+=c;
}
for(int i=L[b[r]];i<=r;i++){
a[i]+=c;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
tot=sqrt(n);
for(int i=1;i<=tot;i++){
L[i]=(i-1)*sqrt(n)+1;
R[i]=i*sqrt(n);
}
if(n>R[tot])tot++,L[tot]=R[tot-1]+1,R[tot]=n;
for(int i=1;i<=tot;i++){
for(int j=L[i];j<=R[i];j++){
b[j]=i;
}
}
for(int i=1;i<=n;i++){
int opt;int l,r,c;
cin>>opt>>l>>r>>c;
if(!opt){
change(l,r,c);
}
else {
cout<<a[r]+lazy[b[r]]<<endl;
}
}
}
数列分块入门2
对于每个块，我们对其内部排序。区间加的情况处理方法同上，但是要维护每个块内元素的有序性。题目还要求求区间 \(\le c^{2}\) 的元素个数，可以在每个块内进行二分查找。
#include<bits/stdc++.h>
using namespace std;
int a[1000005],bl[1005],L[1005],R[1005],lazy[1005],tmp[1000005],tot,be[1000005];
bool cmp(int x,int y){
return x<y;
}
void add(int l,int r,int c){
if(be[l]==be[r]){
for(int i=l;i<=r;i++){
a[i]+=c;
}
for(int i=L[be[l]];i<=R[be[l]];i++){
tmp[i]=a[i];
}
sort(tmp+L[be[l]],tmp+R[be[l]]+1,cmp);
return ;
}
for(int i=be[l]+1;i<=be[r]-1;i++){
lazy[i]+=c;
}
for(int i=l;i<=R[be[l]];i++){
a[i]+=c;
}
for(int i=L[be[r]];i<=r;i++){
a[i]+=c;
}
for(int i=L[be[l]];i<=R[be[l]];i++){
tmp[i]=a[i];
}
for(int i=L[be[r]];i<=R[be[r]];i++){
tmp[i]=a[i];
}
sort(tmp+L[be[l]],tmp+R[be[l]]+1,cmp);
sort(tmp+L[be[r]],tmp+R[be[r]]+1,cmp);
}
int get(int l,int r,int c){
int ans=0;
if(be[l]==be[r]){
int c1=c-lazy[be[l]];
for(int i=l;i<=r;i++){
if(a[i]>=c1){
ans++;
}
}
return ans;
}
for(int i=l;i<=R[be[l]];i++){
int c1=c-lazy[be[l]];
if(a[i]>=c1){
ans++;
}
}
for(int i=L[be[r]];i<=r;i++){
int c1=c-lazy[be[r]];
if(a[i]>=c1){
ans++;
}
}
for(int i=be[l]+1;i<=be[r]-1;i++){
int c1=c-lazy[i];
int ll=L[i],rr=R[i],result=0,mid;
while(ll<=rr)
{
mid=(ll+rr)>>1;
if(tmp[mid]+lazy[i]>=c)
rr=mid-1,result=R[i]-mid+1;
else
ll=mid+1;
}
ans+=result;
}
return ans;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int tot=sqrt(n);
for(int i=1;i<=tot;i++){
L[i]=(i-1)*sqrt(n)+1;
R[i]=i*sqrt(n);
}
if(R[tot]<n){
tot++;
L[tot]=R[tot-1]+1;
R[tot]=n;
}
for(int i=1;i<=tot;i++){
for(int j=L[i];j<=R[i];j++){
tmp[j]=a[j];
be[j]=i;
}
sort(tmp+L[i],tmp+R[i]+1,cmp);
}
for(int i=1;i<=n;i++){
int m,l,r,c;
cin>>m>>l>>r>>c;
if(m==0){
add(l,r,c);
}
else {
cout<<r-l+1-get(l,r,c*c)<<endl;
}
}
}
数列分块入门3
和上一题类似，我们可以用二分查找找到每个数的前驱>_<
#include <bits/stdc++.h>
using namespace std;
int a[1000005], bl[1005], L[1005], R[1005], lazy[1005], tmp[1000005], tot, be[1000005];
bool cmp(int x, int y) {
return x < y;
}
int erfen(int l, int r, int x) {
if (x <= tmp[l])
return -2e9;
int mid;
while (l < r) {
mid = l + r + 1 >> 1;
if (tmp[mid] < x)
l = mid;
else
r = mid - 1;
}
return tmp[l];
}
void add(int l, int r, int c) {
if (be[l] == be[r]) {
for (int i = l; i <= r; i++) {
a[i] += c;
}
for (int i = L[be[l]]; i <= R[be[l]]; i++) {
tmp[i] = a[i];
}
sort(tmp + L[be[l]], tmp + R[be[l]] + 1);
return ;
}
for (int i = be[l] + 1; i <= be[r] - 1; i++) {
lazy[i] += c;
}
for (int i = l; i <= R[be[l]]; i++) {
a[i] += c;
}
for (int i = L[be[r]]; i <= r; i++) {
a[i] += c;
}
for (int i = L[be[l]]; i <= R[be[l]]; i++) {
tmp[i] = a[i];
}
for (int i = L[be[r]]; i <= R[be[r]]; i++) {
tmp[i] = a[i];
}
sort(tmp + L[be[l]], tmp + R[be[l]] + 1);
sort(tmp + L[be[r]], tmp + R[be[r]] + 1);
}
int get(int l, int r, int c) {
int ans = -2e9;
if(be[l]==be[r]){
for(int i=l;i<=r;i++){
if (a[i] + lazy[be[i]] < c)
ans = max(ans, a[i] + lazy[be[i]]);
}
return ans;
}
for (int i = be[l] + 1; i <= be[r] - 1; i++) {
ans = max(ans, erfen(L[i], R[i], c - lazy[i]) + lazy[i]);
}
for (int i = l; i <= R[be[l]]; i++) {
if (a[i] + lazy[be[i]] < c)
ans = max(ans, a[i] + lazy[be[i]]);
}
for (int i = L[be[r]]; i <= r; i++) {
if (a[i] + lazy[be[i]] < c)
ans = max(ans, a[i] + lazy[be[i]]);
}
return ans;
}
signed main(){
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int tot = sqrt(n);
for (int i = 1; i <= tot; i++) {
L[i] = (i - 1) * sqrt(n) + 1;
R[i] = i * sqrt(n);
}
if (R[tot] < n) {
tot++;
L[tot] = R[tot - 1] + 1;
R[tot] = n;
}
for (int i = 1; i <= tot; i++) {
for (int j = L[i]; j <= R[i]; j++) {
tmp[j] = a[j];
be[j] = i;
}
sort(tmp + L[i], tmp + R[i] + 1);
}
for (int i = 1; i <= n; i++) {
int m, l, r, c;
cin >> m >> l >> r >> c;
if (m == 0) {
add(l, r, c);
} else {
if (get(l, r, c) >= -1e9)
cout << get(l, r, c) << endl;
else
cout << -1 << endl;
}
}
}
数列分块入门4
线段树板子题没什么好讲的，直接看代码罢
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int block[50200];
int a[50200],b[50222],lazy[50200];
int sum[50200];
int L[50200],R[50200],tot=0;
void change(int l,int r,int c){
if(b[l]==b[r]){
for(int i=l;i<=r;i++){
a[i]+=c;
sum[b[i]]+=c;
}
return ;
}
for(int i=b[l]+1;i<=b[r]-1;i++){
sum[i]+=(R[i]-L[i]+1)*c;
lazy[i]+=c;
}
for(int i=l;i<=R[b[l]];i++){
a[i]+=c;
sum[b[l]]+=c;
}
for(int i=L[b[r]];i<=r;i++){
a[i]+=c;
sum[b[r]]+=c;
}
}
int get(int l,int r,int c){
c=c+1;
int ans=0;
if(b[l]==b[r]){
for(int i=l;i<=r;i++){
ans=(ans+a[i]+lazy[b[l]])%c;
}
return ans;
}
for(int i=b[l]+1;i<=b[r]-1;i++){
ans=(ans+sum[i])%c;
}
for(int i=L[b[r]];i<=r;i++){
ans=(ans+a[i]+lazy[b[r]])%c;
}
for(int i=l;i<=R[b[l]];i++){
ans=(ans+a[i]+lazy[b[l]])%c;
}
return ans;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
tot=sqrt(n);
for(int i=1;i<=tot;i++){
L[i]=(i-1)*tot+1;
R[i]=i*tot;
}
if(n>R[tot])tot++,L[tot]=R[tot-1]+1,R[tot]=n;
for(int i=1;i<=tot;i++){
for(int j=L[i];j<=R[i];j++){
b[j]=i;
sum[i]+=a[j];
}
}
for(int i=1;i<=n;i++){
int opt;int l,r,c;
cin>>opt>>l>>r>>c;
if(!opt){
change(l,r,c);
}
else {
cout<<get(l,r,c)<<endl;
}
}
}
数列分块入门5
很有意思的一题！注意到当一个数被开方后大小衰减得很快，例如 $ 2^{31}-1 $ 这么大的数只需要五次修改就会变成 $ 1$ 。所以用不了几次我们的序列就会完全由 $ 0 $ 和 $ 1 $ 组成了。当然，从那以后它们的值就不会继续改变。 我们可以分块维护那些块已经完全变成了$ 0 $ 和 $ 1 $ 的序列，再修改时跳过它们即可。
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n;
int block[100200];
int a[100055], b[100005], lazy[1005];
int sum[1005];
int L[1005], R[1005], tot = 0;
void change(int l,int r,int c){
if(b[l]==b[r]){
for(int i=l;i<=r;i++){
sum[b[i]]=sum[b[i]]-a[i]+sqrt(a[i]);
a[i]=sqrt(a[i]);
}
return ;
}
else {
for(int i=b[l]+1;i<=b[r]-1;i++){
if(!lazy[i]){
int ssr=0;
for(int j=L[i];j<=R[i];j++){
sum[i]=sum[i]-a[j]+sqrt(a[j]);
a[j]=sqrt(a[j]);
if(a[j]>1)ssr=1;
}
if(!ssr)lazy[i]=1;
}
}
for(int i=l;i<=R[b[l]];i++){
sum[b[i]]=sum[b[i]]-a[i]+sqrt(a[i]);
a[i]=sqrt(a[i]);
}
for(int i=L[b[r]];i<=r;i++){
sum[b[i]]=sum[b[i]]-a[i]+sqrt(a[i]);
a[i]=sqrt(a[i]);
}
}
}
int get(int l,int r,int c){
int ans=0;
if(b[l]==b[r]){
for(int i=l;i<=r;i++){
ans+=a[i];
}
return ans;
}
for(int i=b[l]+1;i<b[r];i++){
ans+=sum[i];
}
for(int i=l;i<=R[b[l]];i++){
ans+=a[i];
}
for(int i=L[b[r]];i<=r;i++){
ans+=a[i];
}
return ans;
}
main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int m;
tot=sqrt(n);
for(int i=1;i<=tot;i++){
L[i]=(i-1)*tot+1;
R[i]=i*tot;
}
if(R[tot]<n){
tot++;
R[tot]=n;
L[tot]=R[tot-1]+1;
}
for(int i=1;i<=tot;i++){
for(int j=L[i];j<=R[i];j++){
b[j]=i;
sum[i]+=a[j];
}
}
for(int i=1;i<=n;i++){
int opt,l,r,c=0;
cin>>opt>>l>>r>>c;
if(l>r)swap(l,r);
if(!opt){
change(l,r,c);
}
else {
cout<<get(l,r,c)<<endl;
}
}
}
数列分块入门6
对于单点插入，可以将每一个块内元素存到一个 vector 里 ，插入时直接在块内插就可以做到均摊 $O\left ( n\sqrt{n} \right ) $ 但是毒瘤的出题人可能将所有插入集中在同一个块内，这时就需要我们在块内长度明显超出 $ 2n $ 后重新分块。
在loj上此题用vector暴力插入跑的比正解还快，vector中insert的复杂度我暂且蒙古