[DS记录]P7843 「C.E.L.U-03」布尔
command_block
2021-10-20 15:40:36
**题意** ： 有 $n$ 个布尔变量 $X_{1\sim n}$ ，给出 $m$ 个限制。
限制形如 （$X_i$ 为 $a$）$\Leftrightarrow$（$X_j$ 为 $b$）
一共 $q$ 次询问，每次询问给出一个区间 $[l,r]$。求最少把 $l,r$ 划分成多少段连续的区间，使得每段里的限制都可以得到一组合法解。如果无论如何都无法得到合法解，输出 `-1`。
$n\leq 10^5,m\leq 6\times 10^6,q\leq 10^6$ ，时限$\texttt{2.5s}$ 。
------------
限制是 $\text{2-SAT}$ 的形式，但因为双向连边变得十分 simple ，可以转为无向图连通性问题。
问题等价于：有一个有 $2n$ 个点的图，编号为 $1\sim 2n$ 。给出 $m$ 组无向边 $l_{1\sim m}$ 。
将 $l_{l\sim r}$ 连接后若存在 $v,v+n$ 联通，则称区间 $[l,r]$ 是不好的。
每次询问 $[L,R]$ 至少划分为多少个好的区间。
------------
记 $f_i$ 为最大的 $k$ 使得区间 $[i,k)$ 是好的。在 $f$ 上倍增即可回答询问。
接下来只需要求 $f$。
------------
考虑如何便捷地判定图是否合法。
对于 $u$ ，当 $u\leq n$ 时记 $u'=n+n$ ，当 $u>n$ 时记 $u'=u-n$ ，即一对中的另一个。
- ① ：维护每个联通块的点集，并启发式合并，可以做到均摊 $O(n\log n)$。
这种做法由于带有均摊，只能加，不能减和撤回，难以扩展。
- ② ：将原问题转化为：点有颜色（每个对子 $v,v'$ 颜色相同），若存在某个联通块有两个颜色相同的点，则不合法。
维护两个并查集，一个是原图的并查集，一个是颜色的并查集。加边时，若前者成功后者失败，则说明不合法。
这成功地将判定转化为了图的连通性问题。
- ③ ：由于本题的特殊性，有更方便的方法。
**性质** ： 根据（对称的）连边方式，“$u,v$连通” $\Leftrightarrow$“$u+n,v+n$连通” 。
**结论** ： 在对 $u,v,u',v'$ 进行一次连边后，只需判定 $u,u'$ 是否连通。
**证明** ：（只证连接 $(u,v),(u',v')$ 的情况，另一种类似）
假设 $u,u'$ 不连通，且此时存在新的 $w,w'$ 连通。
说明 $w,w'$ 分别与 $u,v$ 或者 $'n,v'$ 连通。
对于第一种情况，$w\leftrightarrow u,\ w'\leftrightarrow v$ ，由引理有 $w'\leftrightarrow u',\ w\leftrightarrow v'$ 。
因此有 $u\leftrightarrow w\leftrightarrow v'\leftrightarrow u'$ ，矛盾。
------------
不难发现 $f$ 具有单调性，利用双指针可以将问题转化为 ：
- 在右侧加入一条边
- 在左侧删除一条边
- 判定是否合法
在线动态图连通性可以做，但是太麻烦，常数又大，不可取。
------------
考虑一类奇怪的 **线段树分治+双指针** 的算法。
记 $E_i$ 表示加入了边 $l_{i\sim f_i}$ 的图。初始时 $f_i=i$。
若已经计算完了 $f_{1\sim i-1}$ ，准备计算 $f_i$ ，考虑 $f_i$ 的增大，若向右加入 $l_{f_i+1}$ 合法，则将其加入到 $E_i$ 中，且令 $f_i$ 加一。
此时 $l_{f_i+1}$ 在 $E$ 中的“存在”区间已经确定为 $[i,f_i+1]$ ，可以用线段树分治来给 $E_{i\sim f_i+1}$ 加入 $l_{f_i+1}$ ，这样就不用考虑删除了。
线段树分治配合可撤回并查集，复杂度为 $O(m\log m\log n+q\log m)$ 。
------------
出题人用了一类奇怪的 **决策单调性分治** ，即 $solve(l,r,L,R)$ 表示求 $f_{l\sim r}$ 且答案必在 $L\sim R$ 内。
假设我们的并查集已经含有 $l_{r+1\sim L-1}$ 。只需逐个加入 $l_{L\sim R}$ 即可求出 $f_{mid}$。
分为两个子问题 $solve(l,mid-1,L,f_{mid}),\ solve(mid+1,r,f_{mid},R)$ 。
对于前一个子问题，需要继承的是 $l_{mid\sim L-1}$ ，先将原并查集恢复到 $l_{r+1\sim L-1}$ ，再加入 $l_{mid\sim r}$ ，完事后再撤回即可。
对于后一个子问题，需要继承的是 $l_{r+1\sim f_{mid}-1}$ ，这个在 $l_{r+1\sim L-1}$ 的基础上再加入 $l_{L\sim f_{mid}-1}$ 就好。
这其实揭示了在贡献不能删除只能撤回（回滚）时，双指针配合决策单调性分治的方法。
根据决策单调性分治的经典分析，复杂度仍然是 $O(m\log m\log n+q\log m)$ 。
------------
这里是 **线段树分治+双指针** 的代码。
还挺好写的。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 200500
#define MaxM 600500
using namespace std;
namespace io {
char buf[8005000],*p1=buf,*p2=buf,obuf[8005000],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,8000000,stdin),p1==p2)?EOF:*p1++)
int rd() {
int x=0;char ch=getchar();
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
void putc(char ch){*O++=ch;}
void print(int x){
if (x<0){putc('-');print(-x);}
else {if(x>9)print(x/10);putc(x%10+'0');}
}
void flush(bool op=0){fwrite(obuf,O-obuf,1,stdout);O=obuf;}
}using namespace io;
struct Data{int u,v;};
struct UFS{
int f[MaxN],c[MaxN];
void Init(int n)
{for (int i=1;i<=n;i++){f[i]=i;c[i]=1;}}
int find(int u)
{while(f[u]!=u)u=f[u];return u;}
bool chk(int u,int v)
{return find(u)==find(v);}
Data stk[MaxN];int tn;
void merge(int u,int v){
u=find(u);v=find(v);
if (u==v)return ;
if (c[u]>c[v])swap(u,v);
stk[++tn]=(Data){u,v};
c[f[u]=v]+=c[u];
}
void undo(){
int u=stk[tn].u,v=stk[tn].v;tn--;
c[v]-=c[f[u]=u];
}
}F;
vector<int> b[1<<21];
int wfl,wfr;
void add(int l,int r,int u)
{
if (wfl<=l&&r<=wfr){b[u].push_back(wfr);return ;}
int mid=(l+r)>>1;
if (wfl<=mid)add(l,mid,u<<1);
if (mid<wfr)add(mid+1,r,u<<1|1);
}
struct Line{int u,v;bool op;}s[MaxM];
int n,m;
bool link(const Line &L)
{
int u=L.u,v=L.v,u2=u+n,v2=v+n;
if (L.op)swap(v,v2);
F.merge(u,v);F.merge(u2,v2);
return F.chk(u,u2);
}
int f[20][MaxM];
void solve(int l,int r,int u)
{
for (int i=0;i<b[u].size();i++)link(s[b[u][i]]);
if (l==r){
int &r=f[0][l];
r=max(l,f[0][l-1]);
while(r<=m){
if (link(s[r]))break;
wfl=l+1;wfr=r;if (wfl<=wfr)add(1,m,1);
r++;
}return ;
}int mid=(l+r)>>1,sav=F.tn;
solve(l,mid,u<<1);while(F.tn>sav)F.undo();
solve(mid+1,r,u<<1|1);while(F.tn>sav)F.undo();
}
int o[MaxM];
int qry(int u,int r)
{
if (o[r]-o[u-1])return -1;
int ans=0;
for (int k=19;k>=0;k--)
if (f[k][u]<=r){u=f[k][u];ans|=1<<k;}
return ans+1;
}
int main()
{
int q;
n=rd();m=rd();q=rd();
for (int i=1;i<=m;i++){
s[i].u=rd();s[i].op^=rd();
s[i].v=rd();s[i].op^=rd();
}
F.Init(n*2);solve(1,m,1);
f[0][m+1]=m+1;
for (int i=1;i<=m;i++)o[i]=o[i-1]+(f[0][i]==i);
for (int j=1;j<20;j++)
for (int i=1;i<=m+1;i++)
f[j][i]=f[j-1][f[j-1][i]];
for (int i=1,l,r;i<=q;i++){
l=rd();r=rd();
print(qry(l,r));putc('\n');
}flush();return 0;
}
```