UOJ #55 & 洛谷 P3920 紫荆花之恋 —— 动态点分治+替罪羊树

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
typedef long long ll;
int rd()
{
  int ret=0,f=1; char ch=getchar();
  while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0; ch=getchar();}
  while(ch>=‘0‘&&ch<=‘9‘)ret=ret*10+ch-‘0‘,ch=getchar();
  return f?ret:-ret;
}
int Max(int x,int y){return x>y?x:y;}
int const xn=1e5+5,inf=1e9,xm=40;
int n,hd[xn],ct,to[xn<<1],nxt[xn<<1],r[xn],fa[xn],dep[xn],f[xn][20];
int tot,rt[xn],frt[xn],siz[xn*xm],ls[xn*xm],rs[xn*xm];//
int size[xn],root,mx,sta[xn*xm],top;//sta
int v[xn*xm],d[xn];//v
ll ans;
vector<int>pt[xn];
bool vis[xn];
void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}
int lca(int x,int y)
{
  if(dep[x]<dep[y])swap(x,y);
  for(int i=19;i>=0;i--)
    if(dep[f[x][i]]>=dep[y])x=f[x][i];
  for(int i=19;i>=0;i--)
    if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
  if(x==y)return x; return f[x][0];
}
int dist(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
int node(){if(top)return sta[top--]; return ++tot;}
int *flag,tmp[xn*xm],tp;//flag
void dfsx(int x)
{
  if(!x)return;
  dfsx(ls[x]); tmp[++tp]=x; dfsx(rs[x]);
}
void solve(int &x,int l,int r)
{
  if(l>r){x=0; return;}
  int mid=((l+r)>>1); x=tmp[mid];
  if(l==r){ls[x]=rs[x]=0; siz[x]=1; return;}
  solve(ls[x],l,mid-1); solve(rs[x],mid+1,r);
  siz[x]=siz[ls[x]]+siz[rs[x]]+1;
}
void rebuild(int &x)
{
  tp=0; dfsx(x);
  solve(x,1,tp);
}
void ins(int &x,int val)
{
  if(!x){x=node(); v[x]=val; siz[x]=1; return;}
  siz[x]++;
  if(val<=v[x])ins(ls[x],val);
  else ins(rs[x],val);
  if(siz[x]*86<=Max(siz[ls[x]],siz[rs[x]])*100)flag=&x;//
}
void insert(int &x,int val)
{
  flag=0; ins(x,val);
  if(flag)rebuild(*flag);//
}
void del(int &x)
{
  if(!x)return;
  del(ls[x]); del(rs[x]);
  siz[x]=v[x]=0; sta[++top]=x; x=0;
}
void getrt(int x,int ff,int sum)
{
  int nmx=0; size[x]=1;
  for(int i=hd[x],u;i;i=nxt[i])
    {
      if(vis[u=to[i]]||u==ff)continue;
      getrt(u,x,sum); size[x]+=size[u];
      nmx=Max(nmx,size[u]);
    }
  nmx=Max(nmx,sum-size[x]);
  if(mx>nmx)mx=nmx,root=x;
}
void dfs(int x,int ff)
{
  size[x]=1; pt[root].pb(x);
  insert(rt[root],r[x]-dist(x,root));
  if(fa[root])insert(frt[root],r[x]-dist(x,fa[root]));
  for(int i=hd[x],u;i;i=nxt[i])
    if(!vis[u=to[i]]&&u!=ff)dfs(u,x),size[x]+=size[u];
}
void build(int x,int ff,int sum)
{
  vis[x]=1;
  del(rt[x]); del(frt[x]);
  fa[x]=ff; pt[x].clear();//
  dfs(x,0);
  for(int i=hd[x],u;i;i=nxt[i])
    {
      if(vis[u=to[i]])continue;
      //int ns=(size[u]>size[x]?sum-size[x]:size[u]);
      int ns=size[u];
      mx=inf; getrt(u,0,ns); build(root,x,ns);
    }
}
int find(int x,int val)
{
  if(!x)return 0;
  if(val<=v[x])return siz[x]-siz[ls[x]]+find(ls[x],val);
  else return find(rs[x],val);
}
/*
void work(int x)
{
  int fl=0;
  rt[x]=node(); v[rt[x]]=r[x]; vis[x]=1;//
  for(int y=x;y;y=fa[y])
    {
      size[y]++; pt[y].pb(x);
      ll ds=dist(x,y),ds2;
      ans+=find(rt[y],ds-r[x]);
      if(fa[y])ans-=find(frt[y],(ds2=dist(x,fa[y]))-r[x]);
      if(fa[y]==y)exit(0);//--------
      insert(rt[y],r[x]-ds);
      if(fa[y])insert(frt[y],r[x]-ds2);
      if(fa[y]&&size[y]*10>(size[fa[y]]+1)*9)fl=fa[y];
    }
  if(fl)
    {
      for(int i=0;i<pt[fl].size();i++)vis[pt[fl][i]]=0;
      mx=inf; getrt(fl,0,size[fl]); build(root,fa[fl],size[fl]);
    }
}
*/
ll query(int x)
{
  ll ret=0;
  for(int y=x;y;y=fa[y])ret+=find(rt[y],dist(x,y)-r[x]);
  for(int y=x;fa[y];y=fa[y])ret-=find(frt[y],dist(x,fa[y])-r[x]);
  return ret;
}
void work(int x)
{
  int fl=-1;
  for(int y=x;y;y=fa[y])
    {
      size[y]++; pt[y].pb(x);
      insert(rt[y],r[x]-dist(x,y));
      if(fa[y])insert(frt[y],r[x]-dist(x,fa[y]));
      if(fa[y]&&size[y]*10>(size[fa[y]]+1)*8)fl=fa[y];//0
    }
  if(fl!=-1)
    {
      for(int i=0;i<pt[fl].size();i++)vis[pt[fl][i]]=0;
      int sum=size[fl];//
      mx=inf; getrt(fl,0,sum); build(root,fa[fl],sum);
    }
}
void init(int x,int ff,int w)
{
  f[x][0]=ff; d[x]=d[ff]+w; dep[x]=dep[ff]+1; vis[x]=1;//vis!!!
  for(int i=1;i<20&&f[f[x][i-1]][i-1];i++)f[x][i]=f[f[x][i-1]][i-1];
}
int gt[35],gtp;
void wr(ll x)
{
  if(!x){puts("0"); return;}
  if(x<0)putchar(‘-‘),x=-x; gtp=0;
  while(x)gt[++gtp]=x%10,x/=10;
  for(int i=gtp;i;i--)putchar(gt[i]+‘0‘);
  puts("");
}
int main()
{
  int T=rd(); n=rd(); ll lst=0;
  rd(); rd(); r[1]=rd(); vis[1]=1; size[1]=1; dep[1]=1;//
  insert(rt[1],r[1]); pt[1].pb(1); puts("0");
  for(int i=2,x,w;i<=n;i++)
    {
      x=(rd()^(lst%inf)); w=rd(); r[i]=rd();
      add(x,i); add(i,x);
      init(i,x,w); fa[i]=x; //work(i);
      ans+=query(i);
      //printf("%lld\n",lst=ans);
      wr(lst=ans);
      work(i);
    }
  return 0;
}