题目

传送门= ̄ω ̄=

题解

显然线段树是可以的,搞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; 
} 
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *