Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P6349 【[PA2011]Kangaroos】

posted on 2020-05-14 01:14:04 | under 题解 |

朴实无华,但快乐的O($n\sqrt{n}$)莫队。

显然这题的询问需要的信息是很难快速合并的,我们可以考虑使用莫队优化暴力

然后我们可以毫不费力的设计出一个O($n\sqrt{nlogn}$)的莫队,即按照莫队的循序处理询问,同时使用线段树在边界移动时维护最长连续段。

但是log数据结构和根号算法八字不合,我们考虑一下有什么办法搞掉这个log。

虽然你写个带log的卡卡常一样能过就是很危险。


我们思考,具体什么操作需要依靠线段树维护的信息来处理。

这里操作很显然只有两个,就是添加和删除。

同样很显然的是,添加完全不需要分治操作,因为我们只询问全局最长连续段,而不关心某个位置所属的连续段长度。我们只需要在一个连续段的左右两端记录其长度,合并的时候更新即可。

那我们的问题就来到删除了,显然按照上面的处理方式,删除是困难的,因为我们不知道当前位置所处的连续段两边在哪,也就没法快速分裂一个连续段。

信息易添加,难删除回滚莫队的标志特征。

我们使用一个可回退化数组处理上面的插入操作即可,每次处理询问先定位右端点r,再把l从所属块右端点移动到询问的位置,记录答案,回滚左端点l即可。

一般的可回退化数据结构允许撤销任意次修改,但这里没必要实现一个通用的可回退化数组。显然我们每次回滚都是回滚到一个特定的版本。我们只需要对于左端点移动产生的操作,记录影响的点和影响前的值,回滚时根据记录的受影响点,直接用影响前的值覆盖回去即可。


要注意几点:

  1. 回滚莫队不能处理两端点在同一块中的询问,这些询问要按所属块放到一起处理。显然包含当前块的区间一定包含其中的询问,我们扫出这些区间,剩下的区间只会是端点在当前块中的,每个询问扫一下当前块,使用另一个可回退化数组维护即可。
  2. 莫队只能处理出两端点至少一个在询问区间内的区间,对于包含询问区间的区间,显然包含当前询问所属块的右端点(注意不一定包含整个块)(不跨块的我们在上面按块分组一起暴力),同样先预处理再做莫队。
  3. 换块处理时候别忘了清空数组和答案,回滚时候别忘了回滚答案。

常数不大,甚至用了vector依旧跑的飞快。快乐rk1。建议改为:香 港 记 者 提交

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <cmath>
using namespace std;
const int kmaxn=200000+5;
struct Array
{
    int a[kmaxn];
    int vis[kmaxn];
    int rv[kmaxn];
    int t[kmaxn],st;
    inline const int operator[](const int i)const
    {
        return a[i];
    }
    inline void mod(int x,int v)
    {
        if(vis[x])
            a[x]=v;
        else
        {
            t[++st]=x;
            vis[x]=1;
            rv[x]=a[x];
            a[x]=v;
        }
    }
    inline void set(int x,int v)
    {
        a[x]=v;
    }
    void cancel_all()
    {
        int tp;
        while(st)
        {
            tp=t[st--];
            a[tp]=rv[tp];
            vis[tp]=0;
        }
    }
    void clear(int n)
    {
        for(int i=1;i<=n;++i)
            a[i]=rv[i]=vis[i];
        st=0;
    }
};
typedef pair<int,int> PR;
Array tb1,tb2;
PR a[kmaxn];
PR seg[kmaxn];
vector<PR> ask[kmaxn];
int trs[kmaxn];
int LE[kmaxn];
int n,m,bs;
inline int BK(int i){return (i-1)/bs+1;}
inline int BR(int i){return min(i*bs,n);}
inline int BL(int i){return BR(i-1)+1;}
inline int TL(int x)
{
    return lower_bound(trs+1,trs+1+n,x)-trs;
}
inline int TR(int x)
{
    return upper_bound(trs+1,trs+1+n,x)-trs-1;
}
int res1,res2,ans[kmaxn];
void add1(int x,Array& tb,int &res)
{
    if(tb[x]!=0)return;
    int dl,dr,len;
    dl=tb[x-1];
    dr=tb[x+1];
    len=dl+dr+1;
    tb.set(x-dl,len);
    tb.set(x+dr,len);
    tb.set(x,len);
    res=max(len,res);
}
void add2(int x,Array& tb,int &res)
{
    if(tb[x]!=0)return;
    int dl,dr,len;
    dl=tb[x-1];
    dr=tb[x+1];
    len=dl+dr+1;
    tb.mod(x-dl,len);
    tb.mod(x+dr,len);
    tb.mod(x,len);
    res=max(len,res);
}
int nb;
bool ck(int k,int l,int r)
{
    int tl=seg[k].first,tr=seg[k].second;
    return !(tr<l||tl>r);
}
int brute(int b,int l,int r)
{
    int k=n/2,tl=BL(b),tr=BR(b);
    if(nb!=b)
    {
        nb=b;   
        tb2.clear(n);
        res2=0;
        for(int i=1;i<=k;++i)
        {
            if(seg[i].first<tl&&seg[i].second>tr)
                add1(i,tb2,res2);
        }
    }
    int tres=res2,p=0;
    for(int i=tl;i<=tr;++i)
    {
        p=a[i].second;
        if(ck(p,l,r))
            add2(p,tb2,res2);
    }
    swap(tres,res2);
    tb2.cancel_all();
    return tres;
}
void solve(int b)
{
    int l,r,tl,tr,tres,k;//[l,r),[tl,tr]
    tb1.clear(n/2);
    res1=0;
    l=r=k=BR(b);
    for(int i=n/2;i>0;--i)
    {
        if(ck(i,r,r))
            add1(i,tb1,res1);
    }
    for(auto p:ask[b])
    {
        tl=LE[p.second];
        tr=p.first;
        if(tr<=k)
        {
            ans[p.second]=brute(b,tl,tr);
            continue;
        }
        while(r<=tr)
            add1(a[r++].second,tb1,res1);
        tres=res1;
        while(l>tl)
            add2(a[--l].second,tb1,res1);
        ans[p.second]=res1;
        tb1.cancel_all();
        res1=tres;
        l=k;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>seg[i].first>>seg[i].second;
        a[i].first=trs[i]=seg[i].first;
        a[i+n].first=trs[i+n]=seg[i].second;
        a[i].second=a[i+n].second=i;
    }
    n*=2;
    bs=sqrt(n);
    sort(trs+1,trs+1+n);
    sort(a+1,a+1+n);
    PR tp;
    for(int i=n/2;i>0;--i)
    {
        seg[i].first=TL(seg[i].first);
        seg[i].second=TR(seg[i].second);
    }
    for(int i=1;i<=m;++i)
    {
        cin>>LE[i]>>tp.first;
        LE[i]=TL(LE[i]);
        tp.first=TR(tp.first);
        tp.second=i;
        ask[BK(LE[i])].push_back(tp);
    }
    for(int i=1;BL(i)<=n;++i)
    {
        if(ask[i].empty())continue;
        sort(ask[i].begin(),ask[i].end());
        solve(i);
    }
    for(int i=1;i<=m;++i)
        cout<<ans[i]<<'\n';
    return 0;
}

为什么会有学弟搞出k-d树这种神仙做法????

强的离谱,i了i了。