bzoj 3730 震波——动态点分治+树状数组

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3730

查询一个点可以转化为查询点分树上自己到根的路径上每个点对应范围答案。可用树状数组 f 。

但有重复，所以再开一个树状数组 g 记录上一层重心的含自己的那棵子树里各种距离的点值和。

查询的时候如果上一层的重心有贡献，就加上它的 f 的对应范围，再减去这一层的 g 的对应范围。这两个范围是一样的，因为这一层的 g 也是相对上一层重心的距离。

修改的时候枚举每层，改一下这一层的 f 和下一层的 g 。只是这样写比较方便而已。

可以用 rmq O(1) 求两点距离，就是欧拉序里两点之间深度最小的就是 LCA 的深度，所以用 ST 表查询之类的。

所有的树状数组一共应该是 nlogn 个点，所以自己开了 nlogn 的数组，给每个点一个 l 和 r 表示它们用的是哪一段。然后疯狂 TLE 。可能也是 query 和 mdfy 的地方写得不好。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define il inline

#define rg register

using namespace std;

const int N=1e5+,K=;

int n,w[N],hd[N],xnt,to[N<<],nxt[N<<],ans;

int tim,tot,dep[N],q[N<<],ps[N],st[N][K+],lg[N<<],bin[K+];

int mn,rt,siz[N],pre[N],f[N*K],g[N*K<<],fl[N],fr[N],gl[N],gr[N],ftp,gtp;

bool vis[N];

il int rdn()

{

  rg int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int dg[];

il void wrt(int x)

{

  if(!x){puts("");return;}

  rg int tt=;while(x)dg[++tt]=x%,x/=;

  for(;tt;tt--)putchar(dg[tt]+'');puts("");

}

il int Mx(rg int a,rg int b){return a>b?a:b;}

il int Mn(rg int a,rg int b){return a<b?a:b;}

il void add(rg int x,rg int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

il void init_dfs(rg int cr,rg int fa)

{

  dep[cr]=dep[fa]+;q[++tot]=cr;ps[cr]=tot;

  for(rg int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)init_dfs(v,cr),q[++tot]=cr;//

}

il void init_dis()

{

  init_dfs(,);

  lg[]=;for(rg int i=;i<=tot;i++)lg[i]=lg[i>>]+;//lg[1]=0!

  bin[]=;for(rg int i=;i<=lg[tot];i++)bin[i]=bin[i-]<<;

  for(rg int i=;i<=tot;i++)st[i][]=dep[q[i]];

  for(rg int t=;t<=lg[tot];t++)

    for(rg int i=;i+bin[t]-<=tot;i++)

      st[i][t]=Mn(st[i][t-],st[i+bin[t-]][t-]);//bin[t-1]!!

}

il int pd(rg int x,rg int y)

{

  rg int u=ps[x],v=ps[y];if(u>v)swap(u,v);

  rg int t=lg[v-u+],d=Mn(st[u][t],st[v-bin[t]+][t]);

  return dep[x]-d+dep[y]-d;

}

il void add(rg int x,rg int l,rg int r,rg int k){for(rg int d=r-l;x<=d;x+=(x&-x))f[x+l]+=k;}

il void addx(rg int x,rg int l,rg int r,rg int k){for(rg int d=r-l;x<=d;x+=(x&-x))g[x+l]+=k;}

il int qry(rg int x,rg int l,rg int r){if(!x)return ;rg int ret=;for(;x;x-=(x&-x))ret+=f[x+l];return ret;}

il int qryx(rg int x,rg int l,rg int r){rg int ret=;for(;x;x-=(x&-x))ret+=g[x+l];return ret;}

il void getrt(rg int cr,rg int fa,rg int s)

{

  siz[cr]=;rg int mx=;

  for(rg int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)

      {

    getrt(v,cr,s);siz[cr]+=siz[v];mx=Mx(mx,siz[v]);

      }

  mx=Mx(mx,s-siz[cr]); if(mx<mn)mn=mx,rt=cr;

}

il void dfs(rg int cr,rg int fa,rg int dis)

{

  if(dis)add(dis,fl[rt],fr[rt],w[cr]);

  for(rg int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)dfs(v,cr,dis+);

}

il void dfsx(rg int cr,rg int fa,rg int dis)

{

  addx(dis,gl[rt],gr[rt],w[cr]);

  //  printf("adx:rt=%d cr=%d dis=%d(w=%d)\n",rt,cr,dis,w[cr]);

  for(rg int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)dfsx(v,cr,dis+);

}

il void init(rg int cr,rg int lst,rg int pr,rg int s)

{

  /*vis[cr]=1;*/pre[cr]=pr;

  fl[cr]=ftp;ftp+=mn;fr[cr]=ftp;//l:1,r:mn

  gl[cr]=gtp;gtp+=(mn<<)+;gr[cr]=gtp;//+1!!i.e.:only one point

  dfs(cr,,);if(lst)dfsx(lst,,);

  vis[cr]=;//for dfsx may cross rt

  for(rg int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]])

      {

    rg int ts=(siz[v]<siz[cr]?siz[v]:s-siz[cr]);

    mn=N;getrt(v,cr,ts);init(rt,v,cr,ts);

      }

}

