Omeed 线段树

题面
题解
代码

题面

2.12 - - -

题解

大概还是挺妙的？

首先基础分和连击分互不干扰，所以可以分开统计。

基础分的统计比较简单，等于：

\[A \sum_{i = l}^{r} p_i
\]

连击分的统计就比较复杂了，因为是求期望，根据期望的线性性，我们可以先算出\(f_i\)表示每个音符的期望连击分，再计算整个区间的期望连击分。

观察连击分的统计方法，可以知道，区间其实是互不干扰的，也就是说，每个区间中的期望连击分，其实都是在对进入这个区间时的期望连击分\(f_{l - 1}\)的一个叠加和增幅。

考虑区间的期望连击分可以表示为：

\[B \sum_{i = l}^r p_i (f_{i - 1} + 1)
\]

因为只有这次打到了完美才可以计入这个音符的贡献，所以这次的贡献是建立在当前音符完美的情况下的，所以贡献就是\(p_i(f_{i - 1} + 1)\)了。

考虑\(f_i\)如何转移。

\[f_i = p_i(f_{i - 1} + 1) + (1 - p_i)f_{i - 1}t
\]

\[= (p_i + t(1 - p_i))f_{i - 1} + p_i
\]

观察到这是一个类似于\(kx + b\)的形式，因此对于一个\(f_i\)，如果一个\(j\)满足\(j \le i\),那么一定可以表示为\(f_i = kf_j + b\)的形式。

那么对于区间\([l, r]\),因为其中每个\(f_i\),都可以表示为类似\(kf_{l - 1} + b\)的形式，因此，这个区间的连击分也一定可以表示为\(kf_{l - 1} + b\)的形式。

因此我们考虑线段树，对于区间\([l, r]\)我们维护5个变量，\(k, b, sumb, sumk, sump\),其中\(sump\)是用来算基础分的，\(sumb, sumk\)就是区间连击分的系数，\(k, b\)则是\(f_r = kf_{l - 1} + b\)中的\(k\)和\(b\).

因为\(B\)是对于整个区间的系数，因此我们可以先不考虑它，直接统计后面的部分，最后再乘上\(B\)即可。

因此我们考虑如何合并2个区间\([l, mid], [mid + 1, r]\).

根据前面的推导，现在有

\[f_{mid} = k_l f_{l - 1} + b_l, \quad f_{r} = k_r f_{mid} + b_r
\]

现在要合并这2个变量，我们只需要把后者表示为\(kf_{l - 1} + b\)的形式即可。

所以直接把\(f_{mid}\)带入后面的等式化简就行了，化简出来新变量的\(k = k_l k_r, \quad b = k_rb_l + b_r\)

然后来考虑合并区间信息：

现在我们有：

\[sumk_l f_{l - 1} + sumb_l
\]

\[sumk_r f_{mid} + sumb_r
\]

我们现在要得到的新区间应该要形如第一个区间的样子，因为第一个区间已经是这样了，所以我们只需要转化一下第二个区间，然后和第一个区间加在一起就行了。

我们直接带入上面的\(f_{mid} = k_l f_{l - 1} + b_l\)，然后化简并和第一个区间的式子加在一起，最后得到新的\(sumk = sumk_r k_l + sumk_l, \quad sumb = sumk_r b_l + sumb_r + sumb_l\)

最后

\[ans[l][r] = B \cdot sumb[l][r] + A \cdot sump[l][r]
\]

代码

#include<bits/stdc++.h>

using namespace std;

#define R register int

#define LL long long

#define AC 501000

#define ac 2001000

#define p 998244353

#define mo(x) ((x) % p)

#define mul(a, b) (1LL * (a) * (b) % p)//error !!!都要用(a), (b)...啊

#define h(x, y) (mul((x), qpow((y), p - 2)))

int n, m, t, A, B;

int pi[AC];

struct node{

	int sumk, sumb, k, b, sump;

}tree[ac];

inline int read()

{

	int x = 0;char c = getchar();

	while(c > '9' || c < '0') c = getchar();

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x;

}

inline void up(int &a, int b) {a += b; if(a < 0) a += p; if(a >= p) a -= p;}

inline int ad(int a, int b) {a += b; if(a < 0) a += p; if(a >= p) a -= p; return a;}

inline int qpow(int x, int have)

{

	int rnt = 1;

	while(have)

	{

		if(have & 1) rnt = mul(rnt, x);

		x = mul(x, x), have >>= 1;

	}

	return rnt;

}

void pre()

{

	n = read();//对于正解来说没有什么用的输入

	n = read(), m = read();

	int a = read(), b = read();

	t = h(a, b), A = read(), B = read();

	for(R i = 1; i <= n; i ++) a = read(), b = read(), pi[i] = h(a, b);

}

node merge(node ll, node rr)

{

	node x;

	x.k = mul(ll.k, rr.k), x.b = ad(mul(rr.k, ll.b), rr.b);

	x.sumk = ad(mul(rr.sumk, ll.k), ll.sumk);

	x.sumb = ad(mul(rr.sumk, ll.b), ad(rr.sumb, ll.sumb));

	x.sump = ad(ll.sump, rr.sump);

	return x;

}

#define update(x) tree[x] = merge(tree[x << 1], tree[(x << 1) + 1]);

node make(int now)

{

	node x;

	x.k = ad(pi[now], mul(t, 1 - pi[now]));

	x.b = x.sumk = x.sumb = x.sump = pi[now];

	return x;

}

void build(int x, int ll, int rr)

{

	if(ll == rr) {tree[x] = make(ll); return ;}

	int mid = (ll + rr) >> 1;

	build(x << 1, ll, mid), build((x << 1) + 1, mid + 1, rr);

	update(x);

}

void change(int x, int l, int r, int w)

{

	if(l == r) {tree[x] = make(w); return ;}

	int mid = (l + r) >> 1;

	if(w <= mid) change(x << 1, l, mid, w);

	else change((x << 1) + 1, mid + 1, r, w);

	update(x);

}

node find(int x, int l, int r, int ll, int rr)

{

	if(l == ll && r == rr) return tree[x];

	int mid = (l + r) >> 1;

	if(rr <= mid) return find(x << 1, l, mid, ll, rr);

	else if(ll > mid) return find((x << 1) + 1, mid + 1, r, ll, rr);

	else

	{

		node a = find(x << 1, l, mid, ll, mid);

		node b = find((x << 1) + 1, mid + 1, r, mid + 1, rr);

		return merge(a, b);

	}

}

void work()

{

	for(R i = 1; i <= m; i ++)

	{

		int o = read();

		if(!o)

		{

			int x = read(), a = read(), b = read();

			pi[x] = h(a, b), change(1, 1, n, x);

		}

		else

		{

			int ll = read(), rr = read();

			node x = find(1, 1, n, ll, rr);

			//int ans = mul(ad(mul(x.sumk, pi[ll]), ad(x.sumb, pi[ll])), B);

			int ans = mul(x.sumb, B);

			up(ans, mul(A, x.sump));

			printf("%d\n", ans);

		}

	}

}

int main()

{

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

	pre();

	build(1, 1, n);

	work();

	fclose(stdin);

	return 0;

}

巴特西

Omeed 线段树

题面

题解

代码

最新文章

热门文章