众所周知，分块是一种神奇的东西，在关键时刻可以怒踩标程。ZJ省队也有一位先辈，以善于在标程的复杂度上套一个$\sqrt{\ \ } $并且怒踩标程而出名(扯淡结束)，最近刷了一些让人颇有感触的分块题，于是口胡一下。
一个n个元素的数组A[]，有n个函数，每个函数对应一个区间$[L_i,R_i]$,函数的值为$\sum_{i=L_i}^{R_i}A[i]$，现有q个操作，每次更改一个元素的值或者询问一段函数的值的和。
感觉非常像树套树啊。。然而如果作为树套树恐惧症的患者，其实可以用不仅编程复杂度更低，时间复杂度也较低的分块来解决。
首先你要明确，CodeChef上空间是不设限的(当然你开大个几百倍基本上得RE(Other)，再大的话没的说得CE)，那么我们开始分块之旅。
对函数进行分块。记录每个元素在一个块中出现的次数。
那么单点更新的时候我们就可以在$\sqrt{n}$的时间里更新每个块的值了。
还有就是如果有一些函数需要单独算(不在块内)，我们可以维护一个BIT，然后log(n)暴力算。
剩下就只有一个问题了:如何得到每个元素在块中出现的次数。
这很无脑，差分即可。
那么我们把块的个数设到$\sqrt{nlog(n)}$，总的复杂度就可以达到$O(n \sqrt{nlog(n)})$了
感觉空间有点大有点虚所以我的阈值只设到了$O(\sqrt{n})$，然而还是过了。。
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
#define debug(x) cout<<#x<<"="<<x<<" ";
#define debugm(x) cout<<#x<<"="<<x<<endl;
#define line puts("---------------");
typedef unsigned long long ll;
const int M=1e5+5;
int cnt[M][340],w[M][340],l[M],r[M],A[M];
inline void rd(int &a){
a=0;char c;
while(c=getchar(),!isdigit(c));
do a=a*10+(c^48);
while(c=getchar(),isdigit(c));
}
ll sum[M];
int n,q;
inline void nt(ll x){
if(!x)return;
nt(x/10);
putchar(x%10+48);
}
void pt(ll x){
if(!x)putchar('0');
else nt(x);
}
struct BIT{
ll bit[M];
inline void add(int x,int a){
for(;x<=n;x+=x&-x)
bit[x]+=a;
}
inline ll sum(int x){
ll res=0;
for(;x;x-=x&-x)
res+=bit[x];
return res;
}
inline ll query(int l,int r){
return sum(r)-sum(l-1);
}
}T;
int main(){
cin>>n;
for(int i=1;i<=n;++i){
rd(A[i]);
T.add(i,A[i]);
}
int S=(int)sqrt(n+1)+1;
for(int i=0;i<n;++i){
rd(l[i]),rd(r[i]);
int s=i/S;
w[l[i]][s]++;w[r[i]+1][s]--;
}
for(int i=0;i*S<n;++i){
int s=0;
ll t=0;
for(int j=1;j<=n;++j){
s+=w[j][i];
cnt[j][i]=s;
t+=1ll*s*A[j];
}
sum[i]=t;
}
cin>>q;
for(int opt,x,y;q--;){
rd(opt),rd(x),rd(y);
if(opt==1){
for(int j=0;j*S<n;++j)
sum[j]+=1ll*(y-A[x])*cnt[x][j];
T.add(x,y-A[x]);
A[x]=y;
}
else{
--x,--y;
int lt=x/S,rt=y/S;
ll res=0;
if(lt==rt){
for(int i=x;i<=y;++i)
res+=T.query(l[i],r[i]);
}
else{
for(int i=x;i<(lt+1)*S;++i)
res+=T.query(l[i],r[i]);
for(int i=lt+1;i<rt;++i)
res+=sum[i];
for(int i=rt*S;i<=y;++i)
res+=T.query(l[i],r[i]);
}
pt(res);putchar('\n');
}
}
return 0;
}
n个元素，每次询问一段区间[L,R]，求这段区间里相同元素距离的最大值(即求$\max\mid x-y \mid$满足$x\ge L,y\le R\ A_x=A_y$)
同样的，这题维度比较多，树形数据结构难以维护，我们使用分块来维护。
但是这道题需要神奇的预处理。
首先设询问的区间为$[l,r]$,$L$为$l$所在块的标号，$R$为$r$所在的块的标号，块的大小是$S$我们观察答案可以出现的区间无非是$[(L+1)\times S,r]$,$[l,R\times S)$,或者左端点在$[l,(L+1)\times S)$，右端点在$[R\times S,r]$中。
我们可以预处理以每一个块的左端点为起点到以所有点为终点的答案，以及以每个块的右端点为终点，起点为所有点的答案，然后在询问的时候只关注最后那一部分(左端点在$[l,(L+1)\times S)$，右端点在$[R\times S,r]$中)
这玩意和预处理的时候一样随便搞搞就可以了。
所以整个的复杂度是$O(n\sqrt{n})$
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int M=1e5+5;
int S,A[M],res[320][M],les[320][M],pre[M],n,m,q;
inline void rd(int &a){
a=0;char c;
while(c=getchar(),!isdigit(c));
do a=a*10+(c^48);
while(c=getchar(),isdigit(c));
}
inline void Max(int &a,int b){
if(a<b)a=b;
}
inline void pret(){
memset(pre,-1,sizeof(pre));
for(int i=0;i*S<n;++i){
for(int j=i*S;j<n;++j){
if(pre[A[j]]==-1)pre[A[j]]=j;
Max(res[i][j],j-pre[A[j]]);
Max(res[i][j],res[i][j-1]);
}
for(int j=i*S;j<n;++j)
pre[A[j]]=-1;
}
int s=n/S;
for(int i=s;~i;--i){
for(int j=i*S-1;j>=0;--j){
if(pre[A[j]]==-1)pre[A[j]]=j;
Max(les[i][j],pre[A[j]]-j);
Max(les[i][j],les[i][j+1]);
}
for(int j=i*S;~j;--j)
pre[A[j]]=-1;
}
}
int main(){
cin>>n>>m>>q;
for(int i=0;i<n;++i)
rd(A[i]);
S=(int)sqrt(n+1);
pret();
for(int l,r;q--;){
rd(l),rd(r),--l,--r;
int L=l/S,R=r/S,tp=0;
if(L==R){
int ans=0;
for(int i=l;i<=r;++i){
if(pre[A[i]]==-1)pre[A[i]]=i;
Max(ans,i-pre[A[i]]);
}
for(int i=l;i<=r;++i)
pre[A[i]]=-1;
printf("%d\n",ans);
continue;
}
for(int i=l;i<min(n,(L+1)*S);++i)
if(pre[A[i]]==-1)pre[A[i]]=i;
int ans=max(res[L+1][r],les[R][l]);
for(int i=R*S;i<=r;++i)
if(~pre[A[i]])Max(ans,i-pre[A[i]]);
for(int i=l;i<min(n,(L+1)*S);++i)
pre[A[i]]=-1;
printf("%d\n",ans);
}
return 0;
}
感觉就是这两题都很妙啊，突破了普通分块的桎梏。。
还有一些分块的题: