[JOISC 2021 Day1] フードコート题解

KingPowers · 2023-08-24 11:55:21 · 题解

题目链接

从去 ZR 第二天起就留下的坑，今天算是给填完了。

个人实现不易，点个赞吧（悲。

提前约定：下文视 n,m,q 同阶。

注意到离开事件是个很烦人的东西，我们不妨先思考下该如何先将它处理掉。

对于每个食品店，我们不妨维护两个东西：总共加入过的人数和当前的人数。对于总共加入的人数，我们相当于是要在每次加入操作时支持一个区间加，线段树可以轻松解决。那么当前的人数又该如何维护呢？

记当前第 i 个食品店的人数为 a_i，不难发现，离开操作的实质其实是 a_i\leftarrow\max(a_i-k,0),i\in[l,r]。注意到这题是单点查询，所以完全没必要写吉司机线段树。想起来高爸当时讲了一个比较精妙的维护一个二元标记的方法，但是现在记得不太清楚了，于是我沿用了这一道题的做法，暴力维护加法标记和 \max 标记，然后将每次离开事件拆成区间减 k、区间对 0 取 \max 两步。

维护这两个东西有什么用呢？我们记 del_i 表示第 i 个食品店已经离开了多少人，不难发现 del_i 其实就是总人数与当前人数之差，而对于一个白嫖事件 (A,B)，我们可以将其转化为：不考虑离开事件的前提下，食品店 A 的第 B+del_i 个人是谁。

这样，我们就成功地找到了离开事件的处理方法，现在只需要考虑性质 C 怎么做就可以了。

现在我们解决问题的思路很明了了：对于每个白嫖事件，我们只要找出第一个使食品店 A 的加入过的总人数大于等于 B+del_i 的修改操作，这次修改操作加入的人就是我们要的答案。使用整体二分或者树套树之类的东西大概可以直接 O(n\log^2n) 解决掉，但其实没必要。

不妨考虑离线。对于每个白嫖事件，我们直接把它先挂到对应食品店的 vector 上；对于每个加入事件，我们将它差分一下：相当于是第 l 个食品店在 [i,q] 时间段内总人数多了 k，第 r+1 个食品店在 [i,q] 时间段内总人数少了 k，同样挂到对应 vector 上处理。然后直接再开一棵线段树，维护每个时间点内某个食品店的总人数，直接扫描线扫过每个食品店，每次询问在线段树上二分即可。

上面这一段可能有点抽象，结合代码应该会好理解很多。

最后理一遍思路：

用一棵支持区间加、单点查询的线段树维护每个食品店的总共加入过的人数。
用一棵支持区间加、区间取 \max 的线段树维护每个食品店当前的人数。
将修改和询问操作离线，用一棵支持区间加、查询第一个大于等于某数的位置（可以线段树上二分）的线段树维护每个食堂在每个时间点的总人数。

注意：以上三棵线段树在代码中分别对应 T_1,T_3,T_2。

时间复杂度：O(n\log n)。

