BZOJ3435: [Wc2014]紫荆花之恋
https://lydsy.com/JudgeOnline/problem.php?id=3435
分析:
- 如果不强制在线，可以将树存下来用点分树来查询和修改。
- 即(dis(i,j)-R_jle R_i)，是个使用点分树维护的经典问题。
- 如果每次直接插到父亲下面会使得点分树不平衡，利用替罪羊重构的思想在不平衡的时候重构一下即可，这里重构一下即对这个子树(连通块)进行点分治。
- 内层如果用线段树会炸空间，于是我内层也使用替罪羊来维护。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 100050
#define M 14000000
#define ls ch[p][0]
#define rs ch[p][1]
#define get(x) (ch[f[x]][1]==x)
typedef long long ll;
#define AL1 0.8
#define AL2 0.9
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
int x=0,f=1; char s=nc();
while(s<'0') {if(s=='-') f=-1; s=nc();}
while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();
return x*f;
}
int head[N],to[N<<1],nxt[N<<1],fa[N][20],Lg[N],dep[N],cnt;
ll dis[N];
int sz[M],rr[N],ch[M][2],f[M],val[M],reimu,n,fb[N],tot;
int Sta[M],top;
vector<int>V[N];
int all[N],vis[N],visc,siz[N],fk[N],rot,used[N];
#define GG(p) (max(sz[ls],sz[rs])>AL1*sz[p])
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
int newnode(int v) {
int p;
if(!top) p=++reimu;
else {
p=Sta[top--];
sz[p]=ls=rs=f[p]=0;
}
val[p]=v;
return p;
}
int S[M],tp,koishi;
struct SGT {
int root;
void insert(int &p,int v,int fa) {
if(!p) {
p=newnode(v); sz[p]=1; f[p]=fa; return ;
}
sz[p]++;
if(val[p]>v) insert(ls,v,p);
else insert(rs,v,p);
if(GG(p)) koishi=p;
}
int ask(int p,int x) {
if(!p) return 0;
if(val[p]<=x) return ask(rs,x)+sz[ls]+1;
else return ask(ls,x);
}
void dfs(int p) {
if(ls) dfs(ls);
S[++tp]=p;
if(rs) dfs(rs);
}
int build(int l,int r,int fa) {
int mid=(l+r)>>1,p=S[mid];
f[p]=fa; ls=rs=0;
if(!f[p]) root=p;
if(l<mid) ls=build(l,mid-1,p);
if(r>mid) rs=build(mid+1,r,p);
sz[p]=sz[ls]+sz[rs]+1;
return p;
}
void Ins(int v) {
koishi=0;
insert(root,v,0);
if(koishi) {
tp=0;
int k=get(koishi),fa=f[koishi];
dfs(koishi);
ch[fa][k]=build(1,tp,fa);
}
}
void asd(int p) {
if(ls) asd(ls);
Sta[++top]=p;
if(rs) asd(rs);
}
void rec() {
asd(root); root=0;
}
}F[N][2];
int lca(int x,int y) {
int i;
if(dep[x]<dep[y]) swap(x,y);
for(i=Lg[dep[x]];i>=0;i--) {
if(fa[x][i]&&dep[fa[x][i]]>=dep[y]) x=fa[x][i];
}
if(x==y) return x;
for(i=Lg[dep[x]];i>=0;i--) if(fa[x][i]&&fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
ll Dis(int x,int y) {return dis[x]+dis[y]-2*dis[lca(x,y)];}
void gr(int x,int y) {
int i;
siz[x]=1; fk[x]=0;
for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]&&vis[to[i]]==visc) {
gr(to[i],x); siz[x]+=siz[to[i]];
fk[x]=max(fk[x],siz[to[i]]);
}
fk[x]=max(fk[x],tot-siz[x]);
if(fk[x]<fk[rot]) rot=x;
}
void gd(int x,int y,int rt) {
int i;
all[rt]++;
F[rt][0].Ins(Dis(x,rt)-rr[x]);
F[rt][1].Ins(Dis(x,fb[rt])-rr[x]);
V[rt].push_back(x);
for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]&&vis[to[i]]==visc) {
gd(to[i],x,rt);
}
}
void solve(int x) {
used[x]=1;
int i,al=tot;
V[x].clear();
all[x]=0;
F[x][0].rec(); F[x][1].rec();
gd(x,0,x);
for(i=head[x];i;i=nxt[i]) if(!used[to[i]]&&vis[to[i]]==visc) {
tot=siz[to[i]]; if(tot>siz[x]) tot=al-siz[x];
rot=0; gr(to[i],x); fb[rot]=x; solve(rot);
}
}
void update(int x) {
int t;
int kksk=0;
for(t=x;t;t=fb[t]) {
all[t]++;
F[t][0].Ins(Dis(x,t)-rr[x]);
F[t][1].Ins(Dis(x,fb[t])-rr[x]);
V[t].push_back(x);
}
for(t=x;fb[t];t=fb[t]) {
if(all[t]>all[fb[t]]*AL2) {
kksk=fb[t];
}
}
if(kksk) {
int p=kksk;
int i,lim=V[p].size(),ff=fb[p];
visc++;
for(i=0;i<lim;i++) {
vis[V[p][i]]=visc;
used[V[p][i]]=0;
}
rot=0;
tot=lim;
gr(p,0);
fb[rot]=ff;
solve(rot);
}
}
int query(int x,int k) {
int t,re=0,lst=0;
ll len;
for(t=x;t;t=fb[t]) {
len=Dis(x,t);
re+=F[t][0].ask(F[t][0].root,k-len);
if(lst) re-=F[lst][1].ask(F[lst][1].root,k-len);
lst=t;
}
return re;
}
int main() {
fk[0]=1<<30;
rd(); n=rd();
int i,x,y,j;
rd(); rd(); rr[1]=rd();
for(i=1,Lg[0]=-1;i<=n;i++) Lg[i]=Lg[i>>1]+1;
dep[1]=1;
ll ans=0;
F[1][0].Ins(-rr[1]);
V[1].push_back(1);
all[1]=1;
puts("0");
for(i=2;i<=n;i++) {
x=rd(); y=rd(); rr[i]=rd();
x^=(ans%1000000000);
dis[i]=dis[x]+y; dep[i]=dep[x]+1; fa[i][0]=x; fb[i]=x;
for(j=1;(1<<j)<=n;j++) fa[i][j]=fa[fa[i][j-1]][j-1];
add(x,i); add(i,x);
ans+=query(i,rr[i]);
printf("%lld
",ans);
update(i);
}
}