UOJ 55 【WC2014】紫荆花之恋—

点分治。在点分树上每个点上用 splay 维护管辖的点的情况。做几次就重构点分树。TLE。只能过 20 分。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

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 Mn(int a,int b){return a<b?a:b;}

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

const int N=1e5+,base=,K=base+,M=N*K,mod=1e9;//K not log!!!//K=base+log

int n,hd[N],xnt,to[N<<],nxt[N<<],w[N<<],r[N],sz[N],mn,Rt; ll ans;

int rt[][N],tot,c[M][],vl[M],siz[M],fa[M],pre[N][K],dis[N][K],dep[N];

bool vis[N];

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

void pshp(int cr){siz[cr]=siz[c[cr][]]+siz[c[cr][]]+;}

void rotate(int x)

{

  int y=fa[x],z=fa[y],d=(x==c[y][]);

  if(z)c[z][y==c[z][]]=x;

  fa[x]=z;

  fa[c[x][!d]]=y; fa[y]=x;

  c[y][d]=c[x][!d]; c[x][!d]=y;

  pshp(y);pshp(x);

}

void splay(int x)

{

  while(fa[x])

    {

      int y=fa[x],z=fa[y];

      if(z)

    ((x==c[y][])^(y==c[z][]))?rotate(x):rotate(y);

      rotate(x);

    }

}

void inst(int &cr,int v,int pr)

{

  if(!cr){cr=++tot;c[cr][]=c[cr][]=;fa[cr]=pr;vl[cr]=v;siz[cr]=;return;}

  siz[cr]++;

  if(v<=vl[cr])inst(c[cr][],v,cr);

  else inst(c[cr][],v,cr);

}

void ins(int x,int v,bool fx)

{

  inst(rt[fx][x],v,);splay(tot);rt[fx][x]=tot;

}

int fnd(int cr,int v)

{

  if(!cr)return -;

  int ret=(vl[cr]>=v?fnd(c[cr][],v):fnd(c[cr][],v));

  if(ret==-&&vl[cr]>=v)ret=cr;

  return ret;

}

void dfsx(int cr)

{

  int ls=c[cr][],rs=c[cr][];

  printf("  cr=%d(%d %d) c0=%d(%d %d) c1=%d(%d %d)\n",

     cr,vl[cr],siz[cr],ls,vl[ls],siz[ls],rs,vl[rs],siz[rs]);

  if(ls)dfsx(ls); if(rs)dfsx(rs);

}

int qry(int x,int v,bool fx)

{

  int cr=fnd(rt[fx][x],v);

  if(cr==-)return ; splay(cr); rt[fx][x]=cr;

  return siz[c[cr][]]+;

}

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

{

  sz[cr]=;int mx=;

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

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

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

  mx=Mx(mx,s-sz[cr]); if(mx<mn)mn=mx,Rt=cr;

}

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

{

  pre[cr][++dep[cr]]=Rt;dis[cr][dep[cr]]=d;

  ins(Rt,r[cr]-d,);if(dep[cr]>)ins(Rt,r[cr]-dis[cr][dep[cr]-],);

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

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

}

void solve(int cr,int s)

{

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

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

    {

      if(vis[v=to[i]])continue;

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

      mn=N;getrt(v,cr,ts);solve(Rt,ts);

    }

}

void cz(int s)

{

  tot=;

  for(int i=;i<=s;i++)vis[i]=;for(int i=;i<=s;i++)dep[i]=;

  for(int i=;i<=s;i++)rt[][i]=rt[][i]=;

  mn=N;getrt(,,s);solve(Rt,s);

}

int main()

