【AtCoder Regular Contest 082 F】Sandglass | Mrsrz's blog

线段树。

题目大意：

给定一个沙漏，总共有 $X$ 的沙子，有两个部分 A 和 B。

开始 A 在上面，有 $a$ 的沙子，每一单位时刻会向下漏 $1$ 的沙子。

给定时刻 $r_1,r_2,\ldots,r_k$，这些时刻沙漏会倒过来。

现在给出若干组询问，给定 $t,a$，问初始 A 中有 $a$ 的沙子，在时刻 $t$ 时，A 中有多少沙子。

题解：

不难发现，如果两种状态，初始时 A 中的沙子分别为 $x_1,x_2$ 且 $x_1\lt x_2$，则无论何时，A 中的沙子都满足 $x_1’\leq x_2’$。也就是说它始终是单调的。

我们再来看倒过来的操作。

我们直接让时间从一个时刻跳跃到下一个时刻，那么对所有初始状态而言，相当于做了全局加，全局对 $X$ 取 $\min$（或者全局减，全局对 $0$ 取 $\max$）。

由于是单调的，所以可以直接使用线段树维护。

Code：

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+5;
int X,k,r[N],ans[N],m,n;
struct node{
    int L,R,tag,add;
}d[N<<2];
struct que{
    int t,a,id;
}q[N];
vector<int>vec;
inline void update(int o){
    d[o].L=min(d[o<<1].L,d[o<<1|1].L);
    d[o].R=max(d[o<<1].R,d[o<<1|1].R);
}
void build(int l,int r,int o){
    if(l==r)d[o]=(node){vec[l],vec[r],0,0};else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        update(o);
    }
}
inline void pushdown(int o){
    if(d[o].tag){
        d[o<<1].tag=d[o<<1|1].tag=d[o].tag;
        d[o<<1].add=d[o<<1|1].add=0;
        if(d[o].tag==-1)
            d[o<<1].L=d[o<<1].R=d[o<<1|1].L=d[o<<1|1].R=0;
        else
            d[o<<1].L=d[o<<1].R=d[o<<1|1].L=d[o<<1|1].R=X;
        d[o].tag=0;
    }
    if(int&x=d[o].add){
        d[o<<1].add+=x,d[o<<1|1].add+=x;
        d[o<<1].L+=x,d[o<<1|1].L+=x;
        d[o<<1].R+=x;d[o<<1|1].R+=x;
        x=0;
    }
}
int query(int l,int r,int o,const int&pos){
    if(l==r)return d[o].L;
    pushdown(o);
    const int mid=l+r>>1;
    if(pos<=mid)return query(l,mid,o<<1,pos);
    return query(mid+1,r,o<<1|1,pos);
}
void increase(int l,int r,int o,const int&dlt){
    if(d[o].R+dlt<=X)
        d[o].L+=dlt,d[o].R+=dlt,d[o].add+=dlt;
    else if(d[o].L+dlt>=X)
        d[o].L=d[o].R=X,d[o].add=0,d[o].tag=1;
    else{
        pushdown(o);
        const int mid=l+r>>1;
        increase(l,mid,o<<1,dlt);
        increase(mid+1,r,o<<1|1,dlt);
        update(o);
    }
}
void decrease(int l,int r,int o,const int&dlt){
    if(d[o].L>=dlt)
        d[o].L-=dlt,d[o].R-=dlt,d[o].add-=dlt;
    else if(d[o].R<=dlt)
        d[o].L=d[o].R=d[o].add=0,d[o].tag=-1;
    else{
        pushdown(o);
        const int mid=l+r>>1;
        decrease(l,mid,o<<1,dlt);
        decrease(mid+1,r,o<<1|1,dlt);
        update(o);
    }
}
int main(){
    scanf("%d%d",&X,&k);
    for(int i=1;i<=k;++i)scanf("%d",r+i);
    r[k+1]=1e9+7;
    scanf("%d",&m);
    vec.push_back(-1);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&q[i].t,&q[i].a);
        q[i].id=i;
        vec.push_back(q[i].a);
    }
    sort(vec.begin(),vec.end()),vec.erase(unique(vec.begin(),vec.end()),vec.end());
    n=vec.size()-1;
    build(1,n,1);
    int cur=-1;
    for(int i=1,it=1;i<=k+1&&it<=m;++i){
        while(it<=m&&q[it].t<=r[i]){
            int pos=lower_bound(vec.begin(),vec.end(),q[it].a)-vec.begin();
            int now=query(1,n,1,pos)+cur*(q[it].t-r[i-1]);
            if(now<0)now=0;
            if(now>X)now=X;
            printf("%d\n",now);
            ++it;
        }
        if(cur==-1)
            decrease(1,n,1,r[i]-r[i-1]);
        else
            increase(1,n,1,r[i]-r[i-1]);
        cur*=-1;
    }
    return 0;
}