题解 P6044 【「ACOI2020」惊吓路径】

zhengrunzhe · 2020-02-03 13:24:35 · 题解

毒瘤出题人卡时空

题意：给定一棵带点权树，求树中有多少对(u,v)满足v在u的子树中且orsum(path(u,v))>=k

首先orsum满足结合律和单调性，不妨考虑枚举每个v有多少个祖先满足条件，当某个祖先u满足orsum\geq k的时候，u的所有祖先也都满足orsum\geq k

考虑倍增从v跳到最深的满足orsum\geq k的祖先u，那么对答案产生的贡献就是dep[u](dep[root]=1)

预处理anc[i][j]表示i的2^j祖先，和orsum[i][j]表示i的父亲到i的2^j祖先路径点权或和，dfs一遍预处理出每个点的深度dep[i]

然后倍增就是基础操作了

#include<cstdio>
template<class type>inline const void read(type &in)
{
    in=0;char ch(getchar());
    while (ch<48||ch>57)ch=getchar();
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
typedef long long ll;
const int N(1e6+10),logn(20);
ll ans;
int orsum[N][logn+1],anc[N][logn+1],dep[N],n,k,head[N],edc,next[N],to[N],val[N];
inline const void addedge(const int &u,const int &v)
{
    next[++edc]=head[u];to[head[u]=edc]=v;
}
inline const void dfs(const int &p)
{
    for (int i(head[p]);i;i=next[i])dep[to[i]]=dep[p]+1,dfs(to[i]);
}
inline const void prework()
{
    for (int j(1);j<=logn;j++)
        for (int i(1);i<=n;i++)
            anc[i][j]=anc[anc[i][j-1]][j-1],
            orsum[i][j]=orsum[i][j-1]|orsum[anc[i][j-1]][j-1];
}
inline const int jump(int p)
{
    int sum(val[p]);
    if (sum>=k)return p;
    for (int i(logn);~i;i--)
        if (anc[p][i])
            if ((sum|orsum[p][i])<k)
                sum|=orsum[p][i],p=anc[p][i];
    return anc[p][0];
}
int main()
{
    read(n);read(k);
    for (int i(1);i<=n;i++)read(val[i]);
    for (int u,v,i(1);i<n;i++)read(u),read(v),addedge(u,v),orsum[v][0]=val[anc[v][0]=u];
    for (int i(1);i<=n;i++)if (!anc[i][0]){dep[i]=1;dfs(i);break;}prework();
    for (int i(1);i<=n;i++)ans+=dep[jump(i)];
    printf("%lld\n",ans);
    return 0;
}

然后交一发mle70分，发现subtask4给了256mb可以过，subtask2都是一百万的链只给128mb就被卡了

然后此时来思考一下链怎么做

这个链非常友好，是形如1\rightarrow 2\rightarrow 3\rightarrow \cdots \rightarrow n的链，考虑链转序列，编号几就是第几个数

同样的思路我们可以对每个i找到编号j\leq i且orsum[j,i]\leq k的最小j，不能再倍增了一开10^6*20的数组直接mle

考虑把倍增换成二分，只要我们能够获取区间orsum就能实现

由于orsum没有可减性，我们不能够通过前缀和的方式O(1)获取

一种简单的方法通过线段树维护O(\log n)获取

然后外面套个二分合起来就是O(n\log^2 n)的

考虑能不能在线段树上二分，显然是可以做的，但是不太好理解，我就写了个Splay上二分

#include<cstdio>
template<class type>inline const void read(type &in)
{
    in=0;char ch(getchar());
    while (ch<48||ch>57)ch=getchar();
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
typedef long long ll;
const int N(1e6+1),logn(19);
ll ans;
int orsum[N][logn+1],anc[N][logn+1],dep[N],n,k,head[N],edc,next[N],to[N],val[N],u[N],v[N];
inline const void addedge(const int &u,const int &v)
{
    next[++edc]=head[u];to[head[u]=edc]=v;
}
inline const void dfs(const int &p)
{
    for (int i(head[p]);i;i=next[i])dep[to[i]]=dep[p]+1,dfs(to[i]);
}
inline const void prework()
{
    for (int j(1);j<=logn;j++)
        for (int i(1);i<=n;i++)
            anc[i][j]=anc[anc[i][j-1]][j-1],
            orsum[i][j]=orsum[i][j-1]|orsum[anc[i][j-1]][j-1];
}
inline const int jump(int p)
{
    int sum(val[p]);
    if (sum>=k)return p;
    for (int i(logn);~i;i--)
        if (anc[p][i])
            if ((sum|orsum[p][i])<k)
                sum|=orsum[p][i],p=anc[p][i];
    return anc[p][0];
}
namespace Splay
{
    struct tree
    {
        int orsum,val;
        tree *son[2],*fa;
        static tree *null;
        void *operator new[](size_t size);
        inline tree():orsum(0),val(0)
        {
            static bool init(0);
            if (!init)
                init=1,
                null=new tree,
                null->son[0]=null->son[1]=null->fa=null;
            son[0]=son[1]=fa=null;
        }
        inline const void pushup()
        {
            orsum=son[0]->orsum|val|son[1]->orsum;
        }
        inline const void set(tree *p,const bool &f)
        {
            if (p!=null)p->fa=this;
            if (this!=null)son[f]=p;
        }
        inline const bool id()
        {
            return fa->son[1]==this;
        }
        inline const void rotate()
        {
            const bool f(id());
            tree *fa(this->fa);
            fa->fa->set(this,fa->id());
            fa->set(son[f^1],f);
            set(fa,f^1);
            fa->pushup();pushup();
        }
        inline const void splay()
        {
            for (;fa!=null;rotate())
                if (fa->fa!=null)
                    (fa->id()^id()?this:fa)->rotate();
        }
    }*node0,*tree::null;
    #define null tree::null
    inline tree *node(const int &x){return node0+x;}
    char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof memory_pool);
    inline void *tree::operator new[](size_t size){return tail-=size;}
    inline tree *build(const int &l,const int &r,tree *fa)
    {
        if (l>r)return null;
        const int mid(l+r>>1);
        node(mid)->val=val[mid];node(mid)->fa=fa;
        if (l==r)return node(l)->orsum=node(l)->val,node(l);
        node(mid)->son[0]=build(l,mid-1,node(mid));
        node(mid)->son[1]=build(mid+1,r,node(mid));
        node(mid)->pushup();
        return node(mid);
    }
    inline const int query(const int &pos)
    {
        tree *p(node(pos));
        p->splay();
        if (p->val>=k)return pos;
        int sum(p->val);p=p->son[0];
        while (p!=null)
            if ((sum|p->son[1]->orsum)>=k)p=p->son[1];
            else if ((sum|p->son[1]->orsum|p->val)>=k)return p-node0;
                else sum|=p->son[1]->orsum|p->val,p=p->son[0];
        return 0;
    }
}using namespace Splay;
int main()
{
    read(n);read(k);
    for (int i(1);i<=n;i++)read(val[i]);
    bool type(1);
    for (int i(1);i<n;i++)read(u[i]),read(v[i]),type=type&&v[i]==u[i]+1;
    if (type)
    {
        node0=new tree[n+1];
        build(1,n,null);
        for (int i(1);i<=n;i++)ans+=query(i);
        printf("%lld\n",ans);
        return 0;
    }
    for (int i(1);i<n;i++)addedge(u[i],v[i]),orsum[v[i]][0]=val[anc[v[i]][0]=u[i]];
    for (int i(1);i<=n;i++)if (!anc[i][0]){dep[i]=1;dfs(i);break;}prework();
    for (int i(1);i<=n;i++)ans+=dep[jump(i)];
    printf("%lld\n",ans);
    return 0;
}

能往右儿子走就往右儿子走，否则看看自己满不满足条件，满足就是自己，否则往左儿子走，记一个排名在当前节点之后的点权或和，往左儿子走的时候就把右子树或和与当前点权的或和累计起来

然后我一开始是这样先把树建好然后把每个点都splay到根，先判断根自己是不是满足条件，否则在其左子树上执行上述二分过程

然后这个玩意tle了四个点，因为建树完之后每次查询树中的点数都是n的，这个常数就大了

因为每次查询之和其前面的数有关，我们不妨一个个插入一个个查

考虑现在原来的平衡树上查，把前一个点splay执行二分，查完之后把这个点插入到根的右儿子上

这样子做的复杂度实际上是错的，这样子出来的树形态是一条链，那就完蛋了

需要多splay几个点维持平衡结构

inline const void query(const int &pos)
{
    if (pos==1)return ans+=val[pos]>=k,void();
    tree *p(node(pos-1));p->splay();
    p->set(node(pos),1);p->orsum|=val[pos];
    int sum(0);
    while (p!=null)
        if ((sum|p->son[1]->orsum)>=k)p=p->son[1];
        else if ((sum|=(p->son[1]->orsum|p->val))>=k)break;
            else p=p->son[0];
    if (p!=null)ans+=p-node0;
    p->splay();
}

接着我写了个这个玩意，把二分到的答案点splay到根，由于答案点十分的随机，所以整个树也许比较随机平衡，然而它还是t了一个点

到最后我实在是懒得想了，直接随机找一个点splay:

#include<cstdio>
#include<cstdlib>
template<class type>inline const void read(type &in)
{
    in=0;char ch(getchar());
    while (ch<48||ch>57)ch=getchar();
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
typedef long long ll;
const int N(1e6+1),logn(19);
ll ans;
int orsum[N][logn+1],anc[N][logn+1],dep[N],n,k,head[N],edc,next[N],to[N],val[N],u[N],v[N];
inline const void addedge(const int &u,const int &v)
{
    next[++edc]=head[u];to[head[u]=edc]=v;
}
inline const void dfs(const int &p)
{
    for (int i(head[p]);i;i=next[i])dep[to[i]]=dep[p]+1,dfs(to[i]);
}
inline const void prework()
{
    for (int j(1);j<=logn;j++)
        for (int i(1);i<=n;i++)
            anc[i][j]=anc[anc[i][j-1]][j-1],
            orsum[i][j]=orsum[i][j-1]|orsum[anc[i][j-1]][j-1];
}
inline const int jump(int p)
{
    int sum(val[p]);
    if (sum>=k)return p;
    for (int i(logn);~i;i--)
        if (anc[p][i])
            if ((sum|orsum[p][i])<k)
                sum|=orsum[p][i],p=anc[p][i];
    return anc[p][0];
}
namespace Splay
{
    struct tree
    {
        int orsum,val;
        tree *son[2],*fa;
        static tree *null;
        void *operator new[](size_t size);
        inline tree():orsum(0),val(0)
        {
            static bool init(0);
            if (!init)
                init=1,
                null=new tree,
                null->son[0]=null->son[1]=null->fa=null;
            son[0]=son[1]=fa=null;
        }
        inline const void pushup()
        {
            orsum=son[0]->orsum|val|son[1]->orsum;
        }
        inline const void set(tree *p,const bool &f)
        {
            if (p!=null)p->fa=this;if (this!=null)son[f]=p;
        }
        inline const bool id()
        {
            return fa->son[1]==this;
        }
        inline const void rotate()
        {
            const bool f(id());
            tree *fa(this->fa);
            fa->fa->set(this,fa->id());
            fa->set(son[f^1],f);
            set(fa,f^1);
            fa->pushup();pushup();
        }
        inline const void splay()
        {
            for (;fa!=null;rotate())
                if (fa->fa!=null)
                    (fa->id()^id()?this:fa)->rotate();
        }
    }*node0,*tree::null;
    #define null tree::null
    inline tree *node(const int &x){return node0+x;}
    char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof memory_pool);
    inline void *tree::operator new[](size_t size){return tail-=size;}
    inline const void query(const int &pos)
    {
        if (pos==1)return ans+=val[pos]>=k,void();
        tree *p(node(pos-1));p->splay();
        p->set(node(pos),1);p->orsum|=val[pos];
        if (val[pos]>=k)return ans+=pos,void();
        if ((val[pos]|val[pos-1])>=k)return ans+=pos-1,void();
        int sum(0);
        while (p!=null)
            if ((sum|p->son[1]->orsum)>=k)p=p->son[1];
            else if ((sum|=(p->son[1]->orsum|p->val))>=k)break;
                else p=p->son[0];
        if (p!=null)ans+=p-node0;
        node(rand()%pos+1)->splay(); //鬼才操作
    }
}using namespace Splay;
int main()
{
    srand(19260817);
    read(n);read(k);
    for (int i(1);i<=n;i++)read(val[i]);
    bool type(1);
    for (int i(1);i<n;i++)read(u[i]),read(v[i]),type=type&&v[i]==u[i]+1;
    if (type)
    {
        node0=new tree[n+1];
        for (int i(1);i<=n;i++)node(i)->val=node(i)->orsum=val[i];
        for (int i(1);i<=n;i++)query(i);
        printf("%lld\n",ans);
        return 0;
    }
    for (int i(1);i<n;i++)addedge(u[i],v[i]),orsum[v[i]][0]=val[anc[v[i]][0]=u[i]];
    for (int i(1);i<=n;i++)if (!anc[i][0]){dep[i]=1;dfs(i);break;}prework();
    for (int i(1);i<=n;i++)ans+=dep[jump(i)];
    printf("%lld\n",ans);
    return 0;
}

然后这个玩意它居然A了，全 体 起 立