{

  int bh=rdn();n=rdn();int pr=rdn()%mod,tw=rdn();r[]=rdn();puts("");

  ins(,r[],);dep[]=;dis[][]=;pre[][]=;

  for(int i=,T=;i<=n;i++,T++)

    {

      if(T==base)cz(i-),T=;

      pr=rdn()^(ans%mod);tw=rdn();r[i]=rdn();

      add(pr,i,tw);add(i,pr,tw);

      for(int j=;j<=dep[pr];j++)

    {

      pre[i][j]=pre[pr][j];dis[i][j]=dis[pr][j]+tw;

      ins(pre[i][j],r[i]-dis[i][j],);

      if(j>)ins(pre[i][j],r[i]-dis[i][j-],);

    }

      dep[i]=dep[pr]+;pre[i][dep[i]]=i;

      ins(i,r[i],);if(dep[i]>)ins(i,r[i]-dis[i][dep[i]-],);

      for(int j=;j<dep[i];j++)

    {

      int u=pre[i][j],v=pre[i][j+],d=dis[i][j]-r[i];

      ans+=qry(u,d,);

      ans-=qry(v,d,);

    }

      printf("%lld\n",ans);

    }

  return ;

}

写对拍的话，可以这样生成，就是在 mk.cpp 里调用写好的程序 a.cpp 得到 ans 。可以把 a.cpp 删掉 main 函数改成 a.hpp 。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

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 Mn(int a,int b){return a<b?a:b;}

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

const int N=,base=,K=base+,M=N*K,mod=1e9;//K not log!!!//K=base+log

int n,hd[N],xnt,to[N<<],nxt[N<<],w[N<<],r[N],sz[N],mn,Rt; ll ans;

int rt[][N],tot,c[M][],vl[M],siz[M],fa[M],pre[N][K],dis[N][K],dep[N];

bool vis[N];

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

void pshp(int cr){siz[cr]=siz[c[cr][]]+siz[c[cr][]]+;}

void rotate(int x)

{

  int y=fa[x],z=fa[y],d=(x==c[y][]);

  if(z)c[z][y==c[z][]]=x;

  fa[x]=z;

  fa[c[x][!d]]=y; fa[y]=x;

  c[y][d]=c[x][!d]; c[x][!d]=y;

  pshp(y);pshp(x);

}

void splay(int x)

{

  while(fa[x])

    {

      int y=fa[x],z=fa[y];

      if(z)

    ((x==c[y][])^(y==c[z][]))?rotate(x):rotate(y);

      rotate(x);

    }

}

void inst(int &cr,int v,int pr)

{

  if(!cr){cr=++tot;c[cr][]=c[cr][]=;fa[cr]=pr;vl[cr]=v;siz[cr]=;return;}

  siz[cr]++;

  if(v<=vl[cr])inst(c[cr][],v,cr);

  else inst(c[cr][],v,cr);

}

void ins(int x,int v,bool fx)

{

  inst(rt[fx][x],v,);splay(tot);rt[fx][x]=tot;

}

int fnd(int cr,int v)

{

  if(!cr)return -;

  int ret=(vl[cr]>=v?fnd(c[cr][],v):fnd(c[cr][],v));

  if(ret==-&&vl[cr]>=v)ret=cr;

  return ret;

}

void dfsx(int cr)

{

  int ls=c[cr][],rs=c[cr][];

  printf("  cr=%d(%d %d) c0=%d(%d %d) c1=%d(%d %d)\n",

     cr,vl[cr],siz[cr],ls,vl[ls],siz[ls],rs,vl[rs],siz[rs]);

  if(ls)dfsx(ls); if(rs)dfsx(rs);

}

int qry(int x,int v,bool fx)

{

  int cr=fnd(rt[fx][x],v);

  if(cr==-)return ; splay(cr); rt[fx][x]=cr;

  return siz[c[cr][]]+;

}

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

{

  sz[cr]=;int mx=;

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

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

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

  mx=Mx(mx,s-sz[cr]); if(mx<mn)mn=mx,Rt=cr;

}

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

{

  pre[cr][++dep[cr]]=Rt;dis[cr][dep[cr]]=d;

  ins(Rt,r[cr]-d,);if(dep[cr]>)ins(Rt,r[cr]-dis[cr][dep[cr]-],);

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

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

}

void solve(int cr,int s)

{

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

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

    {

      if(vis[v=to[i]])continue;

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

      mn=N;getrt(v,cr,ts);solve(Rt,ts);

    }

}

void cz(int s)

