题解 | #小苯的蓄水池(并查集)#

小苯的蓄水池(hard)

https://ac.nowcoder.com/acm/contest/93847/E

#include <bits/stdc++.h>
using namespace std;

const int N  = 2e5+10;
int n,m;
int f[N];
double x;
struct node{
    double sum;
    int cnt;
    int l,r;
}a[N];

int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++){
        scanf("%lf",&a[i].sum);
        a[i].cnt = 1;
        f[i] = i;
        a[i].l = a[i].r = i;
    }
    
    while(m--){
        int op,x,y;
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d",&x,&y);
            for(int i = a[f[x]].r+1;i<=a[f[y]].l;i++){
                if(find(i)==find(x)) continue;
                f[find(i)] = find(x);
                a[f[x]].sum += a[i].sum;
                a[f[x]].cnt += a[i].cnt;
                a[f[x]].r = max(a[f[x]].r,a[f[i]].r);
                a[f[x]].l = min(a[f[x]].l,a[f[i]].l);
            }
        }
        else{
            scanf("%d",&x);
            printf("%.10lf\n",a[find(f[x])].sum/a[find(f[x])].cnt);
        }
    }
    
    return 0;
}
全部评论

相关推荐

废铁汽车人:秋招真是牛鬼蛇神齐聚一堂
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务