P12664 [KOI 2023 Round 2] 烤肉派对题解

· · 题解

首先，我们发现在线去找每个人能够拿到和掉在地上的烤肉比较难实现，所以我们可以把每个询问离线下来，然后枚举所有的烤肉，把每一块烤肉分给某个人。

对于第 i 块烤肉，我们需要找出一个人，使这个人的任意一个签子与这块肉产生交集，且这个人在所有签子与这块肉产生交集的人中访问时间最早。

我们先把 a 数组与 b 数组分别从小到大排序，当我们枚举到第 i 块烤肉时，我们分别二分出 a 数组和 b 数组第一个大于等于 s_i 且 小于 e_i 的位置，这样我们对于 a 数组和 b 数组分别得到两个区间，紧接着我们求出这两个区间中编号（指排队领肉的顺序）最小的数的编号就是这块肉被谁叉走的，最后我们再判断一下这个人能不能叉走这块肉就行。

代码：


#include<cstdio>
#include<algorithm>
#include<cmath>
#define min(a,b) (a<b?a:b)
#define int long long
using namespace std;
const int N=3e5+10;
struct Node{
    int val,id;
    bool operator<(const Node &x)const{
        return val<x.val;
    }
}a[N],b[N];
int s[N],e[N],w[N],ans[N],sl1[N],sl2[N],st1[N][20],st2[N][20],n,m;
void init(int (&st)[N][20]){
    for(int j=1;(1<<j)<=m;j++){
        for(int i=1;i<=m-(1<<j)+1;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
}
int query(int l,int r,int (&st)[N][20]){
    if(l>r) swap(l,r);
    int k=log2(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&s[i],&e[i],&w[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&a[i].val,&b[i].val);
        a[i].id=b[i].id=i;
    }
    sort(a+1,a+m+1);
    sort(b+1,b+m+1);
    for(int i=1;i<=m;i++){
        st1[i][0]=a[i].id;
        st2[i][0]=b[i].id;
        sl1[a[i].id]=i;
        sl2[b[i].id]=i;
    }
    init(st1);
    init(st2);
    for(int i=1;i<=n;i++){
        if(s[i]>e[i]) swap(s[i],e[i]);
        int l=1,r=m,res1=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(s[i]<=a[mid].val&&a[mid].val+1<=e[i]){
                res1=mid;
                r=mid-1;
            }else if(a[mid].val<s[i]){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        l=1,r=m;
        int res2=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(s[i]<=a[mid].val&&a[mid].val+1<=e[i]){
                res2=mid;
                l=mid+1;
            }else if(a[mid].val<s[i]){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        l=1,r=m;
        int ret1=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(s[i]<=b[mid].val&&b[mid].val+1<=e[i]){
                ret1=mid;
                r=mid-1;
            }else if(b[mid].val<s[i]){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        l=1,r=m;
        int ret2=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(s[i]<=b[mid].val&&b[mid].val+1<=e[i]){
                ret2=mid;
                l=mid+1;
            }else if(b[mid].val<s[i]){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        int t=0x7f7f7f7f;
        int flag=0;
        if(~res1) t=query(res1,res2,st1),flag=1;
        if(~ret1){
            int h=query(ret1,ret2,st2);
            if(h<t){
                t=h;
                flag=2;
            }
        }
        if(t!=0x7f7f7f7f){
            int le=a[sl1[t]].val,ri=b[sl2[t]].val;
            if(le+1>s[i]&&ri+1<=e[i]){
                ans[t]+=w[i];
            }
        }
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}