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

· · 题解

首先考虑可以用二分答案来解决询问，可以二分一个长度len，若在区间[x-len,x+len]内包含了所有k种的商店，那么这个len就是合法的，可以通过二分来求其最小值。

对每个商店的存在时间转化为在a时刻出现，在b+1时刻消失，然后和询问一起离线按时间排序，就可以解决时间这一维的限制了。

然后考虑如何快速查询区间内是否包含所有的商店，和支持维护商店的出现消失。

对于这种区间数颜色的问题，可以对每个位置记录与其商店类型相同的上一个位置pre，发现一个位置上可能会有多个商店，那么这里的pre改为记录这些商店的到其各自商店类型相同的上一个位置的最小值。

然后就是如何支持维护$pre$，对于每个位置开一个$multiset$维护该位置所有商店的对应其商店类型的前驱，$multiset$中的最小值即为该位置的$pre$，然后用线段树动态开点来维护区间$pre$的最小值，这里其实就是在线段树的每个叶子节点开了一个$multiset$来维护信息。 对于商店的出现消失维护，对每种商店类型开一个$multiset$，维护该类型所有商店的出现位置，然后出现和消失只用解决对于该位置同类型的前驱和后继的影响就行，线段树单点修改即可实现。 若用线段树查询最小值来判定二分，复杂度是$O(n\ log^2\ n)$的，可以直接在线段树上二分位置，复杂度就是$O(n\ log\ n)$的了。 细节挺多，具体实现就看代码吧。 $code: 
#include<bits/stdc++.h>
#define maxn 900010
#define all 200000000
#define mid ((l+r)>>1)
using namespace std;
typedef multiset<int>::iterator muli;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,k,q,tot,root,tree_cnt,num;
int mi[maxn*20],ls[maxn*20],rs[maxn*20],ans[maxn];
multiset<int> p[maxn],s[maxn*20];
struct node
{
    int pos,tim,id,opt;
}t[maxn];
bool cmp(const node &a,const node &b)
{
    if(a.tim==b.tim) return a.opt<b.opt;
    return a.tim<b.tim;
}
void modify(int l,int r,int pos,int v,int type,int &cur)
{
    if(!cur) cur=++tree_cnt;
    if(l==r)
    {
        if(type) s[cur].insert(v);
        else s[cur].erase(s[cur].find(v));
        if(!s[cur].empty()) mi[cur]=*s[cur].begin();
        else mi[cur]=all;
        return;
    }
    if(pos<=mid) modify(l,mid,pos,v,type,ls[cur]);
    else modify(mid+1,r,pos,v,type,rs[cur]);
    mi[cur]=min(mi[ls[cur]],mi[rs[cur]]);
}
int query(int pos)
{
    if(num<k) return -1;
    int l=1,r=all,cur=root,midmi,rmi=all;
    while(l<r)
    {
        midmi=min(rmi,mi[rs[cur]]);
        if(pos>mid||midmi<2*pos-mid) cur=rs[cur],l=mid+1;
        else rmi=midmi,cur=ls[cur],r=mid;
    }
    return l-pos;
}
int main()
{
    read(n),read(k),read(q),mi[0]=all;
    for(int i=1;i<=k;++i)
    {
        p[i].insert(-all),p[i].insert(all);
        modify(1,all,all,-all,1,root);
    }
    for(int i=1;i<=n;++i)
    {
        int x,id,a,b;
        read(x),read(id),read(a),read(b);
        t[++tot]=(node){x,a,id,1};
        t[++tot]=(node){x,b+1,id,0};
    }
    for(int i=1;i<=q;++i)
    {
        int pos,tim;
        read(pos),read(tim);
        t[++tot]=(node){pos,tim,i,2};
    }
    sort(t+1,t+tot+1,cmp);
    for(int i=1;i<=tot;++i)
    {
        int opt=t[i].opt,id=t[i].id,pos=t[i].pos;
        muli a,b;
        if(opt==0)
        {
            a=b=p[id].lower_bound(pos),a--,b++;
            modify(1,all,*b,pos,0,root);
            modify(1,all,*b,*a,1,root);
            modify(1,all,pos,*a,0,root);
            if(p[id].size()==3) num--;
            p[id].erase(p[id].find(pos));
        }
        if(opt==1)
        {
            a=b=p[id].lower_bound(pos),a--;
            modify(1,all,*b,pos,1,root);
            modify(1,all,*b,*a,0,root);
            modify(1,all,pos,*a,1,root);
            if(p[id].size()==2) num++;
            p[id].insert(pos);
        }
        if(opt==2) ans[id]=query(pos);
    }
    for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
    return 0;
}