【bzoj3435】[Wc2014]紫荆花之恋

2015.06.10 19:44 Wed | 10次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给出一颗树,每个点有权值ri,每次加一个点,在线求当前有多少点对满足dis(i,j)<=ri+rj.n<=100000
题解
这题写的真是爽……首先把公式变形,令p=lca(i,j),设dis[i]表示i根的距离,则dis(i,j)=dis[i]+dis[j]-2*dis[p],移项可得r[i]-(dis[i]-dis[p])>=dis[j]-dis[p]-r[j],于是我们可以对每一个i到根的路径上的节点p维护一个treap,存的是所有节点的dis[j]-dis[p]-r[j]值,因为可能会算重复,比如lca不等于p的点对在以p为根的子树中依然满足条件,于是我们对每个p的子节点再搞一个treap,存的是r[i]-(dis[i]-dis[p])和父亲的第一个treap一样的东西,这样累计答案的时候加上p的,减去p的儿子的就可以去除重复的了。
这样的时间复杂度是多少呢?每次查询,插入是logn的,并且总的还要乘上一个数的高度。假设树是一条链,那么时间复杂度退化为n^2logn,空间也是n^2,tle+mle
于是我们希望把树的高度变得平衡一点,可以采用点分治的做法,但是这道题动态加点啊,如何点分治?这个的解决办法借用了替罪羊树的思想——暴力重构!每当点数不平衡后,重新搞一个点分治就好了。这样做的复杂度大概是n*log^2n的。
说一下细节:
第一、在重构的时候要处理好树分治中点的连接关系,不要把儿子重构了却忘记更新父亲。
第二、内存池是必须的。
第三、一条链的数据栈空间卡的死死的,能不定义的变量尽量别定义,能少传参一定少传参,有可能多一个就RE到死。
第四、不要看错题,是答案先取模1000000000再和f异或……
我不会告诉你们我因为后两条调了一下午……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#define N 200000
#define M 15000005
#define ll long long
#define alpha 0.88
#define inf 0x3f3f3f3f
using namespace std;
int asdfghjl;
int n,tot,sz,tim,minn,root;
int deep[N],father[N][18],dis[N],d[N];
int fa[N],r[N],vis[N],siz[N],mx[N];
set<int> son[N];
ll ans;
struct edge
{
    int f,to,next,val,ban;
}e[N<<1];
int h[N],tp;
void ae(int u,int v,int w)
{
    e[tp].f=u;
    e[tp].to=v;
    e[tp].val=w;
    e[tp].next=h[u];
    h[u]=tp++;
}
int get_lca(int x,int y)
{
    int tx=x,ty=y;
    if(x==y) return x;
    if(deep[tx]<deep[ty]) swap(tx,ty);
    int t=deep[tx]-deep[ty];
    for(int i=0;i<18;i++) if(t&(1<<i)) tx=father[tx][i];
    if(tx==ty) return tx;
    for(int i=17;i>=0;i--)
    if(father[tx][i]!=father[ty][i])
    tx=father[tx][i],ty=father[ty][i];
    return father[tx][0];
}
int get_dis(int x,int y)
{
    return dis[x]+dis[y]-2*dis[get_lca(x,y)];
}
struct node
{
    int ls,rs,siz,w,rnd,val;
}tr[M];
int rt1[N],rt2[N];
void update(int x)
{
    tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+tr[x].w;
}
void lturn(int &k)
{
    int t=tr[k].rs;tr[k].rs=tr[t].ls;tr[t].ls=k;
    tr[t].siz=tr[k].siz;update(k);k=t;
}
void rturn(int &k)
{
    int t=tr[k].ls;tr[k].ls=tr[t].rs;tr[t].rs=k;
    tr[t].siz=tr[k].siz;update(k);k=t;
}
void insert(int &x,int v)
{
    if(!x)
    {
        x=tot?d[tot--]:++sz;
        tr[x].ls=tr[x].rs=0;
        tr[x].siz=tr[x].w=1;
        tr[x].rnd=rand();tr[x].val=v;
        return;
    }
    tr[x].siz++;
    if(tr[x].val==v) tr[x].w++;
    else if(tr[x].val<v)
    {
        insert(tr[x].rs,v);
        if(tr[tr[x].rs].rnd<tr[x].rnd) lturn(x);
    }
    else
    {
        insert(tr[x].ls,v);
        if(tr[tr[x].ls].rnd<tr[x].rnd) rturn(x);
    }
}
ll query(int x,int v)
{
    int ret=0;
    while(x)
    {
        if(tr[x].val>v) x=tr[x].ls;
        else ret+=tr[tr[x].ls].siz+tr[x].w,x=tr[x].rs;
    }
    return ret;
}
void erase(int &x)
{
    if(!x) return;
    erase(tr[x].ls);
    erase(tr[x].rs);
    if(tot<N-1) d[++tot]=x;
    x=0;
}
void del(int x)
{
    vis[x]=tim;
    erase(rt1[x]);
    if(vis[fa[x]]==tim) erase(rt2[x]);
    set<int>::iterator it;
    for(it=son[x].begin();it!=son[x].end();it++)
    del(*it);
    son[x].clear();
}
void dfs_size(int u,int f)
{
    siz[u]=mx[u]=1;int i;
    for(i=h[u];i!=-1;i=e[i].next)
    if(vis[e[i].to]==tim&&e[i].ban!=tim&&e[i].to!=f)
    {
        dfs_size(e[i].to,u);
        siz[u]+=siz[e[i].to];
        mx[u]=max(mx[u],siz[e[i].to]);
    }
}
void dfs_root(int u,int f,int tot)
{
    mx[u]=max(mx[u],tot-siz[u]);
    if(mx[u]<minn) minn=mx[u],root=u;
    int i;
    for(i=h[u];i!=-1;i=e[i].next)
    if(vis[e[i].to]==tim&&e[i].ban!=tim&&e[i].to!=f)
    dfs_root(e[i].to,u,tot);
}
void work(int u,int f,int d,int &x)
{
    insert(x,d-r[u]);int i;
    for(i=h[u];i!=-1;i=e[i].next)
    if(vis[e[i].to]==tim&&e[i].ban!=tim&&e[i].to!=f)
    work(e[i].to,u,d+e[i].val,x);
}
int dfs(int u)
{
    minn=inf;
    dfs_size(u,0);dfs_root(u,0,siz[u]);
    int rt=root;
    work(rt,0,0,rt1[rt]);int i,tmp;
    for(i=h[rt];i!=-1;i=e[i].next)
    if(vis[e[i].to]==tim&&e[i].ban!=tim)
    {
        e[i].ban=e[i^1].ban=tim;
        tmp=0;work(e[i].to,rt,e[i].val,tmp);
        int _rt=dfs(e[i].to);fa[_rt]=rt;rt2[_rt]=tmp;
        son[rt].insert(_rt);
    }
    return rt;
}
void rebuild(int x)
{
    tim++;
    int y=fa[x],t=rt2[x];
    if(y) son[y].erase(x);
    del(x);
    int temp=dfs(x);
    fa[temp]=y;rt2[temp]=t;
    if(y) son[y].insert(temp);
}
void insert(int x)
{
    for(int d,i=x;i;i=fa[i])
    {
        if(fa[i])
        {
            int d=get_dis(x,fa[i]);
            ans+=query(rt1[fa[i]],r[x]-d);
            ans-=query(rt2[i],r[x]-d);
            insert(rt2[i],d-r[x]);
        }
        d=get_dis(x,i);
        insert(rt1[i],d-r[x]);
    }
    int flag=0;
    for(int i=x;fa[i];i=fa[i])
    if(tr[rt1[i]].siz>tr[rt1[fa[i]]].siz*alpha) flag=fa[i];
    if(flag) rebuild(flag);
}
int main()
{
    scanf("%*d");cin>>n;
    memset(h,-1,sizeof(h));
    for(int f,w,i=1;i<=n;i++)
    {
        scanf("%lld%d%d",&f,&w,&r[i]);f=f^(ans%1000000000);
        ae(i,f,w);ae(f,i,w);
        dis[i]=dis[f]+w;father[i][0]=f;deep[i]=deep[f]+1;
        for(int k=1;k<18;k++) father[i][k]=father[father[i][k-1]][k-1];
        fa[i]=f;son[f].insert(i);insert(i);
        printf("%lld\n",ans);
    }
    return 0;
}```