借教室 线段树+懒标记

啊哈磊

[mw_shl_code=cpp,true]#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
    int left,right,num,lazy;
}dataa[2000010];
int readd[1000001],jud=0;
void buildtree(int x,int y,int cur)
{
    int mid;
    dataa[cur].left=x;dataa[cur].right=y;
    if(x==y) dataa[cur].num=readd[x];
    else
    {
        mid=(x+y)/2;
        buildtree(x,mid,cur*2);buildtree(mid+1,y,cur*2+1);
        dataa[cur].num=min(dataa[cur*2].num,dataa[cur*2+1].num);
    }
}
void change(int sum,int x,int y,int cur)
{
    int mid;
    if(dataa[cur].left>=x && dataa[cur].right<=y)
    {
        dataa[cur].num-=sum;dataa[cur].lazy+=sum;
        if(dataa[cur].num<0) jud=1;
    }
    else
    {
        mid=(dataa[cur].left+dataa[cur].right)/2;
        dataa[cur*2].num-=dataa[cur].lazy;dataa[cur*2+1].num-=dataa[cur].lazy;
        dataa[cur*2].lazy+=dataa[cur].lazy;dataa[cur*2+1].lazy+=dataa[cur].lazy;
        dataa[cur].lazy=0;
        if(y<=mid) change(sum,x,y,cur*2);
        else if(x>=mid+1) change(sum,x,y,cur*2+1);
        else{change(sum,x,y,cur*2);change(sum,x,y,cur*2+1);}
        dataa[cur].num=min(dataa[cur*2].num,dataa[cur*2+1].num);
    }
}
int main()
{
    int m,n,i,a,b,c,ans=0;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++) scanf("%d",&readd);
    buildtree(1,n,1);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        change(a,b,c,1);
        if(jud==1 && ans==0) {ans=i;break;}
    }
    if(ans==0) printf("0");
    else printf("-1\n%d",ans);
    return 0;
}[/mw_shl_code]

Jason_MEI

- -
4567890

CommandCraft

但是为什么这个题我写的线段树会被卡掉一个点？

CommandCraft

而且你这个代码还没有位运算优化。所以我到底哪儿常数写大了...

4399APPLE

CommandCraft 发表于 2018-3-24 14:29
而且你这个代码还没有位运算优化。所以我到底哪儿常数写大了...

我看你真的是常数大了.jpg
标算差分的题强行加 log

CommandCraft

4399APPLE 发表于 2018-3-27 18:22
我看你真的是常数大了.jpg
标算差分的题强行加 log

标算我记得是有个二分答案吧。跟线段树一样都是nlogn。
反正我写的代码一直都是自带大常数了