JZOJ-senior-5879. 【NOIP2018提高组模拟9.22】电路图 B
Time Limits: 3000 ms Memory Limits: 262144 KB
Description
Input
Output
Sample Input
5
2 4 1 5 3
7
2 2 4
3 1 3 2
2 2 4
1 2 4
4 2 3 6
1 2 4
2 2 4
Sample Output
1.0000000
3.0
6
5.0000
2.0000000000000
Data Constraint
Hint
Solution
30%:纯暴力
50%~70%:线段树
100%:神奇的线段树
根据初中物理知识,我们知道:
串联一个电阻
并联一个电阻
小结论:一个较大的电阻串联或并联一个电阻,它还是较大的
也就是说对于3,4操作的那一段序列来讲,被操作的区间里的电阻的相对大小不变
通过观察,我们发现一个新的电阻可以用原电阻经过加法与乘法运算得到
于是大佬们想到了用一次函数除以一次函数的形式来表示这个电阻
(像我这种完全没想过可以这样表示的就只能乖乖打暴力了。。。 )
首先,我们考虑如何表示两种操作
我们将电阻表示为 的形式,设原电阻为
那么操作3(串联一个电阻)就相当于一个 的操作
原因:将四元组代入可得 ,可得新电阻为
同理操作4(并联一个电阻)就相当于一个 的操作
原因:将四元组代入可得 ,可得新电阻为
至此,每次的串或并联电阻可以成功被表示
下一步,我们考虑如何合并标记
设树上某一节点的原标记为 ,设原电阻为
那么当前节点经过操作后的电阻应该是这样的
而它现在要与另一个标记 合并
那么合并后的电阻就是 ,将t的表达式代入,
经化简,可得新电阻为
对比一下,我们就得到新的四元组啦
至此,我们成功合并了标记
最后,就是注意精度一下问题惹
Code
#include<algorithm>
#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ldb long double
#define db double
#define L x<<1
#define R L|1
using namespace std;
const int N=25e4+5;
const ldb MX=1e9,MN=0;
int n,m,opt,opl,opr,opx,e[N];
ldb ans;
struct tree
{
ldb a,b,c,d,mx,mn;
}tr[4*N];
void clear(int x)//初始化,可不是全都是0哦~
{
tr[x].a=tr[x].d=1,tr[x].b=tr[x].c=0;
}
void mix(tree &p,tree q)//合并标记
{
p.mx=(q.a*p.mx+q.b)/(q.c*p.mx+q.d);
p.mn=(q.a*p.mn+q.b)/(q.c*p.mn+q.d);
ldb a=q.a*p.a+q.b*p.c,b=q.a*p.b+q.b*p.d;
ldb c=q.c*p.a+q.d*p.c,d=q.c*p.b+q.d*p.d;
p=(tree){1,b/a,c/a,d/a,p.mx,p.mn};//据说不这么打会爆,反正我没尝试过
}
void down(int x)//下传标记
{
mix(tr[L],tr[x]);
mix(tr[R],tr[x]);
clear(x);
}
void update(int x)//更新最大最小电阻值
{
tr[x].mn=min(tr[L].mn,tr[R].mn);
tr[x].mx=max(tr[L].mx,tr[R].mx);
}
void build(int x,int l,int r)//建树
{
clear(x);
if(l==r)
{
tr[x].mx=tr[x].mn=e[l];
return;
}
int mid=(l+r)>>1;
build(L,l,mid);
build(R,mid+1,r);
update(x);
}
ldb get(ldb v)//计算并联的情况
{
return v*opx/(v+opx);
}
void calc(int x,int l,int r)//由于我懒,所以四个操作就打在一起啦
{
if(l^r) down(x);
if(opl<=l&&opr>=r)
{
if(opt==1) ans=max(ans,tr[x].mx);
if(opt==2) ans=min(ans,tr[x].mn);
if(opt==3) tr[x]=(tree){1,opx,0,1,tr[x].mx+opx,tr[x].mn+opx};
if(opt==4) tr[x]=(tree){opx,0,1,opx,get(tr[x].mx),get(tr[x].mn)};
return;
}
int mid=(l+r)>>1;
if(opl<=mid) calc(L,l,mid);
if(opr>mid) calc(R,mid+1,r);
if(opt>=3) update(x);
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d",&n);
fo(i,1,n) scanf("%d",&e[i]);
build(1,1,n);
scanf("%d",&m);
fo(i,1,m)
{
scanf("%d%d%d",&opt,&opl,&opr);
if(opt<=2)
{
if(opt==1) ans=MN; else ans=MX;
calc(1,1,n);
printf("%.10lf\n",(db)ans);
//输出时要转回double,否则输出就全是0了;好像也可以将字母l大写
}
else scanf("%d",&opx),calc(1,1,n);
}
}