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

· · 题解

数据结构神题……

两个log跑了2000ms我也是醉了(人傻常数大)

本题题解

题意还是比较清楚的，数轴上有一堆不同颜色的点，每个点会在一定时间出现在另一些时间消失，每次询问在某一个时间从某一个点出发需要经过多长距离才能经过所有颜色至少一次

然后我们对于这道题的思路基本上就是模拟这个过程，只是使用一些数据结构来加速我们的模拟

扫描线

首先我们先对时间轴进行类似于扫描线的处理，把一个商店拆成一个a时间插入操作和一个b时间删除操作

所以现在问题变成了，动态维护一个颜色序列，支持在某个位置插入一个颜色和删除一个颜色

问题来了我们要支持什么询问呢？

二分答案

然后我们来看询问是询问在某一个时间，一个人从某一位置出发同时向两边走，至少走多远才能经过所有的颜色各一次

当然可以迅速的想到二分答案了……

我们二分一个答案mid，于是问题转化成了，我走mid步可不可以经过所有的颜色

换句话说我们需要强制在线的支持区间查是否有所有的颜色

那么区间数颜色这个问题就是一个套路，套路的名字叫只数左边第一个点

区间数颜色

我们对于每一个颜色记pre_{i}为这个颜色左侧第一个和它同色点的位置，那么我们会发现一个点是区间[l,r]中本颜色的左侧第一个点当且仅当pre_{i}<l(可以画一个图加深理解)那么我们如果要数区间里有多少颜色只需查询[l,r]中的点有多少个点的pre值小于l即可……

然后你当然可以把二分的判定问题转化为区间中的颜色个数是否等于k这个问题

于是你用线段树套线段树去数区间的颜色了……

另外你需要注意的是同一个位置可能出现多个pre值不同的点，此时你的离散化会变的极其恶心同时边界问题基本讨论不清楚

并且此时的你的复杂度是O(nlog^3n)在n=3×10^5的时候这个数字甚至比O(n\sqrt{n})还要大……显然是要T飞的……

查找是否存在所有的颜色

所以让我们回到问题的原点——查找区间中是否存在所有的颜色 有谁告诉你我们非要知道区间里有**多少种**颜色吗？ 我们只是需要知道区间里**是否**有所有的颜色而已 仔细观察pre的含义——左边第一个和这个点同色点的位置，那么我们会发现$pre$值还告诉我们另一个非常重要的信息 **$i$到$pre_{i}$之间不存在i这种颜色** 换句话说，我们可以查找$[r+1,n]$的$pre$的区间最小值$k

这样的话根据pre值的性质,除非区间的左端点小于k，否则我们从r出发一定碰不到所有的颜色，直接说可能不是很好理解，建议这里自己画图

换句话说我们只需要查找[r+1,n]的区间pre最小值，然后和l进行比较即可确认区间中是否有所有的颜色了

这个东西当然可以使用线段树进行维护

当然我们会发现我们落下了一种情况，就是每个颜色的最右点不会被算上

单开一个set存下所有颜色的最右点坐标，然后每次取set里的最小值和区间最小值比较取二者更小的即可

那么插入和删除某一个颜色的时候它的后继的pre值将会变化为他的前驱或者它自己，查找同色前驱后继的操作可以通过开k个set暴力实现

重复值

这才是这道题最恶心的地方，我们将要处理一大堆重复值

注意一件事情是线段树上一个叶子节点里可能存着一堆pre值不同的点，当然甚至可能pre值都相同

这意味着我们不能通过简单的赋值操作来完成替换，我们需要在每一个叶子节点上单开一个multiset来处理最小值，每次修改某一位置的pre值的时候把multiset拉出来做插入删除然后重新更改一下这个叶子节点的最小值

另外就是你的离散化会非常恶心……

因为你二分的是实际距离但是线段树上的值域就是(0,n)

这导致了你需要把实际距离转成线段树上的值域

另外你查出set的前驱后继查出来的都是实际距离但是你还要转成线段树的值域

一种做法就是我**不写离散化了，把线段树换成splay

另一种就是不要拘泥于平常的离散化写法直接使用哈希表来暴力存下离散化数组

对于二分出的距离转线段树的值域可以直接暴力lower_bound然后查哈希表中的值

另外一个坑就是multiset的erase会erase全部的值，只erase一个值的正确做法是先find出一个迭代器然后erase这个迭代器

然后就是愉快的调试环节了，祝各位调试愉快~

代码仅供参考,小压了一下行，121行

上代码~

