过来补常见套路题
对于前缀\([1,i]\)将它们染黑，考虑所有\((H+1) \times (W+1)\)个\(2 \times 2\)小正方形，可以证明\([1,i]\)形成矩形充要条件是：
- 恰好\(4\)个有一个黑格的\(2 \times 2\)小正方形
- 没有任何一个有三个黑格的\(2 \times 2\)小正方形
同时可以发现有一个或三个黑格的小正方形总数不小于\(4\)
于是线段树维护所有前缀的有一个或三个黑格的小正方形个数，维护最小值及其个数。
初始化的时候可以线性建树。
时间复杂度\(O(HW+32Q\log HW)\)是常数非常大的做法，也许可以压一压，不会了。。
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<‘:‘<<x<<endl
const int MAXN=1e6+10;
struct node{
int mn,v;
inline node operator+(const node &b)const{
if(mn==b.mn)return {mn,v+b.v};
return mn<b.mn?(*this):b;
}
}tr[MAXN<<2];
vector<int>mp[MAXN];
int H,W,n,R[MAXN],C[MAXN],tag[MAXN<<2];
#define lson o<<1
#define rson o<<1|1
inline void madd(int o,int v){
tr[o].mn+=v;tag[o]+=v;
}
inline void pushdown(int o){
if(!tag[o])return;
madd(lson,tag[o]);madd(rson,tag[o]);tag[o]=0;
}
void add(int o,int l,int r,int ql,int qr,int v){
if(l>=ql&&r<=qr){madd(o,v);return;}
int mid=l+r>>1;pushdown(o);
if(ql<=mid)add(lson,l,mid,ql,qr,v);
if(qr>mid)add(rson,mid+1,r,ql,qr,v);
tr[o]=tr[lson]+tr[rson];
}
inline void mdy(int x1,int x2,int x3,int x4,int coe){
int a[5]={0,x1,x2,x3,x4};
sort(a+1,a+5);
if(a[1]<a[2])add(1,1,n,a[1],a[2]-1,coe);
if(a[3]<a[4])add(1,1,n,a[3],a[4]-1,coe);
}
int sum[MAXN];
inline void mdy2(int x1,int x2,int x3,int x4){
int a[5]={0,x1,x2,x3,x4};
sort(a+1,a+5);
if(a[1]<a[2])++sum[a[1]],--sum[a[2]];
if(a[3]<a[4])++sum[a[3]],--sum[a[4]];
}
void build(int o,int l,int r){
if(l==r){tr[o]={sum[l],1};return;}
int mid=l+r>>1;
build(lson,l,mid);build(rson,mid+1,r);
tr[o]=tr[lson]+tr[rson];
}
void give_initial_chart(int HH,int WW,vector<int>RR,vector<int>CC){
H=HH;W=WW;n=H*W;
fp(i,1,n)R[i]=RR[i-1]+1,C[i]=CC[i-1]+1;
fp(i,0,H+1)mp[i].resize(W+2,n+1);
fp(i,1,n)mp[R[i]][C[i]]=i;
fp(i,1,H+1)fp(j,1,W+1)mdy2(mp[i-1][j-1],mp[i-1][j],mp[i][j-1],mp[i][j]);
fp(i,1,n)sum[i]+=sum[i-1];
build(1,1,n);
}
inline void mdy(int x,int y,int coe){
mdy(mp[x][y],mp[x-1][y],mp[x][y-1],mp[x-1][y-1],coe);
mdy(mp[x][y],mp[x-1][y],mp[x-1][y+1],mp[x][y+1],coe);
mdy(mp[x][y],mp[x][y-1],mp[x+1][y-1],mp[x+1][y],coe);
mdy(mp[x][y],mp[x][y+1],mp[x+1][y],mp[x+1][y+1],coe);
}
int swap_seats(int a,int b){
++a;++b;
mdy(R[a],C[a],-1);mdy(R[b],C[b],-1);
swap(R[a],R[b]);swap(C[a],C[b]);
mp[R[a]][C[a]]=a;mp[R[b]][C[b]]=b;
mdy(R[a],C[a],1);mdy(R[b],C[b],1);
return tr[1].mn==4?tr[1].v:0;
}