题目

传送门=￣ω￣=

题解

显然线段树是可以的，搞 m 次区间修改、区间最小值查询即可。
复杂度 $O(mlogn)$
然而听说普通线段树被卡常，不加读入优化 70 分，加读入优化 95，得用 zkw 线段树。
所以我打了差分，复杂度只有 $O(n+m)$, 理论上不存在更优的做法了，因为输入复杂度就是 $O(n+m)$了。
设 $f[i]=r[i]-r[i-1]$，
那么每次修改区间 $[l,r]$，区间减 d，则只要 $f[l]-=d,f[r]+=d$
然后我们区间修改了m次以后，还原r[i]的值（$r[i]=f[1]+f[2]+…+f[i]=r[i-1]+f[i]$)，如果某个r[i]<0的话，就依次从第m个修改开始撤销，直到这个r[i]>=0 了。
撤销也是一样，只要 $f[l]+=d,f[r]-=d$，然后如果 $l\leq i\leq r$的话 $r[i]+=d$。
这样最后答案就是最后一个撤销的修改的序号了。
当然如果没撤销，输出 0 即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,d[1000005],v[3][1000005],sum,ans;
int main()
{
    scanf("%lld%lld",&n,&m),ans=m;
    for(int i=1,j=0,k;i<=n;i++)scanf("%d",&k),d[i]=k-j,j=k;
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lld",&v[0][i],&v[1][i],&v[2][i]),
        d[v[1][i]]-=v[0][i],d[v[2][i]+1]+=v[0][i];
    for(int i=1;i<=n;i++)
        for(sum+=d[i];ans>=1&&sum<0;ans--)
        {
            d[v[1][ans]]+=v[0][ans],d[v[2][ans]+1]-=v[0][ans];
            if(v[1][ans]<=i&&i<=v[2][ans])sum+=v[0][ans];
        }
    if(ans==m)printf("0\n");else printf("-1\n%lld\n",ans+1);
    return 0; 
}