LOJ6698 一键挖矿 优美的分治
jr_linys
·
·
题解
LOJ6698 一键挖矿
Oiclass 挖矿
Oiclass 万猪拱塔
显然对于在范围内的方块有 $(\max(x)-\min(x)+1)(max(y)-min(y)+1)=r-l+1$。
此思路来源于 [@ty_Ray](https://www.luogu.com.cn/user/726899) 大佬。
考虑分治，记左/右的坐标极值为 $l/r+ma/mi+x/y$，分以下几种情况：
1. $lmax=rmax$，$lmix=rmix$，$lmay=rmay$，$lmiy=rmiy$。即边界相同。
2. $lmax\le rmax$，$lmix\ge rmix$，$lmay\le rmay$，$lmiy\ge rmiy$，$l,r$ 可以反过来。即呈包含关系。
3. $lmax=rmax$，$lmix=rmix$，$lmay<rmay$，$lmiy<rmiy$，$x,y$、$l,r$ 都可以反过来。即呈平行关系。
因为情况 $2$ 有算重部分，所以答案应为 $3+2-1$。
就情况 $3$ 比较麻烦。假设情况为上面所列举的，由条件可得 $(rmax-rmix+1)(rmay-lmiy+1)=r-l+1$。
令 $sum=(rmax-rmix+1)$，转化为 $sum(rmay+1)-(r-mid)=sum·lmiy+(mid-l+1)$。
每次处理 $rmax,rmix$ 相同的一段，找到对应的 $lmax=rmax,lmix=rmix$ 的一段，在这条限制的基础上，移动右端点，符合 $y$ 限制的左端点在一个区间里，用桶查找满足式子的限制的左端点数量。
时间复杂度小常数 $O(n\log n)$。
```cpp
#include<bits/stdc++.h>
#define y1 yyyy//ty_ray的细节操作
typedef long long ll;
using namespace std;//知道这是快读就行了
int read(){char c;bool flag=1;while(c=getchar(),c<'0'||c>'9') if(c=='-') flag=0;int x=c^'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+(c^'0');return flag?x:-x;}
const int N=2e5;
int n,m,x[N+5],y[N+5],x1[N+5],y1[N+5],x2[N+5],y2[N+5],w[N*2];
ll ans;// mix miy max may 桶
void _calc(int l,int r,int mid,int x1[],int x2[],int y1[],int y2[]){//有点麻烦的情况3
int sum,j=mid,k=mid,K;
auto val=[&](int k){return sum*(y1[k])+(mid-k+1);};
for(int i=mid+1;i<=r;i++){
if(i==mid+1||x1[i]!=x1[i-1]||x2[i]!=x2[i-1]){
//每次处理 $rmax,rmix$ 相同的一段，找到对应的 $lmax=rmax,lmix=rmix$ 的一段
while(j>k) --w[val(j--)];
while(l<=j&&(x1[i]<x1[j]||x2[j]<x2[i])) --j;
sum=x2[j]-x1[j]+1,K=k=j;
while(l<K&&x1[i]==x1[K-1]&&x2[i]==x2[K-1]) --K;
}
if(K>=l&&x1[i]==x1[K]&&x2[i]==x2[K]){
//移动右端点，符合 $y$ 限制的左端点在一个区间里，用桶查找满足式子的限制的左端点数量
while(k>=K&&y2[k]<y2[i]) ++w[val(k--)];
while(j>k&&y1[i]<=y1[j]) --w[val(j--)];
ans+=w[sum*(y2[i]+1)-(i-mid)];
}
}
while(j>k) --w[val(j--)];
}
void calc(int l,int r,int mid,bool fl){
_calc(l,r,mid,x1,x2,y1,y2),_calc(l,r,mid,y1,y2,x1,x2);//x,y 翻转
for(int i=mid+1;i<=r;++i){//普通的情况2
int p=mid+1-((x2[i]-x1[i]+1)*(y2[i]-y1[i]+1)-(i-mid));
if(l<=p&&p<=mid&&x1[i]<=x1[p]&&x2[p]<=x2[i]&&y1[i]<=y1[p]&&y2[p]<=y2[i]) ++ans;
}
}
void solve(int l,int r){
if(l==r) return ++ans,void();
int mid=(l+r)>>1;
solve(l,mid),solve(mid+1,r);
x1[mid]=x2[mid]=x[mid],y1[mid]=y2[mid]=y[mid];
for(int i=mid-1;i>=l;--i) x1[i]=min(x1[i+1],x[i]),x2[i]=max(x2[i+1],x[i]),y1[i]=min(y1[i+1],y[i]),y2[i]=max(y2[i+1],y[i]);
x1[mid+1]=x2[mid+1]=x[mid+1],y1[mid+1]=y2[mid+1]=y[mid+1];
for(int i=mid+2;i<=r;++i) x1[i]=min(x1[i-1],x[i]),x2[i]=max(x2[i-1],x[i]),y1[i]=min(y1[i-1],y[i]),y2[i]=max(y2[i-1],y[i]);
for(int i=mid+1;i<=r;++i){//普通的情况1
int p=mid+1-((x2[i]-x1[i]+1)*(y2[i]-y1[i]+1)-(i-mid));
if(l<=p&&p<=mid&&x1[i]==x1[p]&&x2[p]==x2[i]&&y1[i]==y1[p]&&y2[p]==y2[i]) --ans;
}
calc(l,r,mid,0);
reverse(x1+l,x1+1+r),reverse(y1+l,y1+1+r),reverse(x2+l,x2+1+r),reverse(y2+l,y2+1+r);
calc(l,r,l+(r-mid)-1,1);//l,r 翻转
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) for(int j=1,s;j<=m;++j) s=read(),x[s]=i,y[s]=j;
solve(1,n*m);
printf("%lld",ans);
}
```