NOIp模拟赛西行妖下

题目描述：

给出一棵n个节点的树，每个点初始m值为1。

你有三种操作：

1.Add l r k ，将l到r路径上所有点m值加k。

2.Multi l r k ，将l到r路径上所有点m值乘k。

3.Query l r ，设x是l到r路径上的点，y是x的m值。假设有1~y共y个点，随机打乱，求形成错排的概率。

（k<=1000,n<=80000）

题解：

树剖正解？

（反正我用的dfs序+并查集）

首先1000^80000错排怎么搞啊？

要明白我们真正要的并不是错排数，而是错排数/阶乘。

打表后发现他是：

0.0,0.5,0.333333333,0.375,0.366666667,0.368055556,0.367857143,0.367881944,0.367879464

最后一位用的一般值。

（后来发现这个精度依然不够，要用错排递推直接打表。不然会卡精。）

树链怎么修改啊？

其实可以用单点修改……

重点在于一共只有80000个点，如果m值超过15就不用处理了，保留15位就够了……

所以单点最多修改80000*15次……

并查集维护。

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

//lgl AK in NOIp

#define N 80050

double num[],tmp[];

void init()

{

    double now = ;

    tmp[]=0.0,tmp[]=1.0;

    num[]=0.5;

    for(int i=;i<;i++)

    {

        now*=(double)i;

        tmp[i]=(double)(i-)*(tmp[i-]+tmp[i-]);

        num[i]=(double)tmp[i]/now;

    }

}

int n,hed[N],cnt,q;

char ch[];

struct EG

{

    int to,nxt;

}e[*N];

void ae(int ff,int t)

{

    e[++cnt].to = t;

    e[cnt].nxt = hed[ff];

    hed[ff] = cnt;

}

struct aaafku

{

    int s[*N];

    void ins(int x,int d)

    {

        while(x<*N)

        {

            s[x]+=d;

            x+=(x&(-x));

        }

    }

    int qry(int x)

    {

        int ret = ;

        while(x)

        {

            ret+=s[x];

            x-=(x&(-x));

        }

        return ret;

    }

}f[];

int las[N];

int dep[N],siz[N],fa[N],son[N],top[N],typ[N];

int tin[N],tout[N],tim;

void dfs1(int u,int ff)

{

    tin[u]=++tim;

    typ[u]=;

    siz[u]=;

    dep[u]=dep[ff]+;

    las[u]=u;

    f[].ins(tin[u],);

    for(int j=hed[u];j;j=e[j].nxt)

    {

        int to = e[j].to;

        if(to==ff)continue;

        fa[to]=u;

        dfs1(to,u);

        siz[u]+=siz[to];

        if(siz[to]>siz[son[u]])son[u]=to;

    }

    tout[u]=tim;

    f[].ins(tout[u]+,-);

}

void dfs2(int u,int tp)

{

    top[u] = tp;

    if(!son[u])return ;

    dfs2(son[u],tp);

    for(int j=hed[u];j;j=e[j].nxt)

    {

        int to = e[j].to;

        if(to!=fa[u]&&to!=son[u])

            dfs2(to,to);

    }

}

int get_lca(int x,int y)

{

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]])swap(x,y);

        x=fa[top[x]];

    }

    return dep[x]<dep[y]?x:y;

}

int get_las(int x)

{

    if(las[x]==x)return x;

    return las[x]=get_las(las[x]);

}

void deala(int u,int k,int lim)

{

    if(dep[u]<=lim)return ;

    f[typ[u]].ins(tin[u],-);

    f[typ[u]].ins(tout[u]+,);

    typ[u] = min(,typ[u]+k);

    f[typ[u]].ins(tin[u],);

    f[typ[u]].ins(tout[u]+,-);

    deala(get_las(fa[u]),k,lim);

    if(typ[u]==)las[u]=fa[u];

}

void dealb(int u,int k,int lim)

{

    if(dep[u]<=lim)return ;

    f[typ[u]].ins(tin[u],-);

    f[typ[u]].ins(tout[u]+,);

    typ[u] = min(,typ[u]*k);

    f[typ[u]].ins(tin[u],);

    f[typ[u]].ins(tout[u]+,-);

    dealb(get_las(fa[u]),k,lim);

    if(typ[u]==)las[u]=fa[u];

}

int main()

{

//    freopen("yuyuko.in","r",stdin);

//    freopen("yuyuko.out","w",stdout);

    init();

    scanf("%d",&n);

    for(int ff,t,i=;i<n;i++)

    {

        scanf("%d%d",&ff,&t);

        ae(ff,t),ae(t,ff);

    }

    dfs1(,),dfs2(,);

    scanf("%d",&q);

    for(int l,r,k,i=;i<=q;i++)

    {

        scanf("%s",ch+);

        if(ch[]=='Q')

        {

            scanf("%d%d",&l,&r);

            int lca = get_lca(l,r);

            int ff = fa[lca];

            double ans = 0.0;

            for(int j=;j<;j++)

            {

                int sum = f[j].qry(tin[l])+f[j].qry(tin[r])-f[j].qry(tin[lca])-f[j].qry(tin[ff]);

                ans+=(double)sum*num[j];

            }

            printf("%.1lf\n",ans);

        }else

        {

            scanf("%d%d%d",&l,&r,&k);

            int lca = get_lca(l,r);

            if(ch[]=='A')

            {

                deala(las[l],k,dep[lca]);

                deala(las[r],k,dep[lca]-);

            }else

            {

                dealb(las[l],k,dep[lca]);

                dealb(las[r],k,dep[lca]-);

            }

        }

    }

    return ;

}

巴特西

NOIp模拟赛西行妖下

最新文章

热门文章

巴特西

NOIp模拟赛 西行妖下

最新文章

热门文章

NOIp模拟赛西行妖下