题目内容
从上到下有 n n n 个碗,每个碗中水满了之后会往下一个碗流,最后一个碗水满了后会直接流出去。
现在有两种操作:
1 i x
表示往第 i i i 个碗里加 x x x 的水2 i
表示查询第 i i i 个碗里现在的水量
给定你 m m m 次操作,每次操作是上面两种之一,当面临第二种操作时,请输出第 i i i 个碗里现在的水量。
数据范围
- 1 ≤ n , m ≤ 2 ⋅ 1 0 5 1\leq n,m\leq 2\cdot 10^5 1≤n,m≤2⋅105
- 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n
- 1 ≤ x ≤ 1 0 9 1\leq x\leq 10^9 1≤x≤109
题解
复杂在于如果当前加入水的第 i i i 个碗及其之后的若干个碗都是满的,如何快速找到第一个没满的碗 j j j,水必然是流向 j j j 的。
并查集维护当前碗 i i i 指向的第一个没满的碗 j j j 即可。
时间复杂度: O ( n log n ) O(n\log n) O(nlogn)
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXBIT = 30;
const int MOD = 1e9 + 7;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
vector<int> cur(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> p(n + 1);
iota(p.begin(), p.end(), 0);
auto find = [&](int x) {
int root = x;
while (root != p[root]) root = p[root];
while (x != p[x]) {
int nx = p[x];
p[x] = root;
x = nx;
}
return root;
};
int m;
cin >> m;
while (m--) {
int op, idx, x;
cin >> op >> idx;
idx--;
int fa = find(idx);
if (op == 1) {
cin >> x;
if (fa == n) continue;
int l = fa;
while (x > 0 && l < n) {
int need = min(x, a[l] - cur[l]);
cur[l] += need;
x -= need;
if (cur[l] == a[l]) l += 1;
}
for (int i = fa; i < l; ++i) p[find(i)] = find(l);
} else {
cout << cur[idx] << "\n";
}
}
return 0;
}
文章评论