Alice and Hairdresser
第一眼线段树，第二眼好像可以直接用数组模拟。
当一根头发长于 \(l\)，它再长多长其实都一样，所以不用开 long long。
如果一根新的头发长到比 \(l\) 长，那可以分成以下几种情况：
-
如果它左侧和右侧只有一个元素大于 \(l\) ，那答案不变。
-
如果左侧和右侧都大于 \(l\)，答案减一。因为相当于将左侧区间和右侧区间并到一起。
-
如果右侧和左侧都不大于 \(l\)，答案加一。
在刚开始时统计一遍答案，每次做修改就行了。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
int n, m, l;
vector<int> a;
int ans;
int main() {
cin >> n >> m >> l;
a.resize(n + 7);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
if (a[i] > l && a[i - 1] <= l)
ans++;
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x, y;
cin >> x >> y;
if (a[x] > l) continue;
a[x] += y;
if (a[x] <= l) continue;
if (a[x - 1] > l && a[x + 1] > l) ans--;
if (a[x - 1] <= l && a[x + 1] <= l) ans++;
}
if (op == 0)
cout << ans << endl;
}
}