Codeforces 895E Eyes Closed（线段树）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接 Eyes Closed

题意两个人玩一个游戏，现在有两种操作：

1、两个人格子挑选一个区间，保证两个的区间不相交。在这两个区间里面各选出一个数，交换这两个数。

2、挑选一个区间，求这个区间的和的期望。

对于第一种操作，先求出两个区间的长度$len1$和$len2$，再求出两个区间的期望和$s1$和$s2$。

对于第一个区间，我们先把这个区间里的所有数（期望值）乘上$(len1 - 1)/(len1)$，再加上$s2/len1/len2$

对于第二个区间，我们先把这个区间里的所有数（期望值）乘上$(len2 - 1)/(len2)$，再加上$s1/len1/len2$

线段树维护这两个操作即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	ls		(i << 1)

#define	rs		(i << 1 | 1)

#define	mid		((L + R) >> 1)

#define	lson		i << 1, L, mid

#define	rson		i << 1 | 1, mid + 1, R

typedef long long LL;

const int N = 4e5 + 10;

double add[N], mul[N], s[N];

int n, q;

void pushup(int i){ s[i] = s[ls] + s[rs]; }

void pushdown(int i, int L, int R){

	s[ls] = mul[i] * s[ls] + add[i] * (mid - L + 1);

	mul[ls] *= mul[i];

	add[ls] = mul[i] * add[ls] + add[i];

       	s[rs] = mul[i] * s[rs] + add[i] * (R - mid);

	mul[rs] *= mul[i];

	add[rs] = mul[i] * add[rs] + add[i];

	add[i] = 0;

	mul[i] = 1.0;

}	

void build(int i, int L, int R){

	add[i] = 0, mul[i] = 1;

	s[i] = 0;

	if (L == R){ scanf("%lf", s + i); return; }

	build(lson);

	build(rson);

	pushup(i);

}

void add_update(int i, int L, int R, int l, int r, double val){

	if (l <= L && R <= r){

		s[i] += (R - L + 1) * val;

		add[i] += val;

		return;

	}

	pushdown(i, L, R);

	if (l <= mid) add_update(lson, l, r, val);

	if (r  > mid) add_update(rson, l, r, val);

	pushup(i);

}

void mul_update(int i, int L, int R, int l, int r, double val){

	if (l <= L && R <= r){

		s[i] *= val;

		mul[i] *= val;

		add[i] *= val;

		return;

	}

	pushdown(i, L, R);

	if (l <= mid) mul_update(lson, l, r, val);

	if (r  > mid) mul_update(rson, l, r, val);

	pushup(i);

}

double query(int i, int L, int R, int l, int r){

	if (l <= L && R <= r) return s[i];

	double ret = 0;

	pushdown(i, L, R);

       	if (l <= mid) ret += query(lson, l, r);

	if (r  > mid) ret += query(rson, l, r);

	pushup(i);

	return ret;

}	

int main(){

	scanf("%d%d", &n, &q);

	build(1, 1, n);

	while (q--){

		int op;

		scanf("%d", &op);

		if (op == 1){

			int l1, r1, l2, r2;

			scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

			double s1 = query(1, 1, n, l1, r1);

			double s2 = query(1, 1, n, l2, r2);

			double len1 = r1 - l1 + 1;

			double len2 = r2 - l2 + 1;

			mul_update(1, 1, n, l1, r1, 1.0 * (len1 - 1) / len1);

			mul_update(1, 1, n, l2, r2, 1.0 * (len2 - 1) / len2);

			add_update(1, 1, n, l1, r1, 1.0 / len1 / len2 * s2);

			add_update(1, 1, n, l2, r2, 1.0 / len1 / len2 * s1);

		}

		else{

			int l, r;

			scanf("%d%d", &l, &r);

			printf("%.12f\n", query(1, 1, n, l, r));

		}

	}

	return 0;

}