文章目录

分块

当维护的信息不满足区间可加，可减性的时候，用线段树或者树状数组维护的时候较为困难，通过分块划分+预处理可以有效的解决一些问题

1 区间修改，区间查询

A Simple Problem with Integers POJ - 3468
将1… n 分成 n \sqrt{n} n ​块，每块大小 n \sqrt{n} n ​,对于每次修改或者查询，整块通过sum 直接加上，补足一块的暴力求解

const int maxn = 100010;
LL a[maxn],add[maxn],sum[maxn];
int pos[maxn],R[maxn],L[maxn];
int n,m,t;
void change(int l,int r,LL d){
  int p = pos[l],q = pos[r];
  if(p == q){
    for(int i = l;i <= r; ++i) a[i] += d;
    sum[p] += (r-l+1)*d;
  }
  else{
    for(int i = p+1;i <= q-1; ++i) add[i] += d;
    for(int i = l;i <= R[p];++i)
      a[i] += d;
    sum[p] += (R[p]-l+1)*d;
    for(int i = L[q];i <= r; ++i)
      a[i] += d;
    sum[q] += (r-L[q]+1)*d;
  }
}
LL ask(int l,int r){
  LL ans = 0;
  int p = pos[l],q = pos[r];
  if(p == q){
    for(int i = l;i <= r; ++i)
      ans += a[i];
    ans += (r-l+1)*add[p];
  }
  else{
    for(int i = p+1;i <= q-1; ++i)
      ans += sum[i]+add[i]*(R[i]-L[i]+1);
    for(int i = l;i <= R[p]; ++i)
      ans += a[i];
    ans += add[p]*(R[p]-l+1);
    for(int i = L[q];i <= r; ++i)
      ans += a[i];
    ans += add[q]*(r-L[q]+1);
  }
  return ans;
}
int main(void){

  cin>>n>>m;
  for(int i = 1;i <= n; ++i) scanf("%lld",&a[i]);
  LL t = sqrt(n);
  for(int i = 1;i <= t; ++i){
    L[i] = (i-1)*sqrt(n)+1;
    R[i] = i*sqrt(n);
  }
  if(R[t]  < n) t++,L[t] = R[t-1]+1,R[t] = n;
  // cout<<t<<endl;
  for(int i = 1;i <= t; ++i){
    for(int j = L[i];j <= R[i]; ++j){
      pos[j] = i;
      sum[i] += a[j];
    }
  }
  while(m--){
    char op[3];
    int l,r,x;
    scanf("%s%d%d",op,&l,&r);
    if(op[0] == 'C'){
      scanf("%d",&x);
      change(l,r,x);
    }
    else
      printf("%lld\n",ask(l,r));
  }
  return 0;
}

2 蒲公英 BZOJ2724

题目要求在线，我们同样将我们的序列分块，假设分成T块
预处理出所有块的端点两两之间的每个数出现的次数病记录众数，需要空间 O ( N ∗ T 2 ) O(N*T^2) O(N∗T2)
需要时间 O ( N ∗ T 2 ) O(N*T^2) O(N∗T2),每次询问，需要暴力修改 补足一块的部分 O ( M ∗ N / T ) O(M*N/T) O(M∗N/T),之后将修改补回去

const int N  = 40006,T = 37;
int a[N],b[N],L[N],R[N],pos[N];
int c[T][T][N],f[T][T][2],now[2];
inline void work(int x,int y,int num){
    ++c[x][y][num];
    if(c[x][y][num] > now[0] ||(c[x][y][num] == now[0] && num < now[1])){
        now[0] = c[x][y][num];
        now[1] = num;
    }
}   
int ask(int l,int r){
    int p = pos[l],q = pos[r];
    int x = 0,y = 0;
    if(p+1 <= q-1){
        x = p+1;
        y = q-1;
    }
    memcpy(now,f[x][y],sizeof(now));
    if(p == q){
        rep(i,l,r+1) work(x,y,a[i]);
        rep(i,l,r+1) --c[x][y][a[i]];
    }
    else{
        rep(i,l,R[p]+1) work(x,y,a[i]);
        rep(i,L[q],r+1) work(x,y,a[i]);
        rep(i,l,R[p]+1) --c[x][y][a[i]];
        rep(i,L[q],r+1) --c[x][y][a[i]];
    }
    return b[now[1]];
}
int main(void){
        // freopen("input.txt","r",stdin);

        // freopen("output1.txt","w+",stdout);
    int n,m;cin>>n>>m;
    rep(i,1,n+1) scanf("%d",&a[i]);
    memcpy(b,a,sizeof(a));
    sort(b+1,b+n+1);
    int tot = unique(b+1,b+n+1)-(b+1);
    rep(i,1,n+1) a[i] = lower_bound(b+1,b+tot+1,a[i])-b;
    int t = pow((double)n,(double)1/3);
    int len = t?n/t:n;
    for(int i = 1;i <= t; ++i){
        L[i] = (i-1)*len+1;
        R[i] = i*len;
    }
    if(R[t] < n){
        L[t+1] = R[t]+1;
        R[++t] = n;
    }
    rep(i,1,t+1)
        rep(j,L[i],R[i]+1)
            pos[j] = i;

    me(c),me(f);
    rep(i,1,t+1){
        rep(j,i,t+1){
            rep(k,L[i],R[j]+1)
                ++c[i][j][a[k]];
            rep(k,1,tot+1)
                if(c[i][j][k] > f[i][j][0]){
                    f[i][j][0] = c[i][j][k];
                    f[i][j][1] = k;
                }
        }
    }
    int x = 0;
    while(m--){
        int l,r;scanf("%d%d",&l,&r);
        l = (l+x-1)%n+1;
        r = (r+x-1)%n+1;
        if(l > r) swap(l,r);
        printf("%d\n",x = ask(l,r));
    }


    return 0;
}

