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;
  	}
  }