「BZOJ 4765」普通计算姬 题解

Cnblogs 题解

知识点

主席树，分块，DFS 序。

分析

$O(m\sqrt{n\log_2{n}})$

我们可以离线对修改操作分块，假设每块长度为 $B$。

那么对于每块有修改的点存下来，其余的点 $O(n)$ 的复杂度内预处理出来，以前缀和的方式存下来。

那么我们发现每个有修改的点对于区间 $[l,r]$ 的贡献个数就等于在 $[l,r]$ 内有几个是它的祖先，这部分主席树即可。

那么我们复杂度为 $O(\frac{m}{B}n+mB\log_2{n})$，在 $B=\sqrt{\frac{n}{\log_2{n}}}$ 时取到最小值 $O(m\sqrt{n\log_2{n}})$。

时间复杂度 $O(m\sqrt{n\log_2{n}})$，空间复杂度 $O(n\log_2{n})$。

提示

在每块预处理的时候，可以先处理出按 DFS 序排序的序列，这样会快很多。

$O(m\sqrt{n})$

我们对序列分块。

• 考虑查询，我们会有整块和散点。

  对于整块，我们直接查询；对于散点，我们可以考虑用数据结构维护 DFS 序子树和。

• 考虑修改，对应上面的整块和散点。

  整块的部分，我们预处理出每个点在每一块有几个祖先；散点直接在数据结构上修改即可。

那么数据结构选用分块用来平衡，这里的分块是修改 $O(\sqrt{n})$，查询 $O(1)$ 的。

总时间复杂度 $O(m\sqrt{n})$，空间复杂度 $O(n\sqrt{n})$。

提示

记「每个点在每一块有几个祖先」时，可以将数组开成 short，会快很多。

代码

$O(m\sqrt{n\log_2{n}})$

//#define Plus_Cat "common"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1e5+10);

namespace IOEcat {
	//Fast IO...
} using namespace IOEcat;

bool vis[N];
int n,m,rt,Bl,Bn,cha,que,idx;
int a[N],fa[N],dfn[N];
ull ans[N],sum[N],Sum[N];
struct CFS {
	int tot,h[N];
	struct edge {
		int v,nxt;
		edge(int v=0,int nxt=-1):v(v),nxt(nxt) {}
	} e[N<<1];

	CFS():tot(0) {}

	edge &operator [](int i) { return e[i]; }

	void Init(int n) { RCL(h+1,-1,int,n),tot=-1; }

	void att(int u,int v) { e[++tot]=edge(v,h[u]),h[u]=tot; }

	void con(int u,int v) { att(u,v),att(v,u); }
} g;
struct Change { int u,d; } Cha[N];
struct Query { int t,l,r; } Que[N];
struct SEG {
	int tot;
	int rt[N];
	struct node { int ls,rs,sum; } tr[N*18];

	int &operator [](int i) { return rt[i]; }
#define ls(p) (tr[p].ls)
#define rs(p) (tr[p].rs)
#define mid ((l+r)>>1)
	void Plus(int x,int &p,int q,int l=1,int r=n) {
		tr[p=++tot]=tr[q],++tr[p].sum;
		if(l==r)return;
		return x<=mid?Plus(x,ls(p),ls(q),l,mid):Plus(x,rs(p),rs(q),mid+1,r);
	}

	int Sum(int L,int R,int p,int l=1,int r=n) {
		if(L<=l&&r<=R)return tr[p].sum;
		if(R<=mid)return Sum(L,R,ls(p),l,mid);
		if(mid<L)return Sum(L,R,rs(p),mid+1,r);
		return Sum(L,R,ls(p),l,mid)+Sum(L,R,rs(p),mid+1,r);
	}
#undef ls
#undef rs
#undef mid
} seg;