代码大概 4.5k，也不是很长。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define Mp make_pair
#define pb emplace_back
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e9;
int n,m,q,c[N],ans[N];
bool lmt[N];
vector<pii>cha[N],que[N];
struct Segment_Tree1{
    #define ls now<<1
    #define rs now<<1|1
    int mx[N],tag[N];
    void pushup(int now){mx[now]=max(mx[ls],mx[rs]);};
    void pushdown(int now){
        if(tag[now]){
            mx[ls]+=tag[now];tag[ls]+=tag[now];
            mx[rs]+=tag[now];tag[rs]+=tag[now];
            tag[now]=0;
        }
    }
    void modify_add(int x,int y,int k,int l,int r,int now){
        if(x<=l&&r<=y){
            mx[now]+=k;tag[now]+=k;
            return;
        }
        pushdown(now);
        int mid=(l+r)>>1;
        if(x<=mid) modify_add(x,y,k,l,mid,ls);
        if(y>mid) modify_add(x,y,k,mid+1,r,rs);
        pushup(now);
    }
    int query(int pos,int l,int r,int now){
        if(l==r) return mx[now];
        pushdown(now);
        int mid=(l+r)>>1;
        if(pos<=mid) return query(pos,l,mid,ls);
        return query(pos,mid+1,r,rs);
    }
    int find(int k,int l,int r,int now){
        if(mx[now]<k) return 0;
        if(l==r) return l;
        pushdown(now);
        int mid=(l+r)>>1;
        if(mx[ls]>=k) return find(k,l,mid,ls);
        return find(k,mid+1,r,rs);
    }
    #undef ls
    #undef rs
}T1,T2;
struct Segment_Tree2{
    #define ls now<<1
    #define rs now<<1|1
    int mx[N],tag1[N],tag2[N];
    void pushup(int now){mx[now]=max(mx[ls],mx[rs]);};
    void pushdown(int now){
        if(tag1[now]){
            mx[ls]+=tag1[now];mx[rs]+=tag1[now];
            tag1[ls]+=tag1[now];tag1[rs]+=tag1[now];
            if(tag2[ls]!=-inf) tag2[ls]+=tag1[now];
            if(tag2[rs]!=-inf) tag2[rs]+=tag1[now];
            tag1[now]=0;
        }
        if(tag2[now]!=-inf){
            mx[ls]=max(mx[ls],tag2[now]);mx[rs]=max(mx[rs],tag2[now]);
            tag2[ls]=max(tag2[ls],tag2[now]);tag2[rs]=max(tag2[rs],tag2[now]);
            tag2[now]=-inf;
        }
    }
    void build(int l,int r,int now){
        tag1[now]=0;tag2[now]=-inf;
        if(l==r) return mx[now]=0,void();
        int mid=(l+r)>>1;
        build(l,mid,ls);build(mid+1,r,rs);
        pushup(now);
    }
    void modify_add(int x,int y,int k,int l,int r,int now){
        if(x<=l&&r<=y){
            mx[now]+=k;tag1[now]+=k;
            if(tag2[now]!=-inf) tag2[now]+=k;
            return;
        }
        pushdown(now);
        int mid=(l+r)>>1;
        if(x<=mid) modify_add(x,y,k,l,mid,ls);
        if(y>mid) modify_add(x,y,k,mid+1,r,rs);
        pushup(now);
    }
    void modify_max(int x,int y,int k,int l,int r,int now){
        if(x<=l&&r<=y){
            mx[now]=max(mx[now],k);
            tag2[now]=max(tag2[now],k);
            return;
        }
        pushdown(now);
        int mid=(l+r)>>1;
        if(x<=mid) modify_max(x,y,k,l,mid,ls);
        if(y>mid) modify_max(x,y,k,mid+1,r,rs);
        pushup(now);
    }
    int query(int pos,int l,int r,int now){
        if(l==r) return mx[now];
        pushdown(now);
        int mid=(l+r)>>1;
        if(pos<=mid) return query(pos,l,mid,ls);
        return query(pos,mid+1,r,rs);
    }
    #undef ls
    #undef rs
}T3;
void Main(){
    cin>>n>>m>>q;
    T3.build(1,n,1);
    For(i,1,q){
        int opt,l,r,k,a,b;
        cin>>opt;
        if(opt==1){
            cin>>l>>r>>c[i]>>k;
            T1.modify_add(l,r,k,1,n,1);
            T3.modify_add(l,r,k,1,n,1);
            cha[l].pb(i,k);cha[r+1].pb(i,-k);
        }
        else if(opt==2){
            cin>>l>>r>>k;
            T3.modify_add(l,r,-k,1,n,1);
            T3.modify_max(l,r,0,1,n,1);
        }
        else{
            cin>>a>>b;lmt[i]=1;
            que[a].pb(i,b+T1.query(a,1,n,1)-T3.query(a,1,n,1));
        }
    }
    For(i,1,n){
        for(pii x:cha[i]) T2.modify_add(x.fi,q,x.se,1,q,1);
        for(pii x:que[i]) ans[x.fi]=T2.find(x.se,1,q,1);
    }
    For(i,1,q) if(lmt[i]){
        if(ans[i]>i) cout<<0<<'\n';
        else cout<<c[ans[i]]<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;//cin>>T;
    while(T--) Main();
    return 0;
}

[JOISC 2021 Day1] フードコート 题解

[JOISC 2021 Day1] フードコート题解