首页 > 试题广场 >

小苯的蓄水池（hard）

[编程题]小苯的蓄水池（hard）

热度指数：1193 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小苯有一个大的蓄水场，其中有恰好 $n$ 个蓄水池排成一排，编号分别为 $1$ 到 $n$ ，其中第 $i$ 个蓄水池中的水量为 $a_i$ 。

起初每两个相邻蓄水池之间都有一个隔板，而现在小苯希望在蓄水场维护一些操作和查询，具体的：
$\bullet\ 1\ \ l\ \ r$ 表示将第 $l$ 个水池和第 $r$ 个水池之间所有的挡板拿走。（保证： $1 \leq l < r \leq n$ ）
$\bullet\ 2\ \ i$ 表示查询第 $i$ 个水池目前的水量。

（如果挡板被拿走，则原本挡板两侧水会混合在一起，最终对应的水量会变为平均值，具体可以看样例解释。）

请你帮他回答每次查询吧。

（注意：因本题输入输出数据量较大，请选手选择快速的输入输出方式。）

输入描述:

输入包含  行。
第一行输入两个正整数 ，分别表示蓄水场中水池的个数，以及操作的次数。
第二行  个整数 ，表示每个水池初始时的水量。
接下来  行，每行第一个整数  表示操作。
 如果 ，则表示取掉挡板操作，再输入两个正整数 。
 如果 ，则表示查询操作，再输入一个正整数 。
（注意：已经拿走的挡板在以后的操作中都是“被拿走”的状态。）
（数据保证至少有一次查询操作。）

输出描述:

输出包含若干行，每行一个实数，表示对每个  的询问做出的回答。
（与正确答案的绝对误差不超过  则视为正确。）

示例1

输入

输出

2.3333333333
2.3333333333
3.0000000000
3.0000000000

说明

打开 1 到 3 号之间所有的挡板，则 1 2 3 号水池中的水会混合，水量为他们的平均值：7/3=2.333...。
再打开 1 到 4 号之间所有的挡板，则 1 2 3 4 号水池中的水都会混合，水量为他们的平均值：12/4 = 3。

算法知识视频讲解

C++

chenlan114

核心算法：结合「并查集（路径压缩 + 按秩合并）」和「跳跃指针（nxt 数组）」，解决区间合并的超时问题；

核心逻辑：

并查集维护连通块的数值和、节点数，支持快速查询平均值；
跳跃指针nxt[i]记录连通块右边界的下一个位置，合并时直接跳过整个连通块，避免逐点遍历；

优化目标：将区间合并的时间复杂度从 O (n) 降至 O (α(n))（α 为阿克曼反函数，接近常数），适配 2e5 级别的数据规模。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=2e5+5;

struct UF{
    double v;
    UF* root;
    ll rank=0;
    ll cnt=1;
};
 
UF a[N];
ll nxt[N];
 
UF *Root(UF* a){
    if(a->root!=a){
        a->root=Root(a->root);
    }
    return a->root;
}
 
void merge(ll x,ll y){
    UF* rx=Root(&a[x]);
    UF* ry=Root(&a[y]);
    if(rx==ry)return;
 
    if(rx->rank<ry->rank){
        rx->root=ry;
        ry->cnt+=rx->cnt;
        ry->v+=rx->v;
    }else{
        ry->root=rx;
        rx->cnt+=ry->cnt;
        rx->v+=ry->v;
        if(rx->rank==ry->rank){
            rx->rank++;
        }
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 加速IO
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>a[i].v;
        a[i].root=&a[i]; // 并查集初始化：根为自身
        nxt[i] = i + 1; // 跳跃指针初始化：单个节点的右边界下一位是i+1
    }

    for(ll i=1;i<=m;i++){
        ll op;
        cin>>op;
        if(op==1){
            ll l,r;
            cin>>l>>r;
            ll cur = l;
            // 区间合并：跳跃指针跳过整个连通块，避免逐点遍历
            while(cur <= r){
                ll block_r = nxt[cur]; // 当前连通块的右边界下一位
                if(block_r > r) break; // 连通块超出目标区间，终止
                
                merge(cur, block_r); // 合并当前块与下一个块
                nxt[cur] = nxt[block_r]; // 更新跳跃指针，指向合并后新块的右边界
                cur = block_r; // 处理下一个连通块
            }
        }else if(op==2){
            ll k;
            cin>>k;
            printf("%.9lf\n",Root(&a[k])->v/(double)Root(&a[k])->cnt); // 输出连通块平均值
        }
    }
    return 0;
}

发表于 2026-03-09 12:53:55 回复(0)

提交观点

问题信息

难度：

1条回答 13收藏 56浏览

小苯的蓄水池（hard）

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题