题解 P4632 【[APIO2018] New Home 新家】

xtx1092515503 · 2020-11-28 18:35:08 · 题解

安利可爱的平衡树解法。

首先先说正解。

应该很容易想到可以把询问离线下来跑扫描线，这样我们就对每个询问维护了此时所有尚在开业的商店的类型及位置。

然后，我们是否有方法求出所有颜色离当前位置最近的商店中最远的一个呢？

“最近的最远”，很容易想到二分。于是我们二分区间长度。则问题转换为能否判断一个区间 [l,r] 中是否存在所有颜色。

这是经典主席树问题，思想是对于每个商店 i，维护其左方第一个尚在开业的同色商店 pre_i（不存在则置为 0），随后我们只需要考虑 pre_i<l 的所有商店，即区间中每种颜色第一个出现的位置。

但是如果使用主席树复杂度是非常不可爱的 O(n\log^3n)。当然，如果把外层的二分换成直接在主席树上二分也能把复杂度优化到 O(n\log^2n)，还是有跑过去的希望的。但是我们还有更好的解法。

因为我们要求的不是区间中不同颜色的数目，而是区间中有无出现所有的颜色，是一个存在性问题而非计数问题。这使得我们可以忽略一些信息。

我们仍然考虑上述解法。只不过，我们这时找出所有 i\in(r,+\infty) 的商店中，pre_i 的最小值。明显，如果此时有 \min<l，则 \min 所属的此种颜色并没有在区间中出现，也就无法达成所有颜色全数出现的要求了。

但是，我们会发现，上述解法中每种颜色最右端的商店都不会被考虑到。于是我们另外用点什么东西维护每种颜色最右端的商店，然后将上述的 \min 与这里最右端的商店中最左端的哪一个再取 \min，即可找到上述位置，然后直接与 l 比较即可。

明显这一切都可以使用线段树维护。但是我们发现它有两个缺陷：

线段树必须离散化，但离散化后就不好二分了。
线段树中每个位置上都可能有不止一家商店，所以必须在里面再套一个multiset加以维护。

虽然这两个问题都是可以被处理掉的，但是我不想烦那么多了，就简单写了棵平衡树维护。明显此时就可以不在每个位置上开multiset（平衡树支持键值相同的数存在），也不必离散化了。

然后，无论是线段树还是平衡树，都可以通过在上面直接二分来规避掉外层的那个二分，从而将复杂度优化到 O(n\log n)。

