Description：

一排 $n$ 个电阻，每次可以给一个区间的电阻并联或串联一个给定阻值的电阻，询问区间阻值最大最小值。

$1\leqslant n\leqslant 250000$

Solution：

首先一个重要的性质是原来作为区间最大阻值的在并联或串联后还是区间最大阻值，因此可以用线段树维护，直接在 $\min$ 和 $\max$ 上打标记，现在最大的问题是怎么打标记，串联相当于 $R+R'$ ，并联相当于 $\frac{RR'}{R+R'}$ ，因此可以维护一个四元组 $(k_1,b_1,k_2,b_2)$ 标记，相当于是维护了一个函数 $\frac{k_1x+b_1}{k_2x+b_2}$ ，这样合并标记就相当于是做一个一次函数复合，但是要注意函数复合是有先后顺序的，也就是说 $f(g(x))\ne g(f(x))$ ，这时并联相当于 $\frac{R'x+0}{x+R'}$ ，串联相当于 $\frac{x+R'}{0x+1}$ ，另外一个需要注意的是由于会爆精度所以复合的时候要用一些奇怪的方法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 250010

double w[MAXN];

struct tag

{

	double k1,b1,k2,b2;

	tag(double k1_ = 1,double b1_ = 0,double k2_ = 0,double b2_ = 1)

	{

		k1 = k1_;b1 = b1_;k2 = k2_;b2 = b2_;

	}

	void init()

	{

		k1 = 1;b1 = 0;k2 = 0;b2 = 1;

		return;

	}

	friend tag operator + (tag x,tag y)

	{

		tag k;

		k.k1 = (x.k1 * y.k1 + x.b1 * y.k2);

		k.b1 = (x.k1 * y.b1 + x.b1 * y.b2);

		k.k2 = (x.k2 * y.k1 + x.b2 * y.k2);

		k.b2 = (x.k2 * y.b1 + x.b2 * y.b2);

		k.b1 /= k.k1;k.k2 /= k.k1;k.b2 /= k.k1;

		k.k1 = 1.0;

		return k;

	}

	double f(double x)

	{

		return (x * k1 + b1) / (x * k2 + b2);

	}

};

struct state

{

	double minv,maxv;

	state(){minv = 1000000000;maxv = -1000000000;}

	friend state operator + (state a,state b)

	{

		state res;

		res.minv = min(a.minv,b.minv);

		res.maxv = max(a.maxv,b.maxv);

		return res;

	}

	void set(double k)

	{

		minv = maxv = k;

	}

};

struct node

{

	int lc,rc;

	tag v;

	state val;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].val.set((double)w[l]);

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].val = t[t[rt].lc].val + t[t[rt].rc].val;

	return;

}

void addtag(int rt,tag k)

{

	t[rt].val.minv = k.f(t[rt].val.minv);

	t[rt].val.maxv = k.f(t[rt].val.maxv);

	t[rt].v = k + t[rt].v;

	return;

}

void pushdown(int rt)

{

	addtag(t[rt].lc,t[rt].v);

	addtag(t[rt].rc,t[rt].v);

	t[rt].v.init();

	return;

}

tag bing(double r){return (tag){r,0,1,r};}

tag chuan(double r){return (tag){1,r,0,1};}

void change(int rt,int L,int R,tag k,int l,int r)

{

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

	{

		addtag(rt,k);

		return;

	}

	pushdown(rt);

	if(L <= mid)change(t[rt].lc,L,R,k,l,mid);

	if(R > mid)change(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].val = t[t[rt].lc].val + t[t[rt].rc].val;

	return;

}

state query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].val;

	state res;

	pushdown(rt);

	if(L <= mid)res = res + query(t[rt].lc,L,R,l,mid);

	if(R > mid)res = res + query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int main()

{

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

	freopen("b.out","w",stdout);

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lf",&w[i]);

	build(root,1,n);

	scanf("%d",&m);

	int opt,l,r;

	double x;

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

	{

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

		if(opt == 1)

		{

			printf("%.15lf\n",query(root,l,r,1,n).maxv);

		}

		if(opt == 2)

		{

			printf("%.15lf\n",query(root,l,r,1,n).minv);

		}

		if(opt == 3)

		{

			scanf("%lf",&x);

			change(root,l,r,chuan(x),1,n);

		}

		if(opt == 4)

		{

			scanf("%lf",&x);

			change(root,l,r,bing(x),1,n);

		}

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}