这道题的题意已经说得很清楚了,因为每次剪都需要1s,我们剪的次数必须最少,一次剪得头发数要最大。

我们用 $a_i$ 表示头发长度, $b_i$ 表示 $a_i$ 是否剪过,就能很方便的进行判断是否可以剪一段头发。可是这道题的长度会持续增加,每次判重的操作十分不便,我们可以先剪再判重。详细解释见代码。这题还有一个坑点就是 $10^9$ 的数据得开long long

$\mathcal{Code}$

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