dwjshift's Blog

bzoj3720 Gty的妹子树

| Comments

原文发表时间:2014-09-19
依然是数据结构题>.<
如果这题只有查询的话显然用线段树合并或者dfs序+可持久化线段树就能在一个log的复杂度内艹过去了。但是这题不仅有修改,还有加点,于是就麻烦了一些。干脆就直接对操作进行分块,k次操作后暴力重建一下可持久化线段树/线段树合并,块内的修改就直接考虑一下对询问的贡献。
如果询问的是块内新添加的点的话就很容易了,直接dfs一遍它的子树就好,因为子树大小不超过k。否则的话,先查询一下它的子树中已经建好的点的答案,然后考虑块内的每个修改/加点操作的节点是否在其子树内,如果是的话就可能会影响答案。具体的细节就看代码吧。代码也比较简单无脑,不到3k。(因为一些sb错误查了好久T_T
然后复杂度是,对着数据调一调k就能跑得很快了。不过实际上这题数据很水,我试过压根不重建都能够1900ms就A掉0.0
当然这题也可以用重量平衡树套线段树维护一下动态的dfs序,复杂度是两个log的,不过写起来应该麻烦很多,算上常数的话效率和按操作分块大概也差不了多少吧……

code

#include <cstdio>
#include <cstring>
#define repu(i,x,y) for (i=x; i<=y; ++i)
#define repe(u) for (edge *i=first[u]; i; i=i->next)
#define mid ((l+r)>>1)
using namespace std;
  
int n,m,i,u,v,w[60100],cnt,p[60100],l[60100],r[60100],tot,x,
t[60100],anc[60100],fa[60100],ans,type,stk[60100],top,qt;
bool flag[60100];
struct edge
{
    int v;
    edge *next;
} poole[90100],*tpe=poole,*first[60100];
struct node
{
    int s;
    node *lc,*rc;
} pool[2000000],*tp=pool,*root[60100];
  
void addedge(int u,int v)
{
    tpe->v=v,tpe->next=first[u],first[u]=tpe++;
}
  
void dfs(int u)
{
    p[l[u]=++cnt]=u;
    repe(u)
        if (i->v!=fa[u])
            fa[i->v]=u,dfs(i->v);
    r[u]=cnt;
}
  
void insert(node *now,int w)
{
    long long l=0,r=2147483647;
    while (l<r)
    {
        (++tp)->s=now->s+1;
        if (w<=mid)
            tp->lc=tp+1,tp->rc=now->rc,now=now->lc,r=mid;
        else
            tp->rc=tp+1,tp->lc=now->lc,now=now->rc,l=mid+1;
    }
    (++tp)->s=now->s+1;
}
  
void reset()
{
    memset(flag,0,sizeof(flag));
    n=qt,top=tot=cnt=0;
    dfs(1);
    tp=pool;
    repu(i,1,n)
    {
        root[i]=tp+1,insert(root[i-1],w[p[i]]);
        anc[i]=l[i];
    }
}
  
void query(node *x,node *y,int w)
{
    long long l=0,r=2147483647;
    while (l<r)
        if (w<=mid)
            ans+=y->rc->s-x->rc->s,x=x->lc,y=y->lc,r=mid;
        else
            x=x->rc,y=y->rc,l=mid+1;
}
  
void dfs_(int u)
{
    if (w[u]>x)
        ++ans;
    repe(u)
        dfs_(i->v);
}
  
int main()
{
    root[0]=tp,tp->lc=tp->rc=tp;
    scanf("%d",&n);
    repu(i,2,n)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v),addedge(v,u);
    }
    repu(i,1,n)
        scanf("%d",&w[i]);
    qt=n,reset();
    scanf("%d",&m);
    while (m--)
    {
        scanf("%d%d%d",&type,&u,&x);
        u^=ans,x^=ans;
        if (type)
        {
            if (++tot>3000)
                reset();
            if (type==1)
            {
                if (u<=n && !flag[u])
                    flag[u]=true,t[u]=w[u],stk[++top]=u;
                w[u]=x;
            }
            else
                addedge(u,++qt),anc[qt]=anc[u],w[qt]=x;
        }
        else
        {
            ans=0;
            if (u<=n)
            {
                query(root[l[u]-1],root[r[u]],x);
                repu(i,1,top)
                    if (l[u]<=l[stk[i]] && r[u]>=l[stk[i]])
                    {
                        if (t[stk[i]]>x)
                            --ans;
                        if (w[stk[i]]>x)
                            ++ans;
                    }
                repu(i,n+1,qt)
                    if (w[i]>x && l[u]<=anc[i] && r[u]>=anc[i])
                        ++ans;
            }
            else
                dfs_(u);
            printf("%d\n",ans);
        }
    }
    return 0;
}

Comments

comments powered by Disqus