题解 P6349 【[PA2011]Kangaroos】
_虹_
2020-05-14 01:14:04
## **朴实无华，但快乐的O($n\sqrt{n}$)莫队。**
显然这题的询问需要的信息是很难快速合并的，我们可以考虑使用莫队**优化暴力**。
然后我们可以毫不费力的设计出一个O($n\sqrt{nlogn}$)的莫队，即按照莫队的循序处理询问，同时使用线段树在边界移动时维护最长连续段。
但是log数据结构和根号算法八字不合，我们考虑一下有什么办法搞掉这个log。
~~虽然你写个带log的卡卡常一样能过就是很危险。~~
------------
我们思考，具体什么操作需要依靠线段树维护的信息来处理。
这里操作很显然只有两个，就是添加和删除。
同样很显然的是，添加完全不需要分治操作，因为我们只询问全局最长连续段，而不关心某个位置所属的连续段长度。我们只需要在一个连续段的左右两端记录其长度，合并的时候更新即可。
那我们的问题就来到删除了，显然按照上面的处理方式，删除是困难的，因为我们不知道当前位置所处的连续段两边在哪，也就没法快速分裂一个连续段。
信息**易添加，难删除**。**回滚莫队**的标志特征。
我们使用一个**可回退化数组**处理上面的插入操作即可，每次处理询问先定位右端点r，再把l从所属块右端点移动到询问的位置，记录答案，回滚左端点l即可。
一般的可回退化数据结构允许撤销任意次修改，但这里没必要实现一个通用的可回退化数组。显然我们每次回滚都是回滚到一个特定的版本。我们只需要对于左端点移动产生的操作，记录影响的点和影响前的值，回滚时根据记录的受影响点，直接用影响前的值覆盖回去即可。
------------
### 要注意几点：
1. 回滚莫队**不能**处理**两端点在同一块中**的询问，这些询问要按所属块放到一起处理。显然**包含当前块的区间一定包含其中的询问**，我们扫出这些区间，剩下的区间只会是端点在当前块中的，每个询问扫一下当前块，使用另一个可回退化数组维护即可。
2. 莫队只能处理出**两端点至少一个在询问区间内**的区间，对于包含询问区间的区间，**显然包含当前询问所属块的右端点（注意不一定包含整个块）**（不跨块的我们在上面按块分组一起暴力），同样先预处理再做莫队。
3. 换块处理时候别忘了清空数组和答案，回滚时候别忘了回滚答案。
------------
常数不大，甚至用了vector依旧跑的飞快。快乐rk1。~~建议改为：香 港 记 者~~
```cpp
#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了。