但是反正我外层套了二分也过去了（并且甚至跑进了1s以内），也就懒得再改成平衡树上二分了。所以此处代码是 O(n\log^2n) 的。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int SHO;
struct Shops{
    int tim,pos,tp;
    Shops(int u=0,int v=0,int w=0){tim=u,pos=v,tp=w;}
    friend bool operator<(const Shops &x,const Shops &y){return x.tim<y.tim;}
}sho[600100];
struct Queries{
    int tim,pos,id;
    friend bool operator<(const Queries &x,const Queries &y){return x.tim<y.tim;}
}que[300100];
int res[300100];
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int cnt,rt;
struct Treap{
    int ch[2],rd,pos,pre,mn,sz;
}t[1000100];
void pushup(int x){
    t[x].mn=t[x].pre,t[x].sz=1;
    if(lson)t[x].mn=min(t[lson].mn,t[x].mn),t[x].sz+=t[lson].sz;
    if(rson)t[x].mn=min(t[rson].mn,t[x].mn),t[x].sz+=t[rson].sz;
}
int newnode(int pos,int pre){
    int x=++cnt;
    t[x].rd=rand()*rand();
    t[x].pos=pos;
    t[x].pre=pre;
    pushup(x);
    return x;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rd>t[y].rd){t[x].ch[1]=merge(t[x].ch[1],y),pushup(x);return x;}
    else{t[y].ch[0]=merge(x,t[y].ch[0]),pushup(y);return y;}
}
void splitbyval(int x,int pos,int pre,int &u,int &v){
    if(!x){u=v=0;return;}
    if(t[x].pos<pos||t[x].pos==pos&&t[x].pre<pre)u=x,splitbyval(rson,pos,pre,rson,v);
    else v=x,splitbyval(lson,pos,pre,u,lson);
    pushup(x);
}
void splitbysize(int x,int k,int &u,int &v){
    if(!x){u=v=0;return;}
    if(t[lson].sz>=k)v=x,splitbysize(lson,k,u,lson);
    else u=x,splitbysize(rson,k-t[lson].sz-1,rson,v);
    pushup(x);
}
void Insert(int pos,int pre){
    int a,b;
    splitbyval(rt,pos,pre,a,b);
    rt=merge(merge(a,newnode(pos,pre)),b);
}
void Delete(int pos,int pre){
    int a,b,c;
    splitbyval(rt,pos,pre,a,b);
    splitbysize(b,1,b,c);
    rt=merge(a,c);
}
multiset<int>typ[300100],all;
#define ERASE(x,y) x.erase(x.find(y))
void Ins(int col,int pos){
    auto it=typ[col].lower_bound(pos),ti=it;
    int pre=*--it;
    Insert(pos,pre);
    if(ti!=typ[col].end()){
        int nex=*ti;
        Delete(nex,pre);
        Insert(nex,pos);
    }
    ERASE(all,*typ[col].rbegin());
    typ[col].insert(pos);
    all.insert(*typ[col].rbegin());
}
void Del(int col,int pos){
    ERASE(all,*typ[col].rbegin());
    ERASE(typ[col],pos);
    all.insert(*typ[col].rbegin());
    auto it=typ[col].lower_bound(pos),ti=it;
    int pre=*--it;
    Delete(pos,pre);
    if(ti!=typ[col].end()){
        int nex=*ti;
        Delete(nex,pos);
        Insert(nex,pre);
    }
}
bool che(int l,int r){
    l=max(l,1);
    int a,b;
    splitbyval(rt,r,0x3f3f3f3f,a,b);
    bool ret=t[b].mn>=l;
    rt=merge(a,b);
    return ret;
}
int Query(int pos){
    if(*all.begin()==0)return -1;
    int l=max(pos-*all.begin(),0),r=max(l,*all.rbegin()-pos);
    while(l<r){
        int mid=(l+r)>>1;
        if(che(pos-mid,pos+mid))r=mid;
        else l=mid+1;
    }
    return r;
}
void Iterate(int x){if(x)Iterate(lson),printf("(%d,%d)",t[x].pos,t[x].pre),Iterate(rson);}
int main(){
    scanf("%d%d%d",&n,&m,&q),t[0].mn=0x3f3f3f3f;
    for(int i=1;i<=m;i++)typ[i].insert(0),all.insert(0);
    for(int i=1,a,b,c,d;i<=n;i++)scanf("%d%d%d%d",&a,&b,&c,&d),sho[++SHO]=Shops(c,a,b),sho[++SHO]=Shops(d+1,a,-b);
    sort(sho+1,sho+SHO+1);
    for(int i=1;i<=q;i++)scanf("%d%d",&que[i].pos,&que[i].tim),que[i].id=i;
    sort(que+1,que+q+1);
    for(int i=1,j=1;i<=q;i++){
        while(j<=SHO&&sho[j].tim<=que[i].tim){
            if(sho[j].tp>0)Ins(sho[j].tp,sho[j].pos);
            else Del(-sho[j].tp,sho[j].pos);
            j++;
        }
//      for(int k=1;k<=m;k++,puts(""))for(auto it:typ[k])printf("%d ",it);Iterate(rt),puts("");
        res[que[i].id]=Query(que[i].pos);
    }
    for(int i=1;i<=q;i++)printf("%d\n",res[i]);
    return 0;
}