CF1741F

shinkuu · 2023-05-13 14:10:15 · 题解

为啥现在的题解都感觉这么复杂。我来个容易理解的。

维护一个序列 a，表示当前点被几个线段覆盖。如果当前选出了颜色 x，那么 \forall i,c_i=x，[l_i,r_i] 内所有 a_i\leftarrow a_i-1。这样就只有 c_i\not=x 的 i 会产生贡献了。此时只要找到最近的一个 a_i>0，即为答案位置。线段树上二分维护。

再特判一下线段有交集，就是简单区间查询。

最后发现 1\leq l_i\leq r_i\leq 10^9。离散化一下即可。

code：

int n,m,d[N],L[N],R[N],c[N],ans[N];
vector<int> col[N];
ll tr[N<<2],tag[N<<2];
inline void pushup(int o){
    tr[o]=tr[o<<1]+tr[o<<1|1];
}
inline void pushdown(int l,int r,int o){
    int mid=(l+r)>>1;
    tr[o<<1]+=(mid-l+1)*tag[o],tr[o<<1|1]+=(r-mid)*tag[o];
    tag[o<<1]+=tag[o],tag[o<<1|1]+=tag[o];
    tag[o]=0;
}
void update(int l,int r,int o,int x,int y,int k){
    if(l>=x&&r<=y){
        tr[o]+=(r-l+1)*k;
        tag[o]+=k;
        return;
    }
    pushdown(l,r,o);
    int mid=(l+r)>>1;
    if(x<=mid)
        update(l,mid,o<<1,x,y,k);
    if(y>mid)
        update(mid+1,r,o<<1|1,x,y,k);
    pushup(o);
}
bool query(int l,int r,int o,int x,int y){
    if(l>=x&&r<=y)
        return tr[o];
    pushdown(l,r,o);
    int mid=(l+r)>>1;
    if(x<=mid&&y>mid)
        return query(l,mid,o<<1,x,y)|query(mid+1,r,o<<1|1,x,y);
    if(x<=mid)
        return query(l,mid,o<<1,x,y);
    return query(mid+1,r,o<<1|1,x,y);
}
int query_l(int l,int r,int o,int x){
    if(l>x||!tr[o])
        return 0;
    if(l==r){
        if(tr[o])
            return l;
        return 0;
    }
    pushdown(l,r,o);
    int mid=(l+r)>>1;
    if(x>mid){
        int ret=query_l(mid+1,r,o<<1|1,x);
        if(ret>=1)
            return ret;
    }
    return query_l(l,mid,o<<1,x);
}
int query_r(int l,int r,int o,int x){
    if(r<x||!tr[o])
        return m+1;
    if(l==r){
        if(tr[o])
            return l;
        return m+1;
    }
    pushdown(l,r,o);
    int mid=(l+r)>>1;
    if(x<=mid){
        int ret=query_r(l,mid,o<<1,x);
        if(ret<=m)
            return ret;
    }
    return query_r(mid+1,r,o<<1|1,x);
}
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        col[i].clear();
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&L[i],&R[i],&c[i]);
        d[i]=L[i],d[i+n]=R[i];
        col[c[i]].eb(i);
    }
    sort(d+1,d+n*2+1);
    m=unique(d+1,d+n*2+1)-d-1;
    for(int i=1;i<=m*4;i++)
        tr[i]=tag[i]=0;
    for(int i=1;i<=n;i++){
        L[i]=lower_bound(d+1,d+m+1,L[i])-d;
        R[i]=lower_bound(d+1,d+m+1,R[i])-d;
        update(1,m,1,L[i],R[i],1);
    }
    d[0]=-inf,d[m+1]=inf;
    for(int i=1;i<=n;i++){
        for(int j:col[i])
            update(1,m,1,L[j],R[j],-1);
        for(int j:col[i]){
            if(query(1,m,1,L[j],R[j]))
                ans[j]=0;
            else{
                int pl=query_l(1,m,1,L[j]),pr=query_r(1,m,1,R[j]);
                ans[j]=min(1ll*d[L[j]]-d[pl],1ll*d[pr]-d[R[j]]);
            }
        }
        for(int j:col[i])
            update(1,m,1,L[j],R[j],1);
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    puts("");
}
signed main(){
//  freopen("ex_data1.in","r",stdin);
    int t=1;
        scanf("%d",&t);
    while(t--)
        solve();
}