一键挖矿
弱化版(?):CF562F
将矩阵扩展一个单位(长宽均加1),把当前存在的格子染色。
可以发现当且仅当恰好存在4个有1个格子被染色,不存在有3个格子被染色的2x2矩阵时满足题意。
枚举右端点 r,设 g(l) 表示选择 [l,r] 时有多少个上述矩阵。
可以发现 g(r)=4,且对于 x\(\in\)[l,r],g(x)$\geq$4。
也就是我们维护区间最小值和其个数,判断值是否为4即可。
新增1个 r 会影响其周围4个2x2的矩阵,考虑 r 的贡献,这个根据它在某个矩阵中的大小位置判断。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define ls p<<1
#define rs p<<1|1
const int MAXN=5e5+5;
const int INF=0x3f3f3f3f;
void read(int &x){
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){
if(s=='-') f=-1;s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);s=getchar();
}
x*=f;
}
int n,m,ta[MAXN<<2],up,wz[MAXN][2];
vector<vector<int> >va;
ll Ans;
struct ren{
int mi,con;
ren(){};
ren(int M,int C){mi=M;con=C;}
}t[MAXN<<2];
ren operator+(ren a,ren b){
if(a.mi<b.mi) return a;
if(b.mi<a.mi) return b;
return (ren){a.mi,a.con+b.con};
}
void pup(int p){t[p]=t[ls]+t[rs];}
void pdo(int p){
if(ta[p]==0) return;
t[ls].mi+=ta[p];t[rs].mi+=ta[p];
ta[ls]+=ta[p];ta[rs]+=ta[p];
ta[p]=0;return;
}
void bui(int p,int l,int r){
t[p]=(ren){0,r-l+1};
if(l==r) return;
int mid=(l+r)>>1;
bui(ls,l,mid);bui(rs,mid+1,r);
}
void modi(int p,int l,int r,int ql,int qr,int x){
if(l>=ql&&r<=qr){
ta[p]+=x;t[p].mi+=x;return;
}
pdo(p);
int mid=(l+r)>>1;
if(ql<=mid) modi(ls,l,mid,ql,qr,x);
if(qr>mid) modi(rs,mid+1,r,ql,qr,x);
pup(p);
}
ren que(int p,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr) return t[p];
pdo(p);
int mid=(l+r)>>1;ren tmp=(ren){INF,0};
if(ql<=mid) tmp=tmp+que(ls,l,mid,ql,qr);
if(qr>mid) tmp=tmp+que(rs,mid+1,r,ql,qr);
return tmp;
}
void calc(int x,int y,int z,int zz){
vector<int> vv;vv.push_back(x);vv.push_back(y);vv.push_back(z);vv.push_back(zz);
int wz=0;
sort(vv.begin(),vv.end());
for(int i=0;i<4;i++){
if(vv[i]==x){
wz=i;break;
}
}
for(int i=0;i<4;i++){
int op=(wz-i+1)&1;
if(op&1){
if(i==0) modi(1,1,up,1,vv[i],1);
else modi(1,1,up,vv[i-1]+1,vv[i],1);
}
else{
if(i==0) modi(1,1,up,1,vv[i],-1);
else modi(1,1,up,vv[i-1]+1,vv[i],-1);
}
if(i==wz) break;
}
}
int main(){
read(n);read(m);up=n*m;
va.resize(n+5);
for(int i=0;i<=n+1;i++){
va[i].resize(m+5);
for(int j=0;j<=m+1;j++){
if(i==0||i==n+1||j==0||j==m+1){
va[i][j]=up+1;continue;
}
read(va[i][j]);wz[va[i][j]][0]=i;wz[va[i][j]][1]=j;
}
}
bui(1,1,up);
for(int i=1;i<=up;i++){
int x=wz[i][0],y=wz[i][1];
calc(va[x][y],va[x-1][y],va[x-1][y-1],va[x][y-1]);
calc(va[x][y],va[x][y+1],va[x-1][y],va[x-1][y+1]);
calc(va[x][y],va[x][y-1],va[x+1][y-1],va[x+1][y]);
calc(va[x][y],va[x][y+1],va[x+1][y],va[x+1][y+1]);
ren op=que(1,1,up,1,i);
if(op.mi==4) Ans+=op.con;
}
printf("%lld",Ans);return 0;
}