CF1217F. Forced Online Queries Problem

发表于 分类于

https://codeforces.com/contest/1217/problem/F

题目大意

有$n$个点无向图，要进行$m$次操作，操作如下：

  • 1 x y，表示修改操作，如果当前有$(x,y)$这条边就删掉，否则加上。
  • 2 x y，询问$x,y$在不在一个联通块中。

注意强制在线，每个参数都要改成$(x+last-1)\bmod n+1$，注意$last$为$0/1$。

题解

注意到每个询问只有可能是两种情况。

考虑对询问按时间分块，我们一个块一个块的处理答案。

那么假设我们处理出了前面的块的答案，并求出了一个图，那么我们把所有这个块可能出现修改的边删掉，然后每个连通块缩成一个点，在把边连回去，这时候这个图的大小就是块的大小了，所以所有操作我们都暴力就行了。

实现的时候我们可以在每个块开始的时候重构一遍图，我的实现方法是用$\rm set$去维护连边情况，并查集维护联通情况，所以假设块的大小为$B$，复杂度就是$O(mB+\frac{m}{B}n\log n)$，两项相等时最小，所以$B=\sqrt{n\log n}$，总复杂度就是：$O(m\sqrt{n\log n})$。

注意到$mB$这一项实际上是有一个$4$的常数的，因为每个操作会涉及四个点，所以写代码的时候要把$B$定成$\frac{1}{2}\sqrt{n\log n}$才能通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
const int B = 700;
 
int n,m;
struct Q {int op,x,y,lst;}a[maxn];
 
int id[maxn],fa[maxn],top,rev[maxn];
set<int > e[maxn];
multiset<int > c[maxn];
pii sta[maxn];
 
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
 
int find(set<int > &s,int y) {
    auto i=s.lower_bound(y);
    if(i==s.end()||*i!=y) return 0;
    return 1;
}
 
int find(multiset<int > &s,int y) {
    auto i=s.lower_bound(y);
    if(i==s.end()||*i!=y) return 0;
    return 1;
}
 
void link(int x,int y) {
    x=find(x),y=find(y);
    if(x!=y) fa[x]=y;
}
 
int inc(int x) {return x%n+1;}
 
void rebuild(int t) {
    for(int i=1;i<=n;i++) c[i].clear();top=0;
    auto make=[&](int x,int y) {
                  if(find(e[x],y)) e[x].erase(y),e[y].erase(x),sta[++top]=mp(x,y);
              };
    for(int i=t+1;i<=t+B;i++)
        if(a[i].op==1) make(inc(a[i].x),inc(a[i].y)),make(a[i].x,a[i].y);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) for(auto x:e[i]) link(i,x);
    for(int i=1;i<=top;i++) {
        int x=find(sta[i].fr),y=find(sta[i].sc);
        if(x!=y) c[x].insert(y),c[y].insert(x);
    }
    for(int i=1;i<=top;i++) {
        int x=sta[i].fr,y=sta[i].sc;
        e[x].insert(y),e[y].insert(x);
    }
    
}
 
int use[maxn],vis[maxn],uu;
 
void dfs(int x) {
    vis[x]=1;use[++uu]=x;
    for(auto v:c[x]) if(!vis[v]) dfs(v);
}
 
int main() {
    read(n),read(m);
    for(int i=1;i<=m;i++) read(a[i].op),read(a[i].x),read(a[i].y);
    int lst=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) {
        a[i].lst=lst;
        int u=(a[i].x+lst-1)%n+1,v=(a[i].y+lst-1)%n+1;
        int x=find(u),y=find(v);
        if(a[i].op==1) {
            if(find(e[u],v)) {
                auto pps=c[x].lower_bound(y);
                c[x].erase(pps);pps=c[y].lower_bound(x);
                c[y].erase(pps);e[u].erase(v),e[v].erase(u);
            } else c[x].insert(y),c[y].insert(x),e[u].insert(v),e[v].insert(u);
        } else {
            dfs(x);if(vis[y]) lst=1;else lst=0;putchar(lst+'0');
            for(int j=1;j<=uu;j++) vis[use[j]]=0;uu=0;
        }
        if(i%B==0) rebuild(i);
    }
    return 0;
}