{

  tot=;

  for(int i=;i<=s;i++)vis[i]=;for(int i=;i<=s;i++)dep[i]=;

  for(int i=;i<=s;i++)rt[][i]=rt[][i]=;

  mn=N;getrt(,,s);solve(Rt,s);

}

a.hpp

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<ctime>

#define ll long long

#include "a.hpp"

using namespace std;

const int M1=,M2=;

int main()

{

  srand(time());srand(rand());

  n=N;//n=rand()%N+1;

  printf("%d\n%d\n",rand()%+,n);

  r[]=rand()%M2+;

  printf("0 0 %d\n",r[]);

  ins(,r[],);dep[]=;dis[][]=;pre[][]=;

  int pr,tw;

  for(int i=,T=;i<=n;i++,T++)

    {

      if(T==base)cz(i-),T=;

      pr=rand()%(i-)+;

      tw=rand()%M1+;r[i]=rand()%M2+;

      printf("%lld %d %d\n",pr^(ans%mod),tw,r[i]);

      add(pr,i,tw);add(i,pr,tw);

      for(int j=;j<=dep[pr];j++)

    {

      pre[i][j]=pre[pr][j];dis[i][j]=dis[pr][j]+tw;

      ins(pre[i][j],r[i]-dis[i][j],);

      if(j>)ins(pre[i][j],r[i]-dis[i][j-],);

    }

      dep[i]=dep[pr]+;pre[i][dep[i]]=i;

      ins(i,r[i],);if(dep[i]>)ins(i,r[i]-dis[i][dep[i]-],);

      for(int j=;j<dep[i];j++)

    {

      int u=pre[i][j],v=pre[i][j+],d=dis[i][j]-r[i];

      ans+=qry(u,d,);

      ans-=qry(v,d,);

    }

    }

  return ;

}

mk.cpp

尝试改一改。设一个 base ，重构点分树只重构不平衡的那部分。再把 splay 的一些操作写成非递归的，就能过 85 分。主要是 r <= 10 的数据过不了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

#define db double

#define pb push_back

#define ls c[cr][0]

#define rs c[cr][1]

using namespace std;

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 Mn(int a,int b){return a<b?a:b;}

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

const int N=1e5+,K=,M=N*K,mod=1e9; const db base=0.77;

int n,hd[N],xnt,to[N<<],nxt[N<<],w[N<<],r[N],sz[N],mn,Rt; ll ans;

int rt[][N],tot,c[M][],vl[M],siz[M],fa[M],pre[N][K],dis[N][K],dep[N];

int delpl[M],top; bool vis[N];

vector<int> vt[N];

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

void pshp(int cr){siz[cr]=siz[c[cr][]]+siz[c[cr][]]+;}

void rotate(int x)

{

  int y=fa[x],z=fa[y],d=(x==c[y][]);

  if(z)c[z][y==c[z][]]=x;

  fa[x]=z;

  fa[c[x][!d]]=y; fa[y]=x;

  c[y][d]=c[x][!d]; c[x][!d]=y;

  pshp(y);pshp(x);

}

void splay(int x)

{

  for(int y,z;fa[x];rotate(x))

    {

      y=fa[x];z=fa[y];

      if(z) ((x==c[y][])^(y==c[z][]))?rotate(x):rotate(y);

    }

}

int nwnd()

{

  int ret=(top?delpl[top--]:++tot);

  c[ret][]=c[ret][]=;siz[ret]=;return ret;

}

void ins(int x,int v,bool fx,bool nd)

{

  if(!rt[fx][x]){rt[fx][x]=nwnd();vl[rt[fx][x]]=v;fa[rt[fx][x]]=;return;}

  int cr=rt[fx][x],pr=;

  while()

    {

      siz[cr]++;pr=cr;

      if(v<=vl[cr])

    {

      if(!ls){ls=nwnd();fa[ls]=cr;vl[ls]=v;break;}

      cr=ls;

    }

      else

    {

      if(!rs){rs=nwnd();fa[rs]=cr;vl[rs]=v;break;}

      cr=rs;

    }

    }

  if(nd)splay(cr),rt[fx][x]=cr;

}

