会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
解题思路
并网会把若干主机并入同一个集群，询问需要知道某台主机当前所在集群的算力之和。这是带权并查集：每个根维护该集群的规模。
询问与并网都带时刻，适合离线处理：
- 把每次并网记为类型 0 的事件，把每次询问记为类型 1 的事件（并记下原询问编号）。
- 按时刻从小到大排序；同一时刻类型 0 排在类型 1 前面，从而保证“先并网再询问”。
- 按顺序扫描：遇到并网就把该批主机依次合并；遇到询问就用并查集找到根，输出其规模。
题目内容
有 n 台主机，第 i 台的算力为 wi。初始时每台主机自成一个集群，集群的规模等于其中所有主机的算力之和。
共发生 m 次并网：在时刻 t，把给定的若干台主机所在的集群合并成一个。共有 q 次询问：在时刻 t 询问某台主机当前所在集群的规模。
同一时刻若既有并网又有询问，先完成该时刻的全部并网，再回答询问。
主机编号从 1 开始。主机数不超过 10^5 且至少为 1，并网次数与询问次数均不超过 10^5 且可以为 0。算力与时刻均为不超过 10^9 的非负整数。每次并网至少涉及 1 台主机。
输入描述
