自动搬运

查看原文

来自洛谷，原作者为

	zJx_Lm Zeit und Raum trennen dich und mich.

搬运于2025-08-24 22:15:14，当前版本为作者最后更新于2021-11-10 19:41:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

很好的期望题，很久之前学长讲的，但现在才填坑。

参考了 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,j)$ 均为排序点，期望为 0 。

• $(i,j)$ 均为未排序点，期望为 $\dfrac{1}{2}$ ， 即：$\dfrac{\sum_{i=1}^{n-1}i}{n(n-1)}=\dfrac{1}{2}$ 。

• 仅有 $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}}) $$

$tots$ 为总方案数。

可以用插值求出多项式系数。

最后：

若 $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

#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);
	}
}