分块大法好
gargantuar
·
·
题解
听说没有人写分块题解,那么我来一发
前几天学校模拟赛的时候遇到了这道题，吓得我直接骗了30分(
然而机房的大佬们都纷纷拿出 CDQ，树状数组，平衡树各显神通，蒟蒻自闭。
我就想反正树状数组我也会写，思路听明白了写一遍也是浪费时间(
但是作为新时代好青年，题还是要补的。
为了最大化利用补题时间效率，我就用全新的分块A了这道题。
题目分析
先说30分的写法，显而易见， p<1000 ，此时只要给每一个踏板的起点进行双关键字排序，进行 dp，维护在每个跳板强制跳跃 后到达终点可以节省的最大步数，最后用 n* 2 减去即可。
然后考虑 p<10^5 ，此时显然不能暴力 dp 了，先对 x 和 y 分别进行离散化，然后以 \sqrt p 为长宽，对矩阵进行分块，按照跳板起点位置依次把所有的跳板装进块里，注意普通数组容易炸空间，用 vector 存。
很明显我们要减少对于每一个跳板的状态转移次数，时我们选择改变维护的信息，选择维护每个跳板的位置到终点可以节省的最大步数，注意这里我们不强制跳跃。
这样做的好处就是一个跳板可以直接表示他右上所有路径的最优解。
如图，红色点为跳板起点，蓝色点为终点，黑色为其他跳板的起点。发现两种转移方法，分别是从粉色线上的点直接转移到红色点，表示不选择跳跃，直接走到其他点，和从绿色线上的黑点转移到蓝色点，再加上从红到蓝节省的步数，表示选择跳跃，再走到其他点。剩下的黑点就不用管了。
此时聪明的我已经想到了，对于每一个块记录块内的左下方没有点的点，块间转移时之考虑这些点，之后如果发现一个块的块内有点，右上方的块就不去查询了。至于块内，暴力就行。
但此时聪明的你马上拿出来一组数据来 hack 我
如图，每一个黑点都会转移到所有红点，此时时间瞬间被卡到了 p^2 。
然后分析，为什么时间会被卡爆呢？显然发现，在之前的图中，如果你选中了一个点
作为转移对象，那么这个点的右上方就没必要查询了。然而红点的信息互不包含，黑点只能暴力转移了。而且黑点和黑点也互不构成包含关系。
既然没有点能包含红点，那就新建一些节点包含不就行了？如果我们给每一个块的左下角加上一个新节点，那么这个节点就会包含块内的所有信息。
如图，黄线表示块边界，绿点表示新建的节点，此时每一个黑节点只会从恰好一个绿节点进行转移，而每一个红节点又恰好被至少一个绿节点进行包含，绿点数量也为 O(p) 。所以时间复杂度就降到了 O(p) 了
然后聪明的你又拿出了一组数据 hack 我。
看样子绿点也丧失作用了。
但事实真的如此吗？别忘了我们是对 x 和 y 分别进行离散化的，也就是说块的长宽最大为 \sqrt p ，同时块内也最多存 \sqrt p 个点，也就是说，最坏情况块间转移的复杂度也是 O(p) 的。而且这样的转移是有限的，平均下来，复杂度应该是
当然了，有时候情况会极端一点，例如 $x$ 的取值为分散，但 $y$ 只会取 $1$ 或 $2$，这种情况下 一个块内也可能出现 $p$ 级别的点数。但此时发现点大多的坐标都是重合的。所以写两个数组，分别记录 $x$ 为某个值时的最大转移方案数，和 $y$ 为某个值时的最大转移方案数。
现在，最终方案已经近在咫尺了，对于每个点，我们只需要维护正上方块的转移，正右方块的转移，以及右上方第一个绿点的转移即可。别忘了对块内进行暴力转移。
### AC代码
------------
吸氧优化情况下 $2s$ 不开是 $5s$ 左右，卡卡常数应该可以更快
其实还有很多优化可以加速，不过我是懒狗，就不加了
蒟蒻码风难看，请见谅。
```cpp
#include<bits/stdc++.h>
#define intl long long
using namespace std;
int n,m,eont,eont2,k,k2,mp[400005],mp2[400005],ll[5005],rr[5005],ll2[5005],rr2[5005],bl[400005],bl2[400005],sq,sq2,fnk[2000][2000],fmk[2000][2000],zont,ans;
vector<vector<int> > fzz;
vector<int> fx;
vector<vector<vector<int> > > fk;
vector<vector<vector<int> > > fnmdp;
int xmm[400005],ymm[400005];
struct lsh {
int val,id,w;
} e[800005],e2[800005];
struct node {
int x,y,a,b,v,k;
} a[400005];
bool cmp(lsh a,lsh b) {
return a.val<b.val;
}
bool ccp(node a,node b) {
if(a.x==b.x)return a.y>b.y;
return a.x>b.x;
}
inline void fbl(int bx,int by,int z,int zx,int zy,bool adSelf) {
for(int i=1; i<=fmk[bx][by]; ++i) {
int ii=fk[bx][by][i];
if(a[ii].x>=zx&&a[ii].y>=zy&&ii!=z) {
if(adSelf)a[z].k=max(a[z].k,a[z].v+a[ii].k);
else a[z].k=max(a[z].k,a[ii].k);
}
}
}
inline void fd(int z,int t,bool adSelf) {
if(adSelf)a[z].k=max(a[z].k,a[z].v+a[t].k);
else a[z].k=max(a[z].k,a[t].k);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=m; ++i) {
scanf("%d",&e[++eont].val);
e[eont].id=i;
e[eont].w=1;
scanf("%d",&e2[++eont2].val);
e2[eont2].id=i;
e2[eont2].w=2;
scanf("%d",&e[++eont].val);
e[eont].id=i;
e[eont].w=3;
scanf("%d",&e2[++eont2].val);
e2[eont2].id=i;
e2[eont2].w=4;
a[i].k=a[i].v=e[eont].val-e[eont-1].val+e2[eont2].val-e2[eont2-1].val;
}
sort(e+1,e+1+eont,cmp);
sort(e2+1,e2+1+eont2,cmp);
e[0].val=e[1].val-1;
e2[0].val=e2[1].val-1;
for(int i=1; i<=eont; ++i) {
e[i].val!=e[i-1].val?k++:0;
mp[i]=e[i].val;
if(e[i].w==1) {
a[e[i].id].x=k;
} else if(e[i].w==3) {
a[e[i].id].a=k;
}
}
for(int i=1; i<=eont2; ++i) {
e2[i].val!=e2[i-1].val?k2++:0;
mp2[i]=e2[i].val;
if(e2[i].w==2) {
a[e2[i].id].y=k2;
} else if(e2[i].w==4) {
a[e2[i].id].b=k2;
}
}
for(int i=1; i<=m; ++i) {
}
sq=sqrt(k);
sq2=sqrt(k2);
fx.push_back(0);
for(int i=1; i<=sq2+5; ++i)fzz.push_back(fx);
for(int i=1; i<=sq+5; ++i)fk.push_back(fzz);
for(int i=1; i<=sq+5; ++i)fnmdp.push_back(fzz);
for(int i=1; i<=sq; ++i) {
ll[i]=k/sq*(i-1)+1;
rr[i]=k/sq*i;
}
for(int i=1; i<=sq2; ++i) {
ll2[i]=k2/sq2*(i-1)+1;
rr2[i]=k2/sq2*i;
}
rr[sq]=k,rr2[sq2]=k2;
for(int i=1; i<=sq; ++i)
for(int j=ll[i]; j<=rr[i]; ++j)
bl[j]=i;
for(int i=1; i<=sq2; ++i)
for(int j=ll2[i]; j<=rr2[i]; ++j)
bl2[j]=i;
for(int i=1; i<=sq; ++i) {
for(int j=1; j<=sq2; ++j) {
if(fmk[i][j]==0) {
++zont;
++fmk[i][j];
fk[i][j].push_back(m+zont);
a[m+zont].x=a[m+zont].a=ll[i];
a[m+zont].y=a[m+zont].b=ll2[j];
a[m+zont].v=0;
a[m+zont].k=0;
}
}
}
sort(a+1,a+m+1,ccp);
for(int i=1; i<=m; ++i) {
++fmk[bl[a[i].x]][bl2[a[i].y]];
fk[bl[a[i].x]][bl2[a[i].y]].push_back(i);
++fnk[bl[a[i].a]][bl2[a[i].b]];
fnmdp[bl[a[i].a]][bl2[a[i].b]].push_back(i);
}
for(int xx=sq; xx>=1; --xx)
for(int yy=sq2; yy>=1; --yy) {
if(xx!=sq&&yy!=sq2) {
xmm[rr[xx]]=max(xmm[rr[xx]],a[fk[xx+1][yy+1][1]].k);
ymm[rr2[yy]]=max(ymm[rr2[yy]],a[fk[xx+1][yy+1][1]].k);
}
for(int ii=1; ii<=fnk[xx][yy]; ++ii) {
int i=fnmdp[xx][yy][ii];
for(int q=a[i].a; q<=rr[xx]; ++q) {
if(!xmm[q])continue;
a[i].k=max(a[i].k,a[i].v+xmm[q]);
}
for(int q=a[i].b; q<=rr2[yy]; ++q) {
if(!ymm[q])continue;
a[i].k=max(a[i].k,a[i].v+ymm[q]);
}
}
for(int ii=2,z=1; z||ii==1; ++ii) {
if(ii>fmk[xx][yy])z=0,ii=1;
int i=fk[xx][yy][ii];
int xxx=bl[a[i].a],yyy=bl2[a[i].b];
// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
fbl(xx,yy,i,a[i].x,a[i].y,0);
if(xx!=sq)fbl(xx+1,yy,i,a[i].x,a[i].y,0);
if(yy!=sq2)fbl(xx,yy+1,i,a[i].x,a[i].y,0);
if(xx!=sq&&yy!=sq2)fd(i,fk[xx+1][yy+1][1],0);
// -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
fbl(xxx,yyy,i,a[i].a,a[i].b,1);
if(xxx!=sq&&yyy!=sq2)fd(i,fk[xxx+1][yyy+1][1],1);
ans=max(ans,a[i].k);
xmm[a[i].x]=max(xmm[a[i].x],a[i].k);
ymm[a[i].y]=max(ymm[a[i].y],a[i].k);
}
}
printf("%d",n*2-ans);
}
```