[CTSC2013]没头脑和不高兴
zJx_Lm
·
·
题解
很好的期望题，很久之前学长讲的，但现在才填坑。
参考了 Autoint's Blog
首先转换一下题意，移动次数其实就是序列逆序对的数量。
所以我们实际上是在求序列逆序对数量的期望。
我们令 P_{i,j} 表示位置 (i,j) 上的数为逆序对的期望。
则：
Ans=\sum_{i=1}^{n}\sum_{j=i+1}^{n}P_{i,j}
考虑如何求 P{i,j} ，我们分情况讨论：
-
-
-
仅有 i 为排序点，期望为 \dfrac{V_{i}}{tot+1} 。
首先假设共有 m 个排序点,这种情况我们其实是在求从 n-m 的数中再取一个数比原数小的期望。
我们可以考虑直接选出 m+1 个点，再从 m+1 个点中选出未排序点、
所以期望为 \dfrac{V_{i}}{tot+1},其中 V_{i} 未 i 点的排名，tot 为总排序数。
-
仅有 j 为排序点，期望为 \frac{tot+1-V_{j}}{tot+1} 。
证明同上。
再分情况讨论,设 n' 为题中所给 n ：
若 n'=2n ：
Ans=\frac{1}{2}\binom{n}{2}+\frac{1}{n+1} \left ( \sum_{i=1}^{n}i(n-i+1)+\sum_{i=1}^{n-1}i(n-i) \right )=\frac{7n^2-n}{12}
若 n'=2n+1 ：
Ans=\frac{1}{2}\binom{n}{2}+\frac{1}{n+2} \left ( \sum_{i=1}^{n}i(n-i+1)+\sum_{i=1}^{n}i(n-i+1) \right )=\frac{7n^2+n}{12}
题目第二问要求方差的期望，即：
Var(I_{n})=\frac{\sum(x-E(I_{n}))^2}{tots}=\frac{\sum(x^2-2xE(I_{n})+E(I_{n})^2)}{tots}=E(I_{n}^2)-E({I_{n}})
可以用插值求出多项式系数。
最后：
若 $n'=2n$ ：
$$Var(I_n)=\frac{54n^3+13n^2+23n}{360}$$
若 $n'=2n+1$ ：
$$Var(I_n)=\frac{54n^3+55n^2-29n}{360}$$
------------
考虑怎么维护第一问。
若 $j$ 为未排序点，如果 $j$ 前面有 $k$ 个排序点，那对答案的贡献就为：
$$\dfrac{\sum_{i=1}^{k}i}{tot+1}=\frac{\binom{k}{2}+k}{tot+1}$$
设 1 为排序点，0 为未排序点，于是我们可以统计序列中 `110` 和 `10` 的个数来维护答案。
当 $i$ 为未排序点同理，统计序列中 `011` 和 `01` 的个数即可。
以上过程用线段树维护就可以了。
Code
```cpp
#include <bits/stdc++.h>
#define re register
#define int long long
// #define ll long long
// #define lls long long
#define pir make_pair
#define fr first
#define sc second
#define db double
using namespace std;
const int mol=998244353;
const int maxn=2e5+10;
const int INF=1e9+10;
inline int qpow(int a,int b) { int ans=1; while(b) { if(b&1) (ans*=a)%=mol; (a*=a)%=mol; b>>=1; } return ans; }
inline int read() {
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
int nn,n,m;
namespace STG {
#define lid (id<<1)
#define rid (id<<1|1)
struct TREE { int c1,c0,c01,c10,c011,c110,lazy; } tre[maxn<<2];
inline void update(int id) {
tre[id].c0=tre[lid].c0+tre[rid].c0;
tre[id].c1=tre[lid].c1+tre[rid].c1;
tre[id].c01=tre[lid].c01+tre[rid].c01+tre[lid].c0*tre[rid].c1;
tre[id].c10=tre[lid].c10+tre[rid].c10+tre[lid].c1*tre[rid].c0;
tre[id].c011=tre[lid].c011+tre[rid].c011+tre[lid].c01*tre[rid].c1+tre[lid].c0*tre[rid].c1*(tre[rid].c1-1)/2;
tre[id].c110=tre[lid].c110+tre[rid].c110+tre[lid].c1*tre[rid].c10+tre[rid].c0*tre[lid].c1*(tre[lid].c1-1)/2;
}
inline void build(int id,int l,int r) {
tre[id].lazy=-1;
if(l==r) { if(l&1) tre[id].c1=1; else tre[id].c0=1; return ; }
int mid=(l+r)>>1;
build(lid,l,mid); build(rid,mid+1,r);
update(id);
}
inline void push_down(int id,int l,int r) {
int v=tre[id].lazy; tre[id].lazy=-1;
int mid=(l+r)>>1;
if(v==1) {
tre[lid]=(TREE){ mid-l+1,0 }; tre[rid]=(TREE){ r-mid,0 };
}
else {
tre[lid]=(TREE){ 0,mid-l+1 }; tre[rid]=(TREE){ 0,r-mid };
}
tre[lid].lazy=tre[rid].lazy=v;
}
inline void ins(int id,int l,int r,int ll,int rr,int v) {
if(ll<=l&&r<=rr) { tre[id]=(v!=0)? (TREE){ r-l+1,0 }:(TREE){ 0,r-l+1 }; tre[id].lazy=v; return ; }
if(tre[id].lazy!=-1) push_down(id,l,r);
int mid=(l+r)>>1;
if(ll<=mid) ins(lid,l,mid,ll,rr,v);
if(rr>mid) ins(rid,mid+1,r,ll,rr,v);
update(id);
}
}
signed main(void) {
nn=n=read(); m=read();
if(nn&1) {
n/=2;
int a=7ll*n*n+n,b=12ll,gcd=__gcd(a,b);
printf("%lld/%lld\n",a/gcd,b/gcd);
a=54ll*n*n*n+55ll*n*n-29ll*n,b=360ll,gcd=__gcd(a,b);
printf("%lld/%lld\n",a/gcd,b/gcd);
} else {
n/=2;
int a=7ll*n*n-n,b=12ll,gcd=__gcd(a,b);
printf("%lld/%lld\n",a/gcd,b/gcd);
a=54ll*n*n*n+13ll*n*n+23ll*n,b=360ll,gcd=__gcd(a,b);
printf("%lld/%lld\n",a/gcd,b/gcd);
}
STG::build(1,1,nn);
for(re int i=1,l,r,v;i<=m;i++) {
l=read(); r=read(); v=read();
STG::ins(1,1,nn,l,r,v);
STG::TREE t=STG::tre[1];
int a1=t.c0*(t.c0-1),b1=4;
int a2=t.c01+t.c10+t.c011+t.c110,b2=t.c1+1;
a1=a1*b2+a2*b1,b1*=b2; int gcd=__gcd(a1,b1);
printf("%lld/%lld\n",a1/gcd,b1/gcd);
}
}
```