void dfs_del(int cr)

{

  delpl[++top]=cr;

  if(ls)dfs_del(ls);if(rs)dfs_del(rs);

}

void del(int cr)

{

  dfs_del(rt[][cr]);if(dep[cr]>)dfs_del(rt[][cr]);

  rt[][cr]=rt[][cr]=;

}

int fnd(int cr,int v)

{

  int ret=-;

  while(cr)

    {

      if(vl[cr]>=v)ret=cr,cr=ls;

      else cr=rs;

    }

  return ret;

}

int qry(int x,int v,bool fx)

{

  int cr=fnd(rt[fx][x],v);

  if(cr==-)return ; splay(cr); rt[fx][x]=cr;

  return siz[rs]+;

}

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

{

  sz[cr]=;int mx=;

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

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

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

  mx=Mx(mx,s-sz[cr]); if(mx<mn)mn=mx,Rt=cr;

}

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

{

  pre[cr][++dep[cr]]=Rt;dis[cr][dep[cr]]=d;

  vt[Rt].pb(cr);

  ins(Rt,r[cr]-d,,);if(dep[cr]>)ins(Rt,r[cr]-dis[cr][dep[cr]-],,);

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

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

}

void solve(int cr,int s)

{

  vis[cr]=;vt[cr].clear();rt[][cr]=rt[][cr]=;

  dfs(cr,,);

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

    {

      if(vis[v=to[i]])continue;

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

      mn=N;getrt(v,cr,ts);solve(Rt,ts);

    }

}

void cz(int cr)

{

  int s=vt[cr].size();

  for(int i=,d,t=dep[cr]-;i<s;i++)

    {d=vt[cr][i];vis[d]=;del(d);dep[d]=t;}//t!!

  mn=N;getrt(cr,,s);solve(Rt,s);

}

int main()

{

  int bh=rdn();n=rdn();int pr=rdn()%mod,tw=rdn();r[]=rdn();puts("");

  ins(,r[],,);dep[]=;dis[][]=;pre[][]=;vt[].pb();vis[]=;

  bh=;

  for(int i=;i<=n;i++)

    {

      pr=rdn()^(ans%mod);tw=rdn();r[i]=rdn();

      add(pr,i,tw);add(i,pr,tw);

      for(int j=,u,v;j<=dep[pr];j++,v=u)

    {

      u=pre[i][j]=pre[pr][j];dis[i][j]=dis[pr][j]+tw;

      ins(u,r[i]-dis[i][j],,);

      if(j>)ins(u,r[i]-dis[i][j-],,);

      vt[u].pb(i);

      if(!bh&&j>&&vt[u].size()>vt[v].size()*base)bh=v;

    }

      dep[i]=dep[pr]+;pre[i][dep[i]]=i; vis[i]=;

      ins(i,r[i],,);if(dep[i]>)ins(i,r[i]-dis[i][dep[i]-],,);

      vt[i].pb(i);

      for(int j=;j<dep[i];j++)

    {

      int u=pre[i][j],v=pre[i][j+],d=dis[i][j]-r[i];

      ans+=qry(u,d,);

      ans-=qry(v,d,);

    }

      printf("%lld\n",ans);

      if(bh)cz(bh),bh=;

    }

  return ;

}

然后学习一下 SBT ，还是过不了，有 80 分。于是不想管了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

#define db double

#define pb push_back

#define ls c[cr][0]

#define rs c[cr][1]

using namespace std;

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 Mn(int a,int b){return a<b?a:b;}

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

const int N=1e5+,K=,M=N*K,mod=1e9; const db base=0.77;

int n,hd[N],xnt,to[N<<],nxt[N<<],w[N<<],r[N],sz[N],mn,Rt; ll ans;

int rt[][N],tot,c[M][],vl[M],siz[M],fa[M],pre[N][K],dis[N][K],dep[N];

int delpl[M],top; bool vis[N];

vector<int> vt[N];

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