void dfs(int u) {
	seg.Plus(u,seg[u],seg[fa[u]]),sum[u]=a[u],dfn[++idx]=u;
	EDGE(g,i,u,v)if(v^fa[u])fa[v]=u,dfs(v),sum[u]+=sum[v];
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	/*DE("Input & Build");*/
	I(n,m),g.Init(n);
	FOR(i,1,n)I(a[i]);
	FOR(i,1,n) {
		int u,v;
		I(u,v);
		if(u>v)swap(u,v);
		u?g.con(u,v),0:rt=v;
	}
	dfs(rt);
	/*DE("Offline");*/
	FOR(i,1,m) {
		int op,x,y;
		I(op,x,y),op==1?(Cha[++cha]= {x,y},0):(Que[++que]= {cha,x,y},0);
	}
	DE(cha,que);
	/*DE("Solve");*/
	Bl=max(1,(int)ceil(sqrt(1.0*cha/log2(3.0*max(2,cha))))),Bn=(cha-1)/Bl+1;
	int it(1);
	FOR(j,1,n)Sum[j]=Sum[j-1]+sum[j];
	while(it<=que&&Que[it].t<=0)ans[it]=(Sum[Que[it].r]-Sum[Que[it].l-1]),++it;
	FOR(i,1,Bn) {
		const int l((i-1)*Bl+1),r(min(cha,i*Bl));
		vector<int> tmp;
		FOR(j,l,r)if(!vis[Cha[j].u])vis[Cha[j].u]=1,tmp.push_back(Cha[j].u);
		FOR(j,1,n)sum[j]=(vis[j]?0:a[j]);
		DOR(j,n,1)sum[fa[dfn[j]]]+=sum[dfn[j]];
		FOR(j,1,n)Sum[j]=Sum[j-1]+sum[j];
		FOR(j,l,r) {
			a[Cha[j].u]=Cha[j].d;
			while(it<=que&&Que[it].t<=j) {
				ans[it]=(Sum[Que[it].r]-Sum[Que[it].l-1]);
				for(int u:tmp)ans[it]+=(ull)a[u]*seg.Sum(Que[it].l,Que[it].r,seg[u]);
				++it;
			}
		}
		FOR(j,l,r)if(vis[Cha[j].u])vis[Cha[j].u]=0;
	}
	/*DE("Output");*/
	FOR(i,1,que)O(ans[i],'\n');
	return 0;
}

$O(m\sqrt{n})$

//#define Plus_Cat "common"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1e5+10),sN(317+10);

namespace IOEcat {
	//Fast IO...
} using namespace IOEcat;

int n,m,rt,idx;
int a[N],fa[N],dl[N],dr[N],dfn[N];
struct CFS {
	int tot,h[N];
	struct edge {
		int v,nxt;
		edge(int v=0,int nxt=-1):v(v),nxt(nxt) {}
	} e[N<<1];

	CFS():tot(0) {}

	edge &operator [](int i) { return e[i]; }

	void Init(int n) { RCL(h+1,-1,int,n),tot=-1; }

	void att(int u,int v) { e[++tot]=edge(v,h[u]),h[u]=tot; }

	void con(int u,int v) { att(u,v),att(v,u); }
} g;

namespace Block {
	short cnt[N][sN];
	int Bl,Bn;
	int st[sN],en[sN],bel[N];
	ull sum[sN];
	struct block {
		ull pre[N],Pre[sN];

		void Build(const int Bn) {
			FOR(i,1,Bn) {
				FOR(j,st[i],en[i])pre[j]=(j>st[i]?pre[j-1]:0)+a[dfn[j]];
				Pre[i]=Pre[i-1]+pre[en[i]];
			}
		}

		void Plus(int x,int d) {
			FOR(i,x,en[bel[x]])pre[i]+=d;
			FOR(i,bel[x],Bn)Pre[i]+=d;
		}

		ull Sum(int x) { return Pre[bel[x]-1]+pre[x]; }

		ull Sum(int l,int r) { return Sum(r)-Sum(l-1); }
	} blo;

	void Build(const int n) {
		Bl=ceil(sqrt(n)),Bn=(n-1)/Bl+1;
		FOR(i,1,Bn) {
			st[i]=en[i-1]+1,en[i]=min(en[i-1]+Bl,n);
			FOR(j,st[i],en[i])bel[j]=i;
		}
	}
} using namespace Block;

ull dfs(int u) {
	ull Sum(a[u]);
	FOR(i,1,Bn)cnt[u][i]=cnt[fa[u]][i];
	dfn[dl[u]=++idx]=u,++cnt[u][bel[u]];
	EDGE(g,i,u,v)if(v^fa[u])fa[v]=u,Sum+=dfs(v);
	return dr[u]=idx,sum[bel[u]]+=Sum,Sum;
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	/*DE("Input & Build");*/
	I(n,m),g.Init(n);
	FOR(i,1,n)I(a[i]);
	FOR(i,1,n) {
		int u,v;
		I(u,v);
		if(u>v)swap(u,v);
		u?g.con(u,v),0:rt=v;
	}
	Build(n),dfs(rt),blo.Build(Bn);
	while(m--) {
		int op;
		I(op);
		if(op==1) {
			int u,d;
			I(u,d),blo.Plus(dl[u],d-a[u]);
			FOR(i,1,Bn)sum[i]+=(ull)(d-a[u])*cnt[u][i];
			a[u]=d;
		} else {
			int l,r,bl,br;
			ull ans(0);
			I(l,r),bl=bel[l],br=bel[r];
			if(bl==br) {
				FOR(i,l,r)ans+=blo.Sum(dl[i],dr[i]);
				O(ans,'\n');
				continue;
			}
			FOR(i,l,en[bl])ans+=blo.Sum(dl[i],dr[i]);
			FOR(i,st[br],r)ans+=blo.Sum(dl[i],dr[i]);
			FOR(i,bl+1,br-1)ans+=sum[i];
			O(ans,'\n');
		}
	}
	return 0;
}