今天做了一下这题感受了一下……果然强数学……

以下题解均取自AYQ大神的解题报告

题目大意:
对于[1,n]的每个数的一个随机排列,我们将奇数位上的所有数排好序,之后求这个序列的期望逆序对数,以及逆序对个数的方差。
之后我们有m个操作,每次会将一段位置设置为排好序或者不排序,每次操作后求逆序对的期望。
不妨设E表示整个序列逆序对的期望。

其中P[i,j]表示(i,j)是一对逆序对的概率。
那么我们考虑P[i,j]的取值。我们用C[i]表示第i个位置是否被排序,用num表示被排序的位置总数,表示这个元素在所有被排序元素中的排名(靠左的第i个位置)。

前面两种情况很好理解,这里只介绍第三种情况(第四种与第三种相仿)
此时我们考虑的是这样一个问题:我们从n个元素中随机抽出num个排序,再从剩下的元素中随机抽取一个元素,求它比排序的第k个元素小的概率。
那么我们可以这么考虑:一开始就随机取num+1个元素,排序后求某一个元素在前k个的概率。
那么显然就是
为了维护修改操作,我们需要快速计算出这个式子。
显然,前两种情况非常好维护,只需要知道整个序列内未被排序的元素个数就可以计算。
那么我们还是只考虑第三种情况。不妨设01序列A,0表示这个位置没有被排序,1表示这个位置被排序了。
对于第三种情况,考虑一个固定的j的影响。

其中k表示j左侧有多少个1。
注意到对每个j,其分母都相同。那么我们只需要考虑求
那么我们用线段树维护。根据子区间的,以及1和0的数量,可以计算出当前区间的。具体请多想想……
第四种情况同理,只是方向相反。使用同样的方法即可维护。
在考虑方差之前,我们先继续考虑初始情况的期望。
对于奇数位被排序的情况,我们可以直接把上面的式子化简。过程在这里略过。
设m=
那么我们容易得到:

我们发现这个东西是一个多项式,那么我们猜想其方差也是一个多项式。但是方差肯定不能推导了(情况太多了)。
我们还有一些求解多项式的方法……比如拉格朗日插值……
经过实验得到:

不要问我这个从哪来的……是从题解里抄来的……
于是这个题目就解决了……
下面贴代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    long long lk,rk,lk2,rk2,s[2];
    int mark;
    node(){mark=-1;}
}a[500001];
int n,m;long long A,TMP,T;
long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}
void update(int num)
{
    node*f=&a[num],*x=&a[num<<1],*y=&a[num<<1^1];
    f->s[0]=x->s[0]+y->s[0];
    f->s[1]=x->s[1]+y->s[1];
    f->lk=x->lk+y->lk+x->s[1]*y->s[0];
    f->lk2=x->lk2+y->lk2+y->s[0]*x->s[1]*x->s[1]+2*x->s[1]*y->lk;
    f->rk=x->rk+y->rk+x->s[0]*y->s[1];
    f->rk2=x->rk2+y->rk2+x->s[0]*y->s[1]*y->s[1]+2*y->s[1]*x->rk;
}
void build(int num,int l,int r)
{
    if(l==r){if(l&1)a[num].s[1]=1;else a[num].s[0]=1;return ;}
    build(num<<1,l,l+r>>1);
    build(num<<1^1,(l+r>>1)+1,r);
    update(num);
}
void getans()
{
    long long up=a[1].lk+a[1].rk+a[1].lk2+a[1].rk2;
    long long down=2*(a[1].s[1]+1);
    up+=a[1].s[0]*(a[1].s[0]-1)/2*(a[1].s[1]+1);
    long long g=gcd(up,down);
    printf("%lld/%lld\n",up/g,down/g);
}
void setmark(int num,int len,int v)
{
    a[num].mark=v;
    a[num].s[v]=len;a[num].s[v^1]=0;
    a[num].lk=a[num].rk=a[num].lk2=a[num].rk2=0;
}
void pushdown(int num,int l,int r)
{
    if(a[num].mark==-1)return ;
    setmark(num<<1,(l+r>>1)-l+1,a[num].mark);
    setmark(num<<1^1,r-(l+r>>1),a[num].mark);
    a[num].mark=-1;
}
void modify(int num,int l,int r,int left,int right,int v)
{
    if(l>right||r<left)return ;
    if(l>=left&&r<=right){setmark(num,r-l+1,v);return ;}
    pushdown(num,l,r);
    modify(num<<1,l,l+r>>1,left,right,v);
    modify(num<<1^1,(l+r>>1)+1,r,left,right,v);
    update(num);
}
int main()
{
    scanf("%d%d",&n,&m);build(1,1,n);getans();
    TMP=n>>1;
    if(n&1)
        A=TMP*TMP*TMP*54+TMP*TMP*55-TMP*29;
    else 
        A=TMP*TMP*TMP*54+TMP*TMP*13+TMP*23;
    T=gcd(A,360);
    printf("%lld/%lld\n",A/T,360/T);
    while(m--)
    {    int l,r,v;
        scanf("%d%d%d",&l,&r,&v);
        modify(1,1,n,l,r,v);
        getans();
    }
    return 0;
}

Comments

comments powered by Disqus