CF1903F 题解
sunkuangzheng
·
·
题解
考虑 k 固定的时候怎么做。
题目中的限制可以转化为两条：
你发现这个问题很 2-sat，但是边数是 \mathcal O(nk) 级别的。又发现每次连边是单点连边，或者点向区间连边，线段树优化建图即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 6e5+5;vector<pair<int,int>> gr;
int t,n,m,u,v,dfn[N],low[N],vis[N],st[N],be[N],tp,ti,tot;vector<int> g[N];
int id(int u,int x){return u + 4 * n + n * x;}
void add(int u,int v){return g[u].push_back(v);}
void build(int s,int l,int r){
if(l == r) return add(s,id(l,0));int mid = (l + r) / 2;
build(s*2,l,mid),build(s*2+1,mid+1,r),
g[s].push_back(s*2),g[s].push_back(s*2+1);
}void upd(int s,int l,int r,int ql,int qr,int k){
if(qr < ql || ql <= 0 || qr > n) return ;
if(ql <= l && r <= qr) return add(id(k,1),s);
int mid = (l + r) / 2;
if(ql <= mid) upd(s*2,l,mid,ql,qr,k); if(qr > mid) upd(s*2+1,mid+1,r,ql,qr,k);
}void tarjan(int u){
low[u] = dfn[u] = ++ti,st[++tp] = u,vis[u] = 1;
for(int v : g[u]) if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]); else if(vis[v]) low[u] = min(low[u],dfn[v]);
if(low[u] == dfn[u]) for(++tot;;) if(be[st[tp]] = u,vis[st[tp]] = 0,st[tp --] == u) break;
}bool ck(int mid){
for(int i = 1;i <= 6*n;i ++) g[i].clear(),dfn[i] = low[i] = vis[i] = 0;ti = tot = tp = 0;
build(1,1,n);
for(auto [u,v] : gr) add(id(u,0),id(v,1)),add(id(v,0),id(u,1));
for(int i = 1;i <= n;i ++){
int l = i - mid + 1,r = i + mid - 1;
upd(1,1,n,max(l,1),i-1,i),upd(1,1,n,i+1,min(r,n),i);
}for(int i = 1;i <= 6 * n;i ++) if(!dfn[i]) tarjan(i);
for(int i = 1;i <= n;i ++) if(be[id(i,0)] == be[id(i,1)]) return 0;
return 1;
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> t;
while(t --){
cin >> n >> m,gr.clear();
for(int i = 1;i <= m;i ++) cin >> u >> v,gr.emplace_back(u,v);
int l = 1,r = n;
while(l <= r){
int mid = (l + r) / 2;
if(ck(mid)) l = mid + 1; else r = mid - 1;
}cout << l - 1 << "\n";
}
}
```