序列取反问题题解

想出一道期望题，就这样了。

综合题目条件，简化一下题意。
不妨将n对(x和ax)看做n个区间[x,ax]，根据题意，这n个区间只有包含和相离两种情况。
那么，一个点x被取反，当且仅当x被选或者包含x的区间被选。
单独计算每个点对答案的贡献，当一个点x自己被选，那么贡献为1，如果它没有被选，而是支配它的区间将它取反的话，贡献就是0.由于是等概率选取，假设支配x的区间有c个(包括[x,ax])，那么x的贡献就是1/c。

答案就是

问题变成了求c。
c的话，便有了一个非常简单的做法，需要知道每个点被多少区间覆盖，直接想到区间+1和区间查询。
线段树做法是O(nlogn)，但这样不够优美，可以在假设区间为[x,ax]，那么x处打个+1标记，ax+1处打-1标记，前缀和一下就得到c了，复杂度为O(n)，加上逆元还是nlogn的，线性求逆元又变回O(n)了。

我的做法，是把序列变成树，x子树根节点，ax为子树x的最后一个节点，可以发现，这可以对应一棵树，在树上求期望也是一样的，复杂度也是O(n)。

这里权当提供一个思路，树转序列，序列转树，都是很好的呢。

参考代码(这个代码是将序列变成树之后的做的)：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
int ne[200010*2],t[200010*2],he[200010],d[200010],tot=0,b[200010];
long long ans;
void link(int x,int y)
{
    tot++;
    ne[tot]=he[x];
    he[x]=tot;
    t[tot]=y;
}
long long ny(long long x,int y)
{
    long long ret=1;
    while (y)
    {
        if (y&1) ret=ret*x%998244353;
        x=x*x%998244353;
        y=y>>1;
    }
    return ret;
}
void dfs(int x,int y)
{
    ans=(ans+ny(y,998244353-2))%998244353;
    for (int i=he[x];i;i=ne[i]) dfs(t[i],y+1);
}
    int ret(int n, int* a, int aLen) {
        // write code here
    //freopen("1.in","r",stdin);
        for (int i=0;i<n;i++) b[i+1]=a[i]; 
    int len=1;
    d[1]=1;
    int p=1;
    if (n==1)
    {
        return 1;
    }
    while (1)          //用栈将序列还原成树
    {
        p++;
        len++;
        d[len]=p;
        link(d[len-1],p);
        while (p==b[d[len]]) len--;
        if (!len) break;
    }
    ans=0;
    dfs(1,1);
    return ans;

    }
};