本题数据量较大，用并查集把移走挡板后联通的几个池子合并成一个连通块，求某个池子的蓄水量，只需向上找其祖宗的值和池子总数即可。（每个连通块中，编号大的池子为编号小的节点的父亲）
#include<bits/stdc++.h>
using namespace std;
#define int
展开全文
不使用高级数据结构，仅用最基础算法的一个优雅的写法
思路：区间合并+前缀和
n,m=map(int,input().split())
pool=[0]+list(map(int,input().split()))
s=[0]*(n+10) #前缀和
for i in range(1,n+1):
展开全文
首先因为隔板的存在，所以整个水池开始是一坨一坨的，一共有 坨。
操作 就是把所有与 有交集的坨坨拿来进行合并，合并结果为总水量除以总池子数。
考虑用 set 维护，这样查询就是严格 级别的，我们来分析修改操作。
由于每次合并坨数都会减少 ，所以最多合并 次，均摊下来总复杂度为 ，这样总复杂
展开全文
D&E线段树做法
#include <iostream>
#include <iomanip>
using namespace std;
int a[200005];
struct elem {
double val;
int l,r;
};
struct
展开全文
区间集合管理 (Interval Management System)
针对频繁的区间合并与点查询，最理想的策略是维护一组不相交的连通区间（Disjoint Intervals）。
核心范式：基于有序集合的区间收缩
我们选择使用一个支持快速查找和维护有序性的数据结构（如 C++ 中的 std::se
展开全文
首先看到这一题的时候不难想到使用'并查集'来维护不同水池的联通，但是后来发现我们合并水池之后水位可能会出现变化，所以尝试给并查集加入总量记载的同时再加入合并数量的计算，最后，我们发现联通水池时一旦板子被撤掉就不需要再管他了，而且题目可能在联通方面会有很大的时间消耗，正好有并查集在题目中间，微调一下加
展开全文
import sys
input=sys.stdin.readline
print=sys.stdout.write
def _join(u,v):
u_p,v_p=_find(u),_find(v)
if u_p<v_p:v_p,u_p=u_p,v_p
if u_p
展开全文
核心算法：结合「并查集（路径压缩 + 按秩合并）」和「跳跃指针（nxt 数组）」，解决区间合并的超时问题；核心逻辑：并查集维护连通块的数值和、节点数，支持快速查询平均值；跳跃指针nxt[i]记录连通块右边界的下一个位置，合并时直接跳过整个连通块，避免逐点遍历；优化目标：将区间合并的时间复杂度从 O
展开全文
使用并查集进行合并，每一次的（l,r)合并从左到右更新根节点（指向r），由于不会重复拆板子，所以遍历的合并方法是可行的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector&l
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