#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;const int N=3*1e5+10;const int Md=(1<<25)-1;int ans[N];int n;int m;int q;
struct hsh_map//用来离散化的哈希表 
{
    int f[N];int x[N];int v[N];int ct;int al[Md];int lsh[N];int hd;int rk[N];
    inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
    inline int& operator[](int va)//重载寻址运算符 
    {for(int i=al[va&Md];i;i=x[i])if(v[i]==va){return f[i];}add(va&Md,va);return f[ct];} 
    inline int find(int x)//二分 
    {int* p=lower_bound(lsh+1,lsh+hd+1,x);if(p!=lsh+hd+1)return this->operator [](*p);return n+1;}
    inline void ins(int x){lsh[++hd]=x;}
    inline void build()//暴力离散化 
    {
        sort(lsh+1,lsh+hd+1);
        rk[1]=1;for(int i=1;i<=hd;i++)rk[i]=lsh[i]==lsh[i-1]?rk[i-1]:i;
        for(int i=1;i<=hd;i++)this->operator [](lsh[i])=rk[i];
    }
}mp;
inline void ers(multiset <int>& s,const int& val)//multiset的erase 
{multiset <int>::iterator it=s.find(val);if(it!=s.end())s.erase(it);}
struct opt//扫描线 
{
    int ti;int tp;int k;int pos;
    friend bool operator <(opt a,opt b){return (a.ti==b.ti)?(a.tp<b.tp):(a.ti<b.ti);}
}op[3*N];int hd;
struct linetree
{
    multiset <int> s[4*N];int v[4*N];multiset <int> til;
    inline void build(int p,int l,int r)
    {
        int mid=(l+r)/2;v[p]=0x3f3f3f3f;if(r-l==1)return;
        build(p<<1,l,mid);build(p<<1|1,mid,r);
    }
    inline void ins(int p,int l,int r,const int& pos,const int& val)//插入 
    {
        if(r-l==1){s[p].insert(val);v[p]=*(s[p].begin());return;}int mid=(l+r)/2;
        if(pos<=mid)ins(p<<1,l,mid,pos,val);else ins(p<<1|1,mid,r,pos,val);
        v[p]=min(v[p<<1],v[p<<1|1]);
    }
    inline void del(int p,int l,int r,const int& pos,const int& val)//删除 
    {
        if(r-l==1){ers(s[p],val);v[p]=s[p].empty()?0x3f3f3f3f:*(s[p].begin());return;}int mid=(l+r)/2;
        if(pos<=mid)del(p<<1,l,mid,pos,val);else del(p<<1|1,mid,r,pos,val);
        v[p]=min(v[p<<1],v[p<<1|1]);
    }
    inline void modify(int p,int l,int r,const int& pos,const int& val1,const int& val2)//修改 
    {
        if(r-l==1){ers(s[p],val1);s[p].insert(val2);v[p]=*(s[p].begin());return;}int mid=(l+r)/2;
        if(pos<=mid)modify(p<<1,l,mid,pos,val1,val2);
        else modify(p<<1|1,mid,r,pos,val1,val2);v[p]=min(v[p<<1],v[p<<1|1]);
    }
    inline int query(int p,int l,int r,int dl,int dr)//区间最小值 
    {
        if(dl==l&&dr==r){return v[p];}int ret=0x3f3f3f3f;int mid=(l+r)/2;
        if(dl<mid)ret=min(ret,query(p<<1,l,mid,dl,min(dr,mid)));
        if(mid<dr)ret=min(ret,query(p<<1|1,mid,r,max(dl,mid),dr));
        return ret;
    }
    inline void imd(const int& v){til.insert(v);}//单开的set的操作 
    inline void pmd(const int& v){ers(til,v);}
    inline int cquery(int r){if(r==n+1)return *(til.begin());//判一下是否越界 
    return min(*(til.begin()),query(1,0,n,r-1,n));}
}lt;multiset <int> col[N];int cnt;
inline void ins(int pos,int k)//更改pre值的插入，分4种情况讨论有无前驱后继 
{
    multiset <int>::iterator it,it1,it2;if(col[k].empty())cnt++;it=col[k].insert(pos);
    if(it!=--col[k].end()) 
    {
        int pre=-0x3f3f3f3f;it2=it;++it2;if(it!=col[k].begin()){it1=it;--it1;pre=*it1;}
        lt.modify(1,0,n,mp[*it2],pre,*it);lt.ins(1,0,n,mp[*it],pre);
    }else 
    {
        int pre=-0x3f3f3f3f;if(it!=col[k].begin()){it1=it;--it1;pre=*it1;}
        lt.ins(1,0,n,mp[*it],pre);lt.pmd(pre);lt.imd(*it);
    }
}
inline void del(int pos,int k)//同理删除的时候，分4种情况讨论有无前驱后继 
{
    multiset <int>::iterator it,it1,it2;it=col[k].find(pos);
    if(it!=--col[k].end())
    {
        int pre=-0x3f3f3f3f;it2=it;++it2;if(it!=col[k].begin()){it1=it;--it1;pre=*it1;}
        lt.modify(1,0,n,mp[*it2],*it,pre);lt.del(1,0,n,mp[*it],pre);
    }else 
    {
        int pre=-0x3f3f3f3f;if(it!=col[k].begin()){it1=it;--it1;pre=*it1;}
        lt.del(1,0,n,mp[*it],pre);lt.pmd(*it);lt.imd(pre);
    }ers(col[k],pos);if(col[k].empty())cnt--;
}
inline int query(int pos)//二分答案 
{
    if(cnt!=m)return -1;int l=0;int r=1e8+10;
    while(l!=r)
    {
        int mid=(l+r)/2;int mi=lt.cquery(mp.find(pos+mid+1));
        if(mi<pos-mid)l=mid+1;else r=mid;
    }return l;
}
int main()
{ 
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1,ti1,ti3,pos,col;i<=n;i++)
    {
        scanf("%d%d%d%d",&pos,&col,&ti1,&ti3);mp.ins(pos);
        op[++hd]=(opt){ti1,1,col,pos};op[++hd]=(opt){ti3,3,col,pos};
    }mp.build();
    for(int i=1,ti,pos;i<=q;i++){scanf("%d%d",&pos,&ti);op[++hd]=(opt){ti,2,i,pos};}
    sort(op+1,op+hd+1);lt.build(1,0,n);
    for(int i=1;i<=hd;i++)
    {
        switch(op[i].tp)
        {
            case 1:{ins(op[i].pos,op[i].k);break;}
            case 2:{ans[op[i].k]=query(op[i].pos);break;}
            case 3:{del(op[i].pos,op[i].k);break;}
        }
    }for(int i=1;i<=q;i++)printf("%d\n",ans[i]);return 0;//拜拜程序~ 
}