\(\texttt{「CF1661E」 Narrow Components}\)
\(\texttt{Describe}\)
给你一个 \(3\) 行 \(n\) 列的 \(01\) 矩阵 \(a\)，其中 \(0\) 表示黑色格子，\(1\) 表示白色格子。
再给出 \(q\) 次讯问，每次询问给出两个整数 \(l,r\) 让你回答区间 \([l,r]\) 白色连通块的数量
\(\texttt{Input Format}\)
第 \(1\) 行给出一个整数 \(n\)。
接下来 \(3\) 行，每行有一个长度为 \(n\) 的 \(01\) 串，第 \(i\) 行 \(01\) 串的第 \(j\) 个字符表示 \(a_{i,j}\) 的值。
第 \(5\) 行给出整数 \(q\)。
接下来 \(q\) 行，每行两个整数 \(l,r\)。
\(\texttt{Output Format}\)
对于每个询问每行输出一个整数表示答案。
\(\texttt{Example In 1}\)
12
100101011101
110110010110
010001011101
8
1 12
1 1
1 2
9 9
8 11
9 12
11 12
4 6
\(\texttt{Example Out 1}\)
7
1
1
2
1
3
3
3
\(\texttt{Data}\)
\(1\le n\le 5\times 10^5,1\le q\le 3\times 10^5\\1\le l\le r\le n\)
\(\texttt{Solution1}\)
初看题目感觉信息难以维护，故考虑莫队。由与每次增加或删除都是由新加入或删除的列和当前边界决定，所以 \(\text{Add}\) 和 \(\text{Del}\) 可以简单写出。对于第 \(i\) 列，我们以第 \(3\) 行为最低位，二进制压缩成整数 \(s_i\)。由于在判断两列间的贡献比较麻烦，而且常数很大，但是每列有 \(s_i\in[0,7]\) 所以两列间仅有 \(8^2\) 种状态，可以先用程序打表 \(w_{x,y}\) 表示新加入或删除列为 \(x\)，边界列为 \(y\) 的贡献，大大降低常数。下面贴出打表代码
void init()
{
w[0][0]=0,w[0][1]=0,w[0][2]=0,w[0][3]=0,w[0][4]=0,w[0][5]=0,w[0][6]=0,w[0][7]=0;
w[1][0]=1,w[1][1]=0,w[1][2]=1,w[1][3]=0,w[1][4]=1,w[1][5]=0,w[1][6]=1,w[1][7]=0;
w[2][0]=1,w[2][1]=1,w[2][2]=0,w[2][3]=0,w[2][4]=1,w[2][5]=1,w[2][6]=0,w[2][7]=0;
w[3][0]=1,w[3][1]=0,w[3][2]=0,w[3][3]=0,w[3][4]=1,w[3][5]=0,w[3][6]=0,w[3][7]=0;
w[4][0]=1,w[4][1]=1,w[4][2]=1,w[4][3]=1,w[4][4]=0,w[4][5]=0,w[4][6]=0,w[4][7]=0;
w[5][0]=2,w[5][1]=1,w[5][2]=2,w[5][3]=1,w[5][4]=1,w[5][5]=0,w[5][6]=1,w[5][7]=0;
w[6][0]=1,w[6][1]=1,w[6][2]=0,w[6][3]=0,w[6][4]=0,w[6][5]=0,w[6][6]=0,w[6][7]=0;
w[7][0]=1,w[7][1]=0,w[7][2]=0,w[7][3]=0,w[7][4]=0,w[7][5]=0,w[7][6]=0,w[7][7]=0;
}
此时考虑一个 \(\texttt{Hack}\) 数据
111
001
111
当我们新增加第 \(3\) 列（当前左边界为第 \(1\) 列）时，它不仅没有带来贡献，还把原有的两个连通块联通了，而这种情形是没有考虑到的。发现只有当前这一种特殊情形，故考虑特殊处理本情况，我们考虑向左或向右。
考虑向左，发现只有当在新加入列右方存在连续的 \(\begin{bmatrix}1\\0\\1\end{bmatrix}\) 且上下不连通时当前为 \(\begin{bmatrix}1\\1\\1\end{bmatrix}\) 才会贡献出 \(-1\)，使的上下联通有且仅有 \(\begin{bmatrix}1\\1\\1\end{bmatrix}\) 一种可能性，所以记录 \(\texttt{suf}_{i}\) 表示区间 \([i,\texttt{suf}_i-1]\) 全为 \(\begin{bmatrix}1\\0\\1\end{bmatrix}\)，而第 \(\texttt{suf}_i\) 列为 \(\begin{bmatrix}1\\1\\1\end{bmatrix}\)，如果 \(\texttt{suf}_i=0\) 则无意义。向右显然相似。类似的，我们可以定义 \(\texttt{pre}_i\) 表示在其不为 \(0\) 的情况下表示区间 \([\texttt{pre}_i+1,i]\) 全为 \(\begin{bmatrix}1\\0\\1\end{bmatrix}\) 且第 \(\texttt{pre}_i\) 列为 \(\begin{bmatrix}1\\1\\1\end{bmatrix}\)。
我们可以根据 \(\texttt{pre},\texttt{suf}\) 在每次增减时记录是否贡献 \(-1\) 统计，至于 \(\texttt{pre},\texttt{suf}\) 则可以正序和逆序分别扫一遍 \(\mathcal O(n)\) 预处理，块长取 \(\dfrac{n}{\sqrt q}\)，最终复杂度为 \(\mathcal O(n\sqrt q)\)。
\(\texttt{Solution2}\)
听说可以用并查集的奇妙做法，咕咕咕有时间补补
\(\texttt{Code}\)
点击查看代码
#include<bits/stdc++.h>
#define MOD (1000000007)
#define ll long long
#define Swap(x,y) (x^=y,y^=x,x^=y)
using namespace std;
void read(ll &x)
{
register char ch=0;register bool f=0;x=0;
while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=f?-x:x;
}
void write(ll x,bool bk)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(!x)
{
if(!bk) putchar('0');
return;
}
write(x/10,1);
putchar((x%10)^48);
}
void print(ll x,char ch)
{
write(x,0);
if(ch) putchar(ch);
}
ll w[10][10];
ll n,q,Len,L=1,R=1,cnt;
ll s[500005],idx[500005],ans[300005];
ll pre[500005],suf[500005];
struct Query{
ll l,r,id;
}Se[300005];
bool cmp(Query a,Query b){return (idx[a.l]^idx[b.l])?(idx[a.l]<idx[b.l]):((idx[a.l]&1)?(a.r<b.r):(a.r<b.r));}
void init()
{
w[0][0]=0,w[0][1]=0,w[0][2]=0,w[0][3]=0,w[0][4]=0,w[0][5]=0,w[0][6]=0,w[0][7]=0;
w[1][0]=1,w[1][1]=0,w[1][2]=1,w[1][3]=0,w[1][4]=1,w[1][5]=0,w[1][6]=1,w[1][7]=0;
w[2][0]=1,w[2][1]=1,w[2][2]=0,w[2][3]=0,w[2][4]=1,w[2][5]=1,w[2][6]=0,w[2][7]=0;
w[3][0]=1,w[3][1]=0,w[3][2]=0,w[3][3]=0,w[3][4]=1,w[3][5]=0,w[3][6]=0,w[3][7]=0;
w[4][0]=1,w[4][1]=1,w[4][2]=1,w[4][3]=1,w[4][4]=0,w[4][5]=0,w[4][6]=0,w[4][7]=0;
w[5][0]=2,w[5][1]=1,w[5][2]=2,w[5][3]=1,w[5][4]=1,w[5][5]=0,w[5][6]=1,w[5][7]=0;
w[6][0]=1,w[6][1]=1,w[6][2]=0,w[6][3]=0,w[6][4]=0,w[6][5]=0,w[6][6]=0,w[6][7]=0;
w[7][0]=1,w[7][1]=0,w[7][2]=0,w[7][3]=0,w[7][4]=0,w[7][5]=0,w[7][6]=0,w[7][7]=0;
}
void L_Add(ll now,ll x)
{
cnt+=w[s[x]][s[now]];
if(((suf[now]>R)||(!suf[now]))&&(!(s[x]^7))&&(!(s[now]^5))) --cnt;//printf("[%lld,%lld]=%lld\n",x,R,cnt);
return;
}
void L_Del(ll now,ll x)
{
cnt-=w[s[x]][s[now]];
if(((suf[now]>R)||(!suf[now]))&&(!(s[x]^7))&&(!(s[now]^5))) ++cnt;//printf("[%lld,%lld]=%lld\n",x,R,cnt);
return;
}
void R_Add(ll now,ll x)
{
cnt+=w[s[x]][s[now]];
if((pre[now]<L)&&(!(s[x]^7))&&(!(s[now]^5))) --cnt;//printf("[%lld,%lld]=%lld\n",L,x,cnt);
return;
}
void R_Del(ll now,ll x)
{
cnt-=w[s[x]][s[now]];
if((pre[now]<L)&&(!(s[x]^7))&&(!(s[now]^5))) ++cnt;//printf("[%lld,%lld]=%lld\n",L,x,cnt);
return;
}
int main()
{
init();
read(n);
Len=sqrt(n);
for(ll i=1;i<=3;i++)
{
for(ll j=1;j<=n;j++)
s[j]=(s[j]<<1)+(getchar()^48);
getchar();
}
ll lst;
lst=0;
for(ll i=1;i<=n;i++)
idx[i]=i/Len;
for(ll i=1;i<=n;i++)
{
if((s[i]^5)&&(s[i]^7))
{
lst=0;
continue;
}
if(!(s[i]^5)) pre[i]=lst;
if(!(s[i]^7)) lst=i;
}
lst=0;
for(ll i=n;i;i--)
{
if((s[i]^5)&&(s[i]^7))
{
lst=0;
continue;
}
if(!(s[i]^5)) suf[i]=lst;
if(!(s[i]^7)) lst=i;
}
read(q);
for(ll i=1;i<=q;i++)
{
read(Se[i].l),read(Se[i].r);
Se[i].id=i;
}
if(!(s[1]^0)) cnt=0;
if(!(s[1]^1)) cnt=1;
if(!(s[1]^2)) cnt=1;
if(!(s[1]^3)) cnt=1;
if(!(s[1]^4)) cnt=1;
if(!(s[1]^5)) cnt=2;
if(!(s[1]^6)) cnt=1;
if(!(s[1]^7)) cnt=1;
sort(Se+1,Se+q+1,cmp);
for(ll i=1;i<=q;i++)
{
while(L<Se[i].l)
{//putchar('1');
L_Del(L+1,L);
++L;
}
while(L>Se[i].l)
{//putchar('2');
L_Add(L,L-1);
--L;
}
while(R<Se[i].r)
{//putchar('3');
R_Add(R,R+1);
++R;
}
while(R>Se[i].r)
{//putchar('4');
R_Del(R-1,R);
--R;
}
ans[Se[i].id]=cnt;
}
for(ll i=1;i<=q;i++)
print(ans[i],'\n');
return 0;
}