• 核心算法：结合「并查集（路径压缩 + 按秩合并）」和「跳跃指针（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;
}