void pshp(int cr){siz[cr]=siz[c[cr][]]+siz[c[cr][]]+;}

void rotate(int &cr,int d)

{

  int y=c[cr][!d];

  c[cr][!d]=c[y][d];  c[y][d]=cr;

  pshp(cr); pshp(y);  cr=y;

}

void maintain(int cr,int d)

{

  if(siz[c[c[cr][d]][d]]>siz[cr])rotate(cr,!d);

  else if(siz[c[c[cr][d]][!d]]>siz[cr])rotate(c[cr][d],d),rotate(cr,!d);

  else return;///

  maintain(ls,);  maintain(rs,);

  maintain(cr,);  maintain(cr,);

}

int nwnd()

{

  int cr=(top?delpl[top--]:++tot);

  siz[cr]=;return cr;

}

void ins(int &cr,int v,int pr=)

{

  if(!cr){cr=nwnd();fa[cr]=pr;vl[cr]=v;return;}

  siz[cr]++;

  bool d=(v>vl[cr]); ins(c[cr][d],v,cr); maintain(cr,d);

}

void del(int &cr)

{

  delpl[++top]=cr;

  if(ls)del(ls);if(rs)del(rs); cr=;

}

int qry(int cr,int v)

{

  if(!cr)return ;

  if(vl[cr]>=v)return siz[rs]++qry(ls,v);

  return qry(rs,v);

}

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

{

  sz[cr]=;int mx=;

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

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

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

  mx=Mx(mx,s-sz[cr]); if(mx<mn)mn=mx,Rt=cr;

}

void dfs(int cr,int fa,int d,int t)

{

  pre[cr][++dep[cr]]=Rt;dis[cr][dep[cr]]=d;

  vt[Rt].pb(cr);

  ins(rt[][Rt],r[cr]-d);if(t)ins(rt[][Rt],r[cr]-dis[cr][t]);

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

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

}

void solve(int cr,int s,int t)//t:dep[Rt]-1

{

  vis[cr]=;vt[cr].clear();rt[][cr]=rt[][cr]=;

  dfs(cr,,,t);

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

    {

      if(vis[v=to[i]])continue;

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

      mn=N;getrt(v,cr,ts);solve(Rt,ts,t+);

    }

}

void cz(int cr)

{

  int s=vt[cr].size(),t=dep[cr]-;//t!!

  for(int i=,d;i<s;i++)

    {d=vt[cr][i];vis[d]=;del(rt[][d]);if(dep[d]>)del(rt[][d]);dep[d]=t;}

  mn=N;getrt(cr,,s);solve(Rt,s,t);

}

int main()

{

  int bh=rdn();n=rdn();int pr=rdn()%mod,tw=rdn();r[]=rdn();puts("");

  ins(rt[][],r[]);dep[]=;dis[][]=;pre[][]=;vt[].pb();vis[]=;

  bh=;

  for(int i=;i<=n;i++)

    {

      pr=rdn()^(ans%mod);tw=rdn();r[i]=rdn();

      add(pr,i,tw);add(i,pr,tw);

      vis[i]=; dep[i]=dep[pr]+; int lm=dep[i];//vis[]

      for(int j=,u,v;j<=lm;j++,v=u)

    {

      u=pre[i][j]=(j==lm?i:pre[pr][j]);

      dis[i][j]=(j==lm?:dis[pr][j]+tw);

      ins(rt[][u],r[i]-dis[i][j]);

      if(j>)ins(rt[][u],r[i]-dis[i][j-]);

      vt[u].pb(i);

      if(!bh&&j>&&vt[u].size()>vt[v].size()*base)bh=v;

    }

      for(int j=,u=pre[i][j],v,d;j<lm;j++,u=v)

    {

      v=pre[i][j+];d=dis[i][j]-r[i];

      ans+=qry(rt[][u],d);

      ans-=qry(rt[][v],d);

    }

      printf("%lld\n",ans);

      if(bh)cz(bh),bh=;

    }

  return ;

}

巴特西

UOJ 55 【WC2014】紫荆花之恋——点分治+平衡树

最新文章

热门文章