小苯的蓄水池（hard）
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小苯有一个大的蓄水场，其中有恰好n nn个蓄水池排成一排，编号分别为1 11到n nn，其中第i ii个蓄水池中的水量为a i a_iai。
起初每两个相邻蓄水池之间都有一个隔板，而现在小苯希望在蓄水场维护一些操作和查询，具体的：
- 1 l r 1 \ l \ r1lr表示将第l ll个水池和第r rr个水池之间所有的挡板拿走。（保证：1 ≤ l < r ≤ n 1≤l<r≤n1≤l<r≤n）
- 2 i 2 \ i2i表示查询第i ii个水池目前的水量。
（如果挡板被拿走，则原本挡板两侧水会混合在一起，最终对应的水量会变为平均值，具体可以看样例解释。）
请你帮他回答每次查询吧。
（注意：因本题输入输出数据量较大，请选手选择快速的输入输出方式。）
输入描述：
输入包含m + 2 m+2m+2行。
第一行输入两个正整数1 ≤ n , m ≤ 2 × 10 5 1≤n,m≤2×10^51≤n,m≤2×105，分别表示蓄水场中水池的个数，以及操作的次数。
第二行n nn个整数a i ( 1 ≤ a i ≤ 10 9 ) a_i (1≤a_i≤10^9)ai(1≤ai≤109)，表示每个水池初始时的水量。
接下来m mm行，每行第一个整数o p ( 1 ≤ o p ≤ 2 ) op(1≤op≤2)op(1≤op≤2)表示操作。
如果o p = 1 op=1op=1，则表示取掉挡板操作，再输入两个正整数l , r ( 1 ≤ l < r ≤ n ) l,r (1≤l<r≤n)l,r(1≤l<r≤n)。
如果o p = 2 op=2op=2，则表示查询操作，再输入一个正整数i ( 1 ≤ i ≤ n ) i (1≤i≤n)i(1≤i≤n)。
（注意：已经拿走的挡板在以后的操作中都是“被拿走”的状态。）
（数据保证至少有一次查询操作。）
输出描述：
输出包含若干行，每行一个实数，表示对每个o p = 2 op=2op=2的询问做出的回答。
（与正确答案的绝对误差不超过10 − 4 10^{−4}10−4则视为正确。）
示例1
输入：
4 6 1 2 4 5 1 1 3 2 1 2 3 1 1 4 2 1 2 4输出：
2.3333333333 2.3333333333 3.0000000000 3.0000000000说明：
打开1 11到3 33号之间所有的挡板，则1 2 3 1 \ 2 \ 3123号水池中的水会混合，水量为他们的平均值：7 / 3 = 2.333... 7/3=2.333...7/3=2.333...。
再打开1 11到4 44号之间所有的挡板，则1 2 3 4 1 \ 2 \ 3 \ 41234号水池中的水都会混合，水量为他们的平均值：12 / 4 = 3 12/4 = 312/4=3。
解题思路
本题核心是通过并查集（带权合并）高效维护蓄水池的合并与查询：初始化每个蓄水池为独立集合，p[i]记录父节点，sz[i]记录集合大小，a[i]记录集合总水量；执行移除挡板操作（ 1 l r ） （1 \ l \ r）（1lr）时，从l的根节点开始，循环合并当前节点与下一个节点（直到覆盖l~r区间），合并时将小集合合并到大集合，累加总水量和集合大小；执行查询操作（ 2 i ） （2 \ i）（2i）时，找到i的根节点，计算总水量除以集合大小的平均值并输出。并查集的路径压缩和按序合并保证每次操作的均摊时间复杂度接近O ( 1 ) O(1)O(1)，整体时间复杂度为O ( n + m α ( n ) ) O(n + m α(n))O(n+mα(n))（α αα为阿克曼函数反函数，可视为常数），适配n 、 m ≤ 2 × 10 5 n、m≤2×10^5n、m≤2×105的规模，精准且高效地处理区间合并与单点查询。
总结
- 核心逻辑：用并查集维护合并后的蓄水池集合，记录每个集合的总水量和大小，查询时计算平均值。
- 关键操作：移除挡板时循环合并区间内的相邻蓄水池，查询时找根节点计算平均值。
- 效率保障：并查集的路径压缩和按序合并，使操作均摊时间复杂度接近常数，适配大数据量。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=2e5+10;constll mod=1e4+7;constll INF=1e18;ll p[N],sz[N];doublea[N];llfind(ll x)//并查集{if(p[x]!=x)p[x]=find(p[x]);returnp[x];}voidadd(ll u,ll v){ll pu=find(u),pv=find(v);if(u>v)swap(u,v);p[pu]=p[pv];sz[pv]+=sz[pu];a[pv]+=a[pu];}intmain(){ll n,m;cin>>n>>m;for(ll i=1;i<=n;i++){cin>>a[i];p[i]=i;sz[i]=1;}while(m--){ll op;cin>>op;if(op==1){ll l,r;cin>>l>>r;for(ll i=find(l);i<r;i=find(i))add(i,i+1);}else{ll q;cin>>q;ll t=find(q);printf("%.10lf\n",a[t]/sz[t]);}}return0;}
