正文
SqrtTree学习笔记
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
散步的时候yy区间最值的不同分块做法，发现单点修改\(O(\sqrt{n})\)查询\(O(1)\)的做法不是很会？
于是yy了一个奇怪做法，写出来看看。
考虑查询的时候两端的散点可以用前后缀最值查出来，所以只需要考虑中间的块。
中间这些块似乎比较恶心，不知道怎么做。
于是我们把每一个块的最值拎出来作为一个点，再分一次块，就成功地用\(O(1)\)的时间把问题变成了根号级别的子问题。
于是分块套分块套分块套……，似乎很对？
如果左右端点都在同一个块内那么不是很好玩，就对每一个块里面也分块，也是一个根号级别的子问题。
于是查询\(T(n)=T(\sqrt{n})+O(1)=O(\log \log n)\)。
那么修改的时候呢？要更新这一个块里面的分块、更新总体的分块、更新前后缀，好像就是\(T(n)=2T(\sqrt{n})+\sqrt{n}\)，也就是\(O(\sqrt{n})\)的。
复杂度一脸正确？
然后就被大佬摔在脸上：你这个东西跟sqrt-tree一模一样……
不过hz大佬改了一下，发现只需要分两层，在第二层块数是\(O(n^{\frac 1 4})\)的，于是可以直接暴力维护任意两个块中间的最值。于是就真的是\(O(\sqrt{n})-O(1)\)了。这样预处理的时间变成了\(O(n^{\frac 5 4})\)，但有什么关系呢？反正它除了做模板题以外好像还干不了什么
把hz改后的版本的代码写了出来并且封装了。感觉这东西应该也可以支持\(O(\sqrt{n}+\log n)\)做区间赋值的，打几个标记就可以了，不过懒得写了……（这点应该比正常的SqrtTree优？）
代码以GSS3为例，由于上不了SPOJ所以没有测，但是拍上了。
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
#define templ template<typename T>
#define sz 233333
#define S 400
typedef long long ll;
typedef double db;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
templ inline void read(T& t)
{
t=0;char f=0,ch=getchar();double d=0.1;
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
t=(f?-t:t);
}
template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
char __sr[1<<21],__z[20];int __C=-1,__zz=0;
inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
inline void print(register int x)
{
if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
while(__z[++__zz]=x%10+48,x/=10);
while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
}
void file()
{
#ifdef NTFOrz
freopen("a.in","r",stdin);
#endif
}
inline void chktime()
{
#ifndef ONLINE_JUDGE
cout<<(clock()-t)/1000.0<<'\n';
#endif
}
#ifdef mod
ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
ll inv(ll x){return ksm(x,mod-2);}
#else
ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
#endif
// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
template<typename hh>struct MySqrtTree
{
struct WTF
{
int m;
vector<hh>a;
int cnt,B;
hh mx1[25][25];
hh mx2[25][25][25];
vector<int>L,R,id;
vector<hh>pre,suf;
void init(int type)
{
B=sqrt(m),cnt=(m-1)/B+1;
L.resize(cnt+5),R.resize(cnt+5),id.resize(m+5);
pre.resize(m+5),suf.resize(m+5);
rep(i,1,cnt) L[i]=R[i-1]+1,R[i]=min(L[i]+B-1,m);
rep(i,1,cnt) rep(j,L[i],R[i]) id[j]=i;
rep(i,1,cnt) pre[L[i]]=a[L[i]],suf[R[i]]=a[R[i]];
rep(i,1,cnt) rep(j,L[i]+1,R[i]) pre[j]=pre[j-1]+a[j];
rep(i,1,cnt) drep(j,R[i]-1,L[i]) suf[j]=a[j]+suf[j+1];
if (type) return;
rep(i,1,cnt) rep(j,L[i],R[i])
{
hh cur=mx2[i][j-L[i]][j-L[i]]=a[j];
rep(k,j+1,R[i])
cur=cur+a[k],mx2[i][j-L[i]][k-L[i]]=cur;
}
rep(j,1,cnt) { hh cur=mx1[j][j]=mx2[j][0][R[j]-L[j]]; rep(k,j+1,cnt) cur=cur+mx2[k][0][R[k]-L[k]],mx1[j][k]=cur; }
}
hh query(int type,int l,int r)
{
if (type) return suf[l]+pre[r];
if (id[l]==id[r]) return mx2[id[l]][l-L[id[l]]][r-L[id[l]]];
if (id[l]+1==id[r]) return suf[l]+pre[r];
return suf[l]+mx1[id[l]+1][id[r]-1]+pre[r];
}
void modify(int type,int p,hh w)
{
a[p]=w;
int i=id[p];
pre[L[i]]=a[L[i]],suf[R[i]]=a[R[i]];
rep(j,L[i]+1,R[i]) pre[j]=pre[j-1]+a[j];
drep(j,R[i]-1,L[i]) suf[j]=a[j]+suf[j+1];
if (type) return;
rep(j,L[i],R[i]){ hh cur=mx2[i][j-L[i]][j-L[i]]=a[j]; rep(k,j+1,R[i]) cur=cur+a[k],mx2[i][j-L[i]][k-L[i]]=cur; }
rep(j,1,cnt) { hh cur=mx1[j][j]=mx2[j][0][R[j]-L[j]]; rep(k,j+1,cnt) cur=cur+mx2[k][0][R[k]-L[k]],mx1[j][k]=cur; }
}
}s[S];
void init(hh *a,int n)
{
s[0].a.resize(n+1);
s[0].m=n;
rep(i,1,n) s[0].a[i]=a[i];
s[0].init(1);
rep(i,1,s[0].cnt)
{
s[i].a.resize(s[0].R[i]-s[0].L[i]+3);
rep(j,s[0].L[i],s[0].R[i]) s[i].a[j-s[0].L[i]+1]=a[j],++s[i].m;
}
rep(i,1,s[0].cnt) s[i].init(0);
int cnt=s[0].cnt;
s[cnt+1].a.resize(cnt+1);
rep(i,1,cnt) s[cnt+1].a[i]=s[0].pre[s[0].R[i]];
s[cnt+1].m=cnt;
s[cnt+1].init(0);
}
hh query(int l,int r)
{
int il=s[0].id[l],ir=s[0].id[r];
if (il==ir-1) return s[0].query(1,l,r);
if (il==ir) return s[il].query(0,l-s[0].L[il]+1,r-s[0].L[il]+1);
return s[0].suf[l]+s[s[0].cnt+1].query(0,il+1,ir-1)+s[0].pre[r];
}
void modify(int p,hh w)
{
s[0].modify(1,p,w);
int i=s[0].id[p];
s[i].modify(0,p-s[0].L[i]+1,w);
s[s[0].cnt+1].modify(0,i,s[0].pre[s[0].R[i]]);
}
};
int n,m;
int a[sz];
struct hhh
{
ll lmx,rmx,mx,sum;
hhh (ll Lmx=0,ll Rmx=0,ll Mx=0,ll Sum=0){lmx=Lmx,rmx=Rmx,mx=Mx,sum=Sum;}
const hhh operator + (const hhh &x) const
{
hhh ret;
ret.lmx=max(lmx,x.lmx+sum);
ret.rmx=max(x.rmx,rmx+x.sum);
ret.mx=max({mx,x.mx,rmx+x.lmx});
ret.sum=sum+x.sum;
return ret;
}
}A[sz];
MySqrtTree<hhh>tr;
int main()
{
file();
read(n);
rep(i,1,n) read(a[i]),A[i]=hhh(a[i],a[i],a[i],a[i]);
tr.init(A,n);
read(m);
int x,y,z;
while (m--)
{
read(z,x,y);
if (z==0) tr.modify(x,hhh(y,y,y,y));
else printf("%lld\n",tr.query(x,y).mx);
}
return 0;
}
（正经的学习笔记在路上了……）
