牛客66E
作者:
Air1222
,
2024-11-05 21:07:33
,
所有人可见
,
阅读 2
//用并查集合并时,只需要把当前区间的祖先节点绑定在同一个节点即可
//我们设为每个区间的右端点
//开一个总容积和个数数组记录即可(保证精度)
//会发现TLE
//我们发现,当每个节点的祖先节点都为右端点时,我们就没有必要枚举当前点到右端点的节点了,我们直接找到其右端点,更新其右端点,前面的节点也会随之更新
//即i=find(i),这样,时间复杂度即可将为O(n)
//即,并查集祖先节点更新,子节点也会随之更新(之前没注意到)
#include <iostream>
using namespace std;
const int N = 2e5+10;
typedef long long LL;
int p[N];
LL s[N];
LL v[N];
int c[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
{
c[i]=1;
p[i]=i;
s[i]=v[i];
}
while(m--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int l,r;
scanf("%d%d",&l,&r);
int b=find(r);
for(int i=l;i<=r-1;i++)
{
i=find(i);
int a=find(i);
if(a!=b)
{
c[b]+=c[a];
s[b]+=s[a];
p[a]=p[b];
}
}
}
else
{
int x;
scanf("%d",&x);
x=find(x);
printf("%.5f",1.0*s[x]/c[x]);
puts("");
}
}
}