铃铛计数问题 解题报告

U72118 铃铛计数问题

对点我们发现有两种编号，一种是它本身的编号用作询问，一种是便于我们子树/链的操作的重新编号。

如果对链树剖作为第二编号，把点放到二维平面内，我们就可以用个kd-tree维护，需要支持一些加和询问之类的操作，但因为有个(log)段，所以实际上是(sqrt nlog n)的。我寻思卡卡是可以过的。

正解是分块

我们考虑对原编号分块

设(f_{i,r})表示点(i)对块(r)的贡献，这个可以dp出来，从父亲那里转移。

这样我们大块询问和大块修改就可以完成了

考虑小块询问和小块修改

实际上我们需要支持询问子树和，修改单点值，要求询问(O(1))

考虑放到(dfs)序上，就成了单点改，区间询问，然后再分一拨块就可以了

写成单点询问，区间修改比较好写

---

Code:

#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#define ll long long
using std::min;
const int SIZE=1<<21;
char ibuf[SIZE],*iS,*iT;
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
#define gc() getchar()
template <class T>
void read(T &x)
{
	int f=0;x=0;char c=gc();
	while(!isdigit(c)) f|=c=='-',c=gc();
	while(isdigit(c)) x=x*10+c-'0',c=gc();
	if(f) x=-x;
}
const int N=1e5+10;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int n,q,rt,yuy[N],toki[N][320],B,T,L[N],R[N],belong[N];
int dfn[N],low[N],ha[N],dfsclock;
ll sum[N];
void dfs(int now,int fa)
{
	dfn[now]=++dfsclock;
	ha[dfsclock]=now;
	for(int i=1;i<=T;i++) toki[now][i]=toki[fa][i]+(L[i]<=now&&now<=R[i]),sum[i]+=1ll*toki[now][i]*yuy[now];
	for(int v,i=head[now];i;i=Next[i])
		if((v=to[i])!=fa)
			dfs(v,now);
	low[now]=dfsclock;
}
ll tag[N],f[N];
void modi(int x,int d)
{
	int pos=belong[x];
	for(int i=pos+1;i<=T;i++) tag[i]+=d;
	for(int i=x;i<=R[pos];i++) f[i]+=d;
}
ll qry(int x)
{
	return f[x]+tag[belong[x]];
}
int main()
{
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
	read(n),read(q);
	for(int i=1;i<=n;i++) read(yuy[i]);
	for(int u,v,i=1;i<=n;i++)
	{
		read(u),read(v);
		if(u) add(u,v),add(v,u);
		else rt=v;
	}
	B=sqrt(n)+1,T=(n-1)/B+1;
	for(int i=1;i<=T;i++)
	{
		L[i]=R[i-1]+1,R[i]=min(i*B,n);
		for(int j=L[i];j<=R[i];j++)
			belong[j]=i;
	}
	dfs(rt,0);
	for(int i=1;i<=n;i++) f[i]=f[i-1]+yuy[ha[i]];
	for(int op,l,r,i=1;i<=q;i++)
	{
		read(op),read(l),read(r);
		if(op==1)
		{
			int d=r-yuy[l];
			yuy[l]=r;
			for(int j=1;j<=T;j++)
				sum[j]+=1ll*d*toki[l][j];
			modi(dfn[l],d);
		}
		else
		{
			int lp=belong[l],rp=belong[r];
			ll ans=0;
			if(rp-lp<=1)
			{
				for(int j=l;j<=r;j++)
					ans+=qry(low[j])-qry(dfn[j]-1);
			}
			else
			{
				for(int j=l;j<=R[lp];j++) ans+=qry(low[j])-qry(dfn[j]-1);
				for(int j=lp+1;j<rp;j++) ans+=sum[j];
				for(int j=L[rp];j<=r;j++) ans+=qry(low[j])-qry(dfn[j]-1);
			}
			printf("%lld
",ans);
		}
	}
	return 0;
}

---

2019.5.23