分块
分块
当维护的信息不满足区间可加，可减性的时候，用线段树或者树状数组维护的时候较为困难，通过分块划分+预处理可以有效的解决一些问题
1 区间修改，区间查询
A Simple Problem with Integers POJ - 3468
将1… n 分成 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
预处理出所有块的端点两两之间的每个数出现的次数病记录众数，需要空间 O(N∗T2)
需要时间 O(N∗T2),每次询问，需要暴力修改 补足一块的部分 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 磁力块
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的询问
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-莫队 组合数查询也可以通过莫队分块然后修改
