小苯的蓄水池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≤lr≤n1≤lr≤n2 i 2 \ i2i表示查询第i ii个水池目前的水量。如果挡板被拿走则原本挡板两侧水会混合在一起最终对应的水量会变为平均值具体可以看样例解释。请你帮他回答每次查询吧。注意因本题输入输出数据量较大请选手选择快速的输入输出方式。输入描述输入包含m 2 m2m2行。第一行输入两个正整数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 op1op1则表示取掉挡板操作再输入两个正整数l , r ( 1 ≤ l r ≤ n ) l,r (1≤lr≤n)l,r(1≤lr≤n)。如果o p 2 op2op2则表示查询操作再输入一个正整数i ( 1 ≤ i ≤ n ) i (1≤i≤n)i(1≤i≤n)。注意已经拿走的挡板在以后的操作中都是“被拿走”的状态。数据保证至少有一次查询操作。输出描述输出包含若干行每行一个实数表示对每个o p 2 op2op2的询问做出的回答。与正确答案的绝对误差不超过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/32.333...7/32.333...。再打开1 11到4 44号之间所有的挡板则1 2 3 4 1 \ 2 \ 3 \ 41234号水池中的水都会混合水量为他们的平均值12 / 4 3 12/4 312/43。解题思路本题核心是通过并查集带权合并高效维护蓄水池的合并与查询初始化每个蓄水池为独立集合p[i]记录父节点sz[i]记录集合大小a[i]记录集合总水量执行移除挡板操作 1 l r 1 \ l \ r1lr时从l的根节点开始循环合并当前节点与下一个节点直到覆盖l~r区间合并时将小集合合并到大集合累加总水量和集合大小执行查询操作 2 i 2 \ i2i时找到i的根节点计算总水量除以集合大小的平均值并输出。并查集的路径压缩和按序合并保证每次操作的均摊时间复杂度接近O ( 1 ) O(1)O(1)整体时间复杂度为O ( n m α ( n ) ) O(n m α(n))O(nmα(n))α αα为阿克曼函数反函数可视为常数适配n 、 m ≤ 2 × 10 5 n、m≤2×10^5n、m≤2×105的规模精准且高效地处理区间合并与单点查询。总结核心逻辑用并查集维护合并后的蓄水池集合记录每个集合的总水量和大小查询时计算平均值。关键操作移除挡板时循环合并区间内的相邻蓄水池查询时找根节点计算平均值。效率保障并查集的路径压缩和按序合并使操作均摊时间复杂度接近常数适配大数据量。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N2e510;constll mod1e47;constll INF1e18;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 pufind(u),pvfind(v);if(uv)swap(u,v);p[pu]p[pv];sz[pv]sz[pu];a[pv]a[pu];}intmain(){ll n,m;cinnm;for(ll i1;in;i){cina[i];p[i]i;sz[i]1;}while(m--){ll op;cinop;if(op1){ll l,r;cinlr;for(ll ifind(l);ir;ifind(i))add(i,i1);}else{ll q;cinq;ll tfind(q);printf(%.10lf\n,a[t]/sz[t]);}}return0;}