P7560 [JOISC 2021 Day1] フードコート

Genius_Star · 2024-04-02 09:49:34 · 题解

这里提供一个在线主席树算法。

题意：

有一个长为 n 的序列，序列每个位置有个队列。

有 m 个操作，每个操作可能是以下几种之一：

• 查询某个队列中第 k 个人的类型（不足 k 个输出 0）。

思路：

发现离开的操作很麻烦，先抛掉，即先考虑性质 C 的做法。

假设现在只有两个操作：

• 区间加。

• 求 x 号点所有版本中 \ge y 时最靠前的版本。

明显是主席树板子，但是发现一般主席树只支持单点修改，区间查。

而本题我们需要区间修改，单点查询，注意是单点查询，那么我们可以标记永久化，即不下传懒标记（因为这样修改的点太多了，主席树不好维护），那我们可以写一个标记永久化主席树，每个点维护当前版本下区间加的值。

对于查询，因为都是加法，没有减法，那么一个点的值是单调不递减，所以考虑二分算法，可以二分版本的编号。

• 初始 l=1,r=i-1。

• 若 a_{mid,x} \ge y（即 mid 版本时 x 号点的值大于等于 y），那么说明 [mid,i-1] 的版本都满足，将 r \to mid-1,ans \to mid；否则将 l \to mid+1。

• 最后答案就是 c_{ans}（ans 这个版本时加入的人的类型）。

时间复杂度为 O(N \log^2 N)。

此时考虑删除操作，设第 i 个队列要删除 s_i 个人，那么询问时就相当于查询第 (y+s_i) 个人的类型，就可以转化为上述主席树做法。

现在想一下如何求 s_i，因为“删除人数 = 总共加入人数 - 当前人数”；考虑维护上述两个信息。

维护每个队列的总人数，就是在操作 1 时将 [l,r] 区间加 k。

发现将区间 a_i \to \max(a_i-k,0) 是不好维护的，考虑将这个操作拆开，即先区间减，再对区间取 \max。

因为不需要动态维护区间和，只需要单点查询，可以不用吉司机线段树；考虑直接暴力维护加法标记和 \max 标记，单点查询时下传即可（注意当 \max 标记存在时，加法标记也要累加过去）。

总时间复杂度为 O(N \log^2 N)。

