题解：P8856 [POI2002] 火车线路

· · 题解

题意简述

对长度为 C 的数组区间修改，且最大值不能超过 S，对每次修改后最大值是否超过 S 进行判断，若超过就不修改。

思路

我们知道因为数组修改前的最大值肯定不会大于 S，所以求最大值可以转化为求要修改的区间的最大值。

又有区间查询，又有区间修改，想到什么？没错，就是分块！当然有一个细节就是区间修改的右边界要减一，因为此时已经下车了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=60005,T=255;
int n,s,m;//n个点，s为座位数量，m为操作次数。
int block,t,st[T],ed[T],pos[N];
int a[N],add[T],mx[T];//a存数组，add存每个块的标记，mx为块的最大值。
void build(){//初始化。
    block=sqrt(n);
    t=n/block;
    if(n%block)t++;
    for(int i=1;i<=t;i++){
        st[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1;
}

int update(int l,int r,int d){//更新函数，由于增加一次判断一次所以把判断加入。
    int p=pos[l],q=pos[r];
    if(p==q){//如果在一个块，暴力做。
        int tmblar=0;//The max between l and r.
        for(register int i=l;i<=r;i++)tmblar=max(tmblar,a[i]+add[p]);
        //先求出原有的最大值。
        if(tmblar+d>s)return 0;//判断，若不行直接返回0。
        mx[p]=0;//暴力重新算最大值。
        for(register int i=st[p];i<=ed[p];i++){
            if(l<=i&&i<=r)a[i]+=d;//增加。
            mx[p]=max(mx[p],a[i]+add[p]);
        }
        return 1;//可以被满足。
    }
    else{
        int tmblar=0;//The max between l and r.
        for(register int i=l;i<=ed[p];i++)tmblar=max(tmblar,a[i]+add[p]);
        for(register int i=p+1;i<=q-1;i++)tmblar=max(tmblar,mx[i]);
        for(register int i=st[q];i<=r;i++)tmblar=max(tmblar,a[i]+add[q]);
        //求出原有的最大值。
        if(tmblar+d>s)return 0;//判断，若不行直接返回0。
        mx[p]=0;//暴力重新算最大值。
        for(register int i=st[p];i<=ed[p];i++){
            if(l<=i)a[i]+=d;
            mx[p]=max(mx[p],a[i]+add[p]);
        }
        for(register int i=p+1;i<=q-1;i++){
            add[i]+=d;//对整个块标记。
            mx[i]+=d;//因为都加了d，所以最大值也加d。
        }
        mx[q]=0;
        for(register int i=st[q];i<=ed[q];i++){
            if(i<=r)a[i]+=d;
            mx[q]=max(mx[q],a[i]+add[q]);
        }
        return 1;//可以被满足。
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>s>>m;
    build();
    for(register int i=1;i<=m;i++){
        int L,R,D;
        cin>>L>>R>>D;
        if(update(L,R-1,D))cout<<"T"<<'\n';//一定是R-1！！！
        else cout<<"N"<<'\n';//用\n可以快一点。
    }
    return 0;
}

吸氧可过，不开就超时一点点。