il void query(rg int cr,rg int x,rg int dis,rg int yd)

{

  for(;pre[cr];cr=pre[cr])

    {

      ans+=qry(Mn(dis,fr[cr]-fl[cr]),fl[cr],fr[cr])+w[cr];

      dis=yd-pd(x,pre[cr]); if(dis<)return;//

      if(dis)ans-=qryx(Mn(dis,gr[cr]-gl[cr]),gl[cr],gr[cr]);

    }

  ans+=qry(Mn(dis,fr[cr]-fl[cr]),fl[cr],fr[cr])+w[cr];

}

il void mdfy(rg int cr,rg int k,rg int x,rg int dis)

{

  for(;pre[cr];cr=pre[cr])

    {

      if(dis)add(dis,fl[cr],fr[cr],k);

      dis=pd(x,pre[cr]);

      addx(dis,gl[cr],gr[cr],k);

    }

  if(dis)add(dis,fl[cr],fr[cr],k);

}

int main()

{

  n=rdn(); rg int Q=rdn();

  for(rg int i=;i<=n;i++)w[i]=rdn();

  for(rg int i=,u,v;i<n;i++)u=rdn(),v=rdn(),add(u,v),add(v,u);

  init_dis();

  mn=N;getrt(,,n);init(rt,,,n);

  rg int op,x,k;

  while(Q--)

    {

      op=rdn();x=rdn()^ans;k=rdn()^ans;if(!op)ans=;//if()

      if(!op) query(x,x,k,k),wrt(ans);//,printf("%d\n",ans);

      else mdfy(x,k-w[x],x,),w[x]=k;

    }

  return ;

}

看了半天题解，写成线段树版本。还是 TTT 。

如果给这份代码写上很多 inline 和 register ，就会在 bzoj 上 CE 。会报错 l+r>>1 位置没加括号，然而加上之后会没有错误信息地 CE 。也不知是怎么回事。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ls Ls[cr]

#define rs Rs[cr]

using namespace std;

const int N=1e5+,M=N*,K=;

int n,w[N],hd[N],xnt,to[N<<],nxt[N<<],ans;

int tot,dep[N],ps[N],st[N<<][K+],lg[N<<],bin[K+];//st[N<<1]

int mn,rot,siz[N],pre[N],rt[N<<],sm[M],Ls[M],Rs[M];

bool vis[N];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int dg[];

void wrt(int x)

{

  if(!x){puts("");return;}

  int tt=;while(x)dg[++tt]=x%,x/=;

  for(;tt;tt--)putchar(dg[tt]+'');puts("");

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

void init_dfs(int cr,int fa)

{

  dep[cr]=dep[fa]+;ps[cr]=++tot;st[tot][]=dep[cr];

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)init_dfs(v,cr),st[++tot][]=dep[cr];//

}

void init_dis()

{

  init_dfs(,);

  lg[]=;for(int i=;i<=tot;i++)lg[i]=lg[i>>]+;//lg[1]=0!

  bin[]=;for(int i=;i<=lg[tot];i++)bin[i]=bin[i-]<<;

  for(int t=;t<=lg[tot];t++)

    for(int i=;i+bin[t]-<=tot;i++)

      st[i][t]=Mn(st[i][t-],st[i+bin[t-]][t-]);//bin[t-1]!!

}

int pd(int x,int y)

{

  int u=ps[x],v=ps[y];if(u>v)swap(u,v);

  int t=lg[v-u+],d=Mn(st[u][t],st[v-bin[t]+][t]);

  return dep[x]-d+dep[y]-d;

}

void getrt(int cr,int fa,int s)

{

  siz[cr]=;int mx=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)

      {

    getrt(v,cr,s);siz[cr]+=siz[v];mx=Mx(mx,siz[v]);

      }

  mx=Mx(mx,s-siz[cr]); if(mx<mn)mn=mx,rot=cr;

}

void init(int cr,int s)

{

  vis[cr]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]])

      {

    int ts=(siz[v]<siz[cr]?siz[v]:s-siz[cr]);

    mn=N;getrt(v,cr,ts);pre[rot]=cr;init(rot,ts);

      }

}

int qry(int l,int r,int cr,int R)

{

  if(!cr)return ;

  if(r<=R)return sm[cr]; int mid=l+r>>;

  if(R>mid)return sm[ls]+qry(mid+,r,rs,R);

  return qry(l,mid,ls,R);

}

void mdfy(int l,int r,int &cr,int p,int k)

{

  if(!cr)cr=++tot; sm[cr]+=k;

  if(l==r)return;  int mid=l+r>>;

  if(p<=mid)mdfy(l,mid,ls,p,k);

  else mdfy(mid+,r,rs,p,k);

}

void query(int cr,int yd)