常数偏大，谨慎使用。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=250050,INF=1e17;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct Node{
    int lchild,rchild;
    ll data;
}X[N*25];
ll y;
int n,m,q,op,l,r,x,k,sum;
int c[N],id[N],ans[N];
int root[N];
inline void updata(register int &k,register int l,register int r,register int L,register int R,register int v){
    X[++sum]=X[k];
    k=sum;
    if(l==L&&R==r){
        X[k].data+=v;
        return ;
    }
    ll mid=(l+r)>>1;
    if(R<=mid)
      updata(X[k].lchild,l,mid,L,R,v);
    else if(L>mid)
      updata(X[k].rchild,mid+1,r,L,R,v);
    else{
        updata(X[k].lchild,l,mid,L,mid,v);
        updata(X[k].rchild,mid+1,r,mid+1,R,v);
    }
}
inline void qurey(register int k,register int l,register int r,register int i,register ll &t){
    if(!k)
      return ;
    t+=X[k].data;
    if(l==i&&r==i)
      return ;
    register int mid=(l+r)>>1;
    if(i<=mid)
      qurey(X[k].lchild,l,mid,i,t);
    else
      qurey(X[k].rchild,mid+1,r,i,t);
}
class Tree1{
public:
    struct Node{
        ll data;
        ll tag;
    }X[N<<2];
    inline void add(register int k,register ll v){
        X[k].data+=v;
        X[k].tag+=v;
    }
    inline void push_down(register int k){
        if(X[k].tag){
            add(k<<1,X[k].tag);
            add(k<<1|1,X[k].tag);
            X[k].tag=0;
        }
    }
    inline void updata(register int k,register int L,register int R,register int l,register int r,register int v){
        if(L==l&&r==R){
            add(k,v);
            return ;
        }
        push_down(k);
        register int mid=(L+R)>>1;
        if(r<=mid)
          updata(k<<1,L,mid,l,r,v);
        else if(l>mid)
          updata(k<<1|1,mid+1,R,l,r,v);
        else{
            updata(k<<1,L,mid,l,mid,v);
            updata(k<<1|1,mid+1,R,mid+1,r,v);
        }
    }
    inline ll qurey(register int k,register int L,register int R,register int i){
        if(L==i&&i==R)
          return X[k].data;
        push_down(k);
        register int mid=(L+R)>>1;
        if(i<=mid)
          return qurey(k<<1,L,mid,i);
        else
          return qurey(k<<1|1,mid+1,R,i);
    }
}T1;
class Tree2{
public:
    struct Node{
        int l,r;
        ll data;
        ll tag1;
        ll tag2;
    }X[N<<2];
    inline void add(register int k,register ll v){
        X[k].data+=v;
        X[k].tag1+=v;
        if(X[k].tag2!=-INF)
          X[k].tag2+=v;
    }
    inline void Max(register int k,register ll v){
        X[k].data=max(X[k].data,v);
        X[k].tag2=max(X[k].tag2,v);
    }
    inline void push_down(register int k){
        if(X[k].tag1){
            add(k<<1,X[k].tag1);
            add(k<<1|1,X[k].tag1);
            X[k].tag1=0;
        }
        if(X[k].tag2!=-INF){
            Max(k<<1,X[k].tag2);
            Max(k<<1|1,X[k].tag2);
            X[k].tag2=-INF;
        }
    } 
    inline void build(register int k,register int l,register int r){
        X[k].l=l,X[k].r=r;
        X[k].tag2=-INF;
        if(l==r)
          return ;
        register int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r); 
    }
    inline void updata(register int k,register int l,register int r,register int v){
        if(X[k].l==l&&r==X[k].r){
            add(k,v);
            return ;
        }
        push_down(k);
        register int mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          updata(k<<1,l,r,v);
        else if(l>mid)
          updata(k<<1|1,l,r,v);
        else{
            updata(k<<1,l,mid,v);
            updata(k<<1|1,mid+1,r,v);
        }
    }
    inline void Max(register int k,register int l,register int r,register int v){
        if(X[k].l==l&&r==X[k].r){
            Max(k,v);
            return ;
        }
        push_down(k);
        register ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          Max(k<<1,l,r,v);
        else if(l>mid)
          Max(k<<1|1,l,r,v);
        else{
            Max(k<<1,l,mid,v);
            Max(k<<1|1,mid+1,r,v);
        }
    }
    inline ll qurey(register int k,register int i){
        if(X[k].l==i&&i==X[k].r)
          return X[k].data;
        push_down(k);
        register ll mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          return qurey(k<<1,i);
        else
          return qurey(k<<1|1,i);
    }
}T2;
int main(){
    n=read(),m=read(),q=read();
    T2.build(1,1,n);
    for(register int i=1;i<=q;i++){
        root[i]=root[i-1];
        op=read();
        if(op==1){
            l=read(),r=read(),c[i]=read(),k=read();
            T1.updata(1,1,n,l,r,k);
            T2.updata(1,l,r,k);
            updata(root[i],1,n,l,r,k);
        }
        else if(op==2){
            l=read(),r=read(),k=read();
            T2.updata(1,l,r,-k);
            T2.Max(1,l,r,0);
        }
        else{
            x=read(),y=read();
            register ll Max=T1.qurey(1,1,n,x);
            y+=Max-T2.qurey(1,x);
            if(y>Max){
                puts("0");
                continue;
            }
            register int l=1,r=i-1,ans=0;
            while(l<=r){
                register int mid=(l+r)>>1;
                register ll t=0;
                qurey(root[mid],1,n,x,t);
                if(t>=y){
                    r=mid-1;
                    ans=mid;
                } 
                else
                  l=mid+1;
            }
            write(c[ans]);
            putchar('\n');          
        }
    }
    return 0;
}