3 磁力块

将磁力石按照重量分块，然后块内按照距离排序，用一个数组记录每段中吸引到何处，将所有吸引的磁石加入队列，然后去吸引每一个块，存在一个j，1…j-1的所有重量小于引力，j+1 之后的都不能吸引，于是可以扫描叫1…j-1 ,暴力扫描j块中的，之后将满足的都加入到队列里

const int maxn = 250000+10;
struct C{
   LL  x,y,m,p,r;
   LL d;
};
C c[maxn];
// int H[maxn];
int L[maxn],R[maxn],pos[maxn];
LL  maxm[maxn];
bool cmp1(const C &a,const C &b){
    return a.m < b.m;
}
bool cmp2(const C &a,const C &b){
    return a.d < b.d; 
}
bool inq[maxn];
int main(void)
{
        // freopen("input.txt","r",stdin);
        // freopen("output.txt","w+",stdout);
    LL x0,y0,pl,pr,N;cin>>x0>>y0>>pl>>pr>>N;
    pr *= pr;
    // cerr<<pr<<endl;
    rep(i,1,N+1){
        scanf("%lld %lld %lld %lld %lld",&c[i].x,&c[i].y,&c[i].m,&c[i].p,&c[i].r);
        c[i].x -= x0;
        c[i].y -= y0;
        c[i].d =  c[i].x*c[i].x+c[i].y*c[i].y;
        c[i].r *= c[i].r;
    }
    int t = sqrt(N);
    for(int i = 1;i <= t; ++i)
        L[i] = (i-1)*t+1,R[i] = i*t;
    if(R[t] < N){
        L[t+1] = R[t]+1;
        R[++t] = N;
    }
    // cout<<t<<endl;
    sort(c+1,c+N+1,cmp1);
    // cout<<L[1]<<" "<<R[1]<<endl;
    for(int i = 1;i <= t; ++i){
        sort(c+L[i],c+R[i]+1,cmp2);
        for(int j = L[i];j <= R[i]; ++j)
            maxm[i] = max(maxm[i],c[j].m);
        // cout<<i<<" "<<L[i] <<" "<<R[i]<<endl;
    }
    // for(int i = 1;i <= t; ++i){
    // cout<<endl;
    // for(int j = L[i];j <= R[i]; ++j){
    // cout<<c[j].m<<" "<<c[j].d<<" "<<c[j].r<<" "<<c[j].p<<endl;
    // }
    // }
    queue<P> Q;
    Q.push(P(pl,pr));
    int cnt = 0;
    while(!Q.empty()){
        P p = Q.front(); Q.pop();
        cnt++;
        int j = t+1;
        for(int i = 1;i <= t; ++i){
            if(maxm[i] > p.first){
                j = i;
                break;
            }
        }
        for(int i = 1;i < j; ++i)
        {
            while(L[i] <= R[i]&&c[L[i]].d <= p.second){
                if(!inq[L[i]])
                    Q.push(P(c[L[i]].p,c[L[i]].r));
                inq[L[i]] = true;
                L[i]++;

            }
        }
        if(j <= t){
            for(int i = L[j];i <= R[j]; ++i){
                if(c[i].m <= p.first &&c[i].d <= p.second){
                    if(!inq[i])
                        Q.push(P(c[i].p,c[i].r));
                    inq[i] = true;
                }
            }
        }
    }
    cout<<cnt-1<<endl;
   return 0;
}

4 洛谷P2709 小B的询问

对查询按照l排序，然后分块，块内按照r排序，暴力修改

const int maxn = 50000+10;
int n,m,k;
int pos[maxn];
int a[maxn];
int num[maxn];
LL  Ans[maxn];
int L[maxn],R[maxn];
struct Query{
    int l,r,id;
};
Query q[maxn];
bool cmp1 (const Query &a,const Query &b){
    return a.l < b.l ||(a.l == b.l && a.r < b.r);
}
bool cmp2(const Query &a,const  Query &b){
    return a.r < b.r;
}

void work(int x,LL &ans,int d){
    ans -= 1ll*num[x]*num[x];
    num[x] += d;
    ans += 1ll*num[x]*num[x];
}
int main(){
    cin>>n>>m>>k;
    rep(i,1,n+1) scanf("%d",&a[i]);
    rep(i,1,m+1){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    int t = sqrt(m);
    for(int i = 1;i <= t; ++i){
        L[i] = (i-1)*t;
        R[i] = i*t;
    }
    if(R[t] < m){
        L[t+1] = R[t]+1;
        R[++t] = m; 
    }
    sort(q+1,q+m+1,cmp1);
    for(int i = 1;i <= t; ++i){
        sort(q+L[i],q+R[i]+1,cmp2);
        LL ans = 0;
        me(num);
        int l = q[L[i]].l,r = q[L[i]].r;
        rep(i,l,r+1) work(a[i],ans,1);
        Ans[q[L[i]].id] = ans;
        for(int j = L[i]+1;j <= R[i]; ++j){
            // l = L[j].l,r = L[j].r;
            while(l < q[j].l) work(a[l++],ans,-1);
            while(l > q[j].l) work(a[--l],ans,1);
            while(r < q[j].r) work(a[++r],ans,1);
            while(r > q[j].r) work(a[r--],ans,-1);
            Ans[q[j].id] = ans;
        }
    }
    rep(i,1,m+1)
        printf("%lld\n",Ans[i]);
    return 0;
}

例题

1 小z的袜子(国家集训队) 对询问分块暴力修改
2 D. Powerful array 同上
3 HDU6333-2018ACM暑假多校联合训练1002-Harvest of Apples-莫队 组合数查询也可以通过莫队分块然后修改