[CF1386C] Joker （IOI 赛制，分治，整体二分+可回退并查集）
题面
给一个
N
N
N 点
M
M
M 边的简单无向图，询问
Q
Q
Q 次，每次问你把编号在
[
l
i
,
r
i
]
[l_i,r_i]
[li,ri] 之间的边删掉后，该图是否存在奇数环，即是否不能被二染色。
1
≤
N
,
M
,
Q
≤
200000
1\leq N,M,Q\leq 200000
1≤N,M,Q≤200000.
题解
看了半天才搞懂官解里的奇怪分治是什么，其实就是整体二分嘛！
部分分就不多赘述了，大概就是一步步引导我们到正解的整体二分+可回退并查集（官解称其为：DSU）上。
并查集是经典的解决二染色问题的方法了，每个点存一个值表示自己和父亲的颜色是否不同(0/1)，再存一个集合大小，然后用启发式合并保证每次只变动一条边，最后用一个栈来存每次加的边，以备回退之需。
我们发现答案具有包含性，即：若询问为
[
l
,
r
]
[l,r]
[l,r] 时答案是 YES，那么
[
l
′
,
r
′
]
[l',r']
[l′,r′] （
[
l
′
,
r
′
]
⊂
[
l
,
r
]
[l',r']\sub[l,r]
[l′,r′]⊂[l,r]）的答案也是 YES ，这个易证，因为能形成奇数环的边都还在。
再换一种思路，我们令
m
a
x
r
[
i
]
maxr[i]
maxr[i] 为区间左端点 l=i+1，满足答案是 YES 的最大右端点编号 +1（即此时
[
1
,
i
]
∪
[
m
a
x
r
[
i
]
,
M
]
[1,i]\cup[maxr[i],M]
[1,i]∪[maxr[i],M] 以内的边都保留）。那么对于一个询问
[
l
,
r
]
[l,r]
[l,r] 当且仅当
m
a
x
r
[
l
−
1
]
>
r
maxr[l-1]>r
maxr[l−1]>r 时答案为 YES。同时，由于之前的包含性，我们可以发现
i
<
j
⇒
m
a
x
r
[
i
]
≤
m
a
x
r
[
j
]
i<j\Rightarrow maxr[i]\leq maxr[j]
i<j⇒maxr[i]≤maxr[j]
即：
m
a
x
r
[
i
]
maxr[i]
maxr[i] 单调不降！
为了配合可回退并查集，具体地，我们这样分治：
- s
o
l
v
e
(
l
1
,
r
1
,
l
2
,
r
2
)
solve(l_1,r_1,l_2,r_2)
solve(l1,r1,l2,r2)，四个参数，分别表示两个区间：要求的标号区间
[
l
1
,
r
1
]
[l_1,r_1]
[l1,r1]，以及通过之前的计算已经确定的该区间内针对所有位置
m
a
x
r
maxr
maxr 的范围
[
l
2
,
r
2
]
[l_2,r_2]
[l2,r2]。为配合并查集，操作前得保证前提条件：
l
1
l_1
l1 左边的边和
r
2
r_2
r2 右边的边都已经加入并查集。
- 整体二分常规程序，先取
m
i
d
1
=
⌊
l
1
+
r
1
2
⌋
mid_1=\lfloor\frac{l_1+r_1}{2}\rfloor
mid1=⌊2l1+r1⌋，然后把
[
l
1
,
m
i
d
1
]
[l_1,mid_1]
[l1,mid1] 的边都加上，再从
r
2
r_2
r2 开始往前加边，直到存在奇数环，即求出了
m
a
x
r
[
m
i
d
1
]
maxr[mid_1]
maxr[mid1]。
- 令
m
i
d
2
=
m
a
x
r
[
m
i
d
1
]
mid_2=maxr[mid_1]
mid2=maxr[mid1]，那么我们可以往下转移了，我们知道
[
l
1
,
m
i
d
1
−
1
]
[l_1,mid_1-1]
[l1,mid1−1] 的
m
a
x
r
maxr
maxr 一定在
[
l
2
,
m
i
d
2
]
[l_2,mid_2]
[l2,mid2] 以内，以及
[
m
i
d
1
+
1
,
r
1
]
[mid_1+1,r_1]
[mid1+1,r1] 的
m
a
x
r
maxr
maxr 一定在
[
m
i
d
2
,
r
2
]
[mid_2,r_2]
[mid2,r2] 以内。
- 递归
s
o
l
v
e
(
m
i
d
1
+
1
,
r
1
,
m
i
d
2
,
r
2
)
solve(mid_1+1,r_1,mid_2,r_2)
solve(mid1+1,r1,mid2,r2) 。此前暴力回退、加边使之满足前提条件。
- 递归
s
o
l
v
e
(
l
1
,
m
i
d
1
−
1
,
l
2
,
m
i
d
2
)
solve(l_1,mid_1-1,l_2,mid_2)
solve(l1,mid1−1,l2,mid2)。同理。
递归到边界就不用多说了吧。
时间复杂度
O
(
M
log
2
M
+
Q
)
O(M\log^2M+Q)
O(Mlog2M+Q)。
CODE
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
int U[MAXN],V[MAXN];
vector<int> g[MAXN];
int fa[MAXN],ds[MAXN],siz[MAXN];
int findd(int x) {if(x == fa[x]) return 0;return findd(fa[x])^ds[x];}
int findf(int x) {return x==fa[x] ? x:findf(fa[x]);}
vector<int> st;
bool unionSet(int a,int b) {
int u = findf(a),v = findf(b);
if(siz[u] > siz[v]) swap(u,v),swap(a,b);
int d1 = findd(a),d2 = findd(b);
if(u == v) {
return d1 ^ d2;
}
if(d1 == d2) ds[u] = 1;
else ds[u] = 0;
siz[v] += siz[u]; fa[u] = v;
st.push_back(u);
return 1;
}
void POP() {
int u = st.back(); st.pop_back();
int v = fa[u];
ds[u] = 0; siz[v] -= siz[u];
fa[u] = u; return ;
}
int maxr[MAXN];
int li[MAXN],ri[MAXN];
void solve(int l,int r,int l2,int r2) {
if(l > r || l2 > r2) return ;
if(l2 == r2) {
for(int i = l;i <= r;i ++) maxr[i] = l2;
return ;
}
int mid = (l + r) >> 1,le = (int)st.size(),rr = max(l2,mid-1);
int flag = 0;
for(int i = l;i <= mid;i ++) if(i) flag |= 1^unionSet(U[i],V[i]);
int le2 = (int)st.size();
if(flag) rr = r2;
for(int i = min(r2,m);i > mid && i >= l2 && i > rr;i --) {
flag |= 1^unionSet(U[i],V[i]);
if(flag) {rr = i;break;}
}
maxr[mid] = rr;
while((int)st.size() > le2) POP();
solve(mid+1,r,rr,r2);
while((int)st.size() > le) POP();
for(int i = min(r2,m);i >= rr;i --) unionSet(U[i],V[i]);
solve(l,mid-1,l2,rr);
while((int)st.size() > le) POP();
return ;
}
int main() {
n = read();m = read();int Q = read();
for(int i = 1;i <= m;i ++) {
s = read();o = read();
g[s].push_back(o);
g[o].push_back(s);
U[i] = s; V[i] = o;
}
int rr = 0;
for(int i = 1;i <= Q;i ++) li[i] = read(),ri[i] = read(),rr = max(li[i],rr);
for(int i = 1;i <= n;i ++) fa[i] = i,ds[i] = 0,siz[i] = 1;
solve(0,m,0,m+1);
for(int i = 1;i <= Q;i ++) {
s = li[i];o = ri[i];
if(maxr[s-1] > o) printf("YES\n");
else printf("NO\n");
}
return 0;
}
最新文章
- ORA-00494: enqueue [CF] held for too long (more than 900 seconds) by 'inst 1, osid 5166'
- 大型网站提速关键技术(页面静态化,memcached,MySql优化)(三)
- Ext.Net 学习随笔 003 Panel基本使用
- TW2015技术雷达中文版发布
- Windows 下用 gogs 配置局域网 git server
- lib3ds类库
- 请问用Inno_Setup打包文件夹时怎么排除其中一个文件？
- SQL日志文件的作用
- 学习了几天的jQuery Mobile的一点感受
- 切割 bitmap
- Unity 制作虚拟手柄例子
- differ比较两个字符串的差异
- Cocos2d-x 3.1.1开发环境
- js中的整型都是用double存储的，有时候不精确，如，
- P4语言编程快速开始 实践一
- jquery通过ajax向后台发送（checkbox）数组，并在后台接收，（发送的数据是checkedbox）
- 阿里云Prismplayer-Web播放器的使用
- sass 安装与使用
- python使用
- JavaScript变量声明var,let.const