{

  int x=cr,dis=yd; ans+=qry(,n,rt[cr],dis);

  for(;pre[cr];cr=pre[cr])

    {

      dis=yd-pd(x,pre[cr]); if(dis<)continue;

      ans+=qry(,n,rt[pre[cr]],dis);

      ans-=qry(,n,rt[cr+n],dis);

    }

}

void mdfy(int cr,int k)

{

  int x=cr,dis; mdfy(,n,rt[cr],,k);

  for(;pre[cr];cr=pre[cr])

    {

      dis=pd(x,pre[cr]);

      mdfy(,n,rt[pre[cr]],dis,k);

      mdfy(,n,rt[cr+n],dis,k);

    }

}

int main()

{

  n=rdn(); int Q=rdn();

  for(int i=;i<=n;i++)w[i]=rdn();

  for(int i=,u,v;i<n;i++)u=rdn(),v=rdn(),add(u,v),add(v,u);

  init_dis();  tot=;

  mn=N;getrt(,,n);init(rot,n);

  for(int i=;i<=n;i++)mdfy(i,w[i]);

  int op,x,k;

  while(Q--)

    {

      op=rdn();x=rdn()^ans;k=rdn()^ans;if(!op)ans=;//if()

      if(!op) query(x,k),wrt(ans);

      else mdfy(x,k-w[x]),w[x]=k;

    }

  return ;

}

最后写了 vector 实现的树状数组。 v . resize( k ) 可以给 v 开出 k 大小，角标是 0 到 k-1 。

人家还存下来了每个点的 log 个点分树上祖先以及自己到它们的距离，感觉好清爽。（速度也变快了？）

树状数组查不到 0 位置的值，所以那里手动加上 w[cr] （就和自己第一个版本一样）。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int N=1e5+,K=;

int n,w[N],hd[N],xnt,to[N<<],nxt[N<<],ans,mn,rt,siz[N];

int dep[N],pre[N][K],fsz[N],gsz[N],dis[N][K]; vector<int> f[N],g[N];

bool vis[N];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int dg[];

void wrt(int x)

{

  if(!x){puts("");return;}

  int tt=;while(x)dg[++tt]=x%,x/=;

  for(;tt;tt--)putchar(dg[tt]+'');puts("");

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

void add(int cr,int x,int k){for(x=Mn(x,fsz[cr]);x&&x<=fsz[cr];x+=(x&-x))f[cr][x]+=k;}//x&&...

int qry(int cr,int x){int ret=;for(x=Mn(x,fsz[cr]);x;x-=(x&-x))ret+=f[cr][x];return ret+w[cr];}

void addx(int cr,int x,int k){for(x=Mn(x,gsz[cr]);x&&x<=gsz[cr];x+=(x&-x))g[cr][x]+=k;}

int qryx(int cr,int x){int ret=;for(x=Mn(x,gsz[cr]);x;x-=(x&-x))ret+=g[cr][x];return ret;}

void getrt(int cr,int fa,int s)

{

  siz[cr]=;int mx=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)

      {

    getrt(v,cr,s);siz[cr]+=siz[v];mx=Mx(mx,siz[v]);

      }

  mx=Mx(mx,s-siz[cr]); if(mx<mn)mn=mx,rt=cr;

}

void dfs(int cr,int fa,int ds)

{

  pre[cr][++dep[cr]]=rt;dis[cr][dep[cr]]=ds;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)dfs(v,cr,ds+);

}

void init(int cr,int s)

{

  fsz[cr]=mn;gsz[cr]=(mn<<)+;

  f[cr].resize(fsz[cr]+);g[cr].resize(gsz[cr]+);

  vis[cr]=;dfs(cr,,);

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]])

      {

    int ts=(siz[v]<siz[cr]?siz[v]:s-siz[cr]);

    mn=N;getrt(v,cr,ts);init(rt,ts);

      }

}

void query(int cr,int yd)

{

  ans+=qry(cr,yd);

  for(int i=dep[cr]-;i;i--)

    {

      if(dis[cr][i]>yd)continue;

      ans+=qry(pre[cr][i],yd-dis[cr][i]);

      ans-=qryx(pre[cr][i+],yd-dis[cr][i]);

    }

}

void mdfy(int cr,int k)

{

  for(int i=dep[cr]-;i;i--)

    {

      add(pre[cr][i],dis[cr][i],k);

      addx(pre[cr][i+],dis[cr][i],k);

    }

}

int main()

{

  n=rdn(); int Q=rdn();

  for(int i=;i<=n;i++)w[i]=rdn();

  for(int i=,u,v;i<n;i++)u=rdn(),v=rdn(),add(u,v),add(v,u);

  mn=N;getrt(,,n);init(rt,n);

  for(int i=;i<=n;i++)mdfy(i,w[i]);

  int op,x,k;

  while(Q--)

    {

      op=rdn();x=rdn()^ans;k=rdn()^ans;if(!op)ans=;//if()

      if(!op) query(x,k),wrt(ans);

      else mdfy(x,k-w[x]),w[x]=k;

    }

  return ;

}

巴特西

bzoj 3730 震波——动态点分治+树状数组

最新文章

热门文章