题解CF1055B【Alice and Hairdresser】
Rbu_nas
2019-02-23 11:59:08
这道题的题意已经说得很清楚了，因为每次剪都需要1s，我们剪的次数必须最少，一次剪得头发数要最大。
我们用$a_i$表示头发长度，$b_i$表示$a_i$是否剪过，就能很方便的进行判断是否可以剪一段头发。可是这道题的长度会持续增加，每次判重的操作十分不便，我们可以**先剪再判重**。详细解释见代码。这题还有一个坑点就是$10^9$的数据得开`long long`
$\mathcal{Code}$
```cpp
#include <cstdio>
using namespace std;
#define N 100003
#define LL long long
int n, q, l, opt, p, h;
LL a[N], res;
bool flag[N];
int main(void)
{
scanf("%d %d %d", &n, &q, &l);
for(int i=1; i<=n; ++i)
{
scanf("%lld", &a[i]);
if(a[i] > l)
{
flag[i]=true;
if(!flag[i-1]) ++res; //进来预处理，不能一段剪的ans+1
}
}
while(q--)
{
scanf("%d", &opt);
if(!opt)
printf("%lld\n", res);
else
{
scanf("%d %d", &p, &h);
if(a[p] <= l && a[p]+h > l) //这里条件注意一下，之前的a[i]>l的情况已经计数，如果直接a[p]>l的话会重复计数
{
++res; flag[p]=true;
if(flag[p-1]) --res;
if(flag[p+1]) --res;
/*
这里也要注意，如果前面一根和后面一根都剪过，a[p]这根头发相当于连接了新的一段，ans-=2
如果只是前面或后面见过a[p]只是连接了1根头发，ans-=1
*/
}
a[p]+=h;
}
}
return 0;
}
```