306583: CF1217F. Forced Online Queries Problem
Memory Limit:256 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Forced Online Queries Problem
题意翻译
### 题目描述 给你一个有$n$个点的无向图,点的编号从$1$到$n$,最初图中没有边 给定两种操作: - $1\ x\ y(1\le n,x\neq y)$如果在点$(x+lstans-1)mod\ n+1$与边$(y+lstans-1)mod\ n+1$之间有边,则删,无边则加 - $2\ x\ y(1\le x,y \le n,x\neq y)$检查点$(x+lstans-1)mod\ n+1$与点$(y+lstans-1)mod\ n+1$之间的连通性,联通则输出1,否则输出0 (这里定义$lastans$为上一次操作$2$的结果,特别的,在第一次操作$2$之前,$lastans=0$) ### 输入格式 第一行输入两个整数$n,m(2\le n,m\le 2\cdot 10^5)$,$n$代表点的个数,而$m$代表操作的个数 接下来有$m$行,具体格式如题目描述中所写(保证有至少一次操作$2$) ### 输出格式 对于每一个操作$2$,输出一个整数,为这个询问的答案(不用空格隔开) ### 说明/提示 对于样例$1$,输入所代表的实际询问如下: - 1 1 2 - 1 1 3 - 2 3 2 - 1 3 5 - 2 4 5 - 1 2 4 - 2 3 4 - 1 2 4 - 2 5 4 对于样例$2$,输入所代表的实际询问如下: - 1 1 2 - 1 2 3 - 1 3 1 - 2 1 3 - 1 1 3 - 2 3 1 - 1 2 3 - 2 2 3 - 2 1 2题目描述
You are given an undirected graph with $ n $ vertices numbered from $ 1 $ to $ n $ . Initially there are no edges. You are asked to perform some queries on the graph. Let $ last $ be the answer to the latest query of the second type, it is set to $ 0 $ before the first such query. Then the queries are the following: - $ 1~x~y $ ( $ 1 \le x, y \le n $ , $ x \ne y $ ) — add an undirected edge between the vertices $ (x + last - 1)~mod~n + 1 $ and $ (y + last - 1)~mod~n + 1 $ if it doesn't exist yet, otherwise remove it; - $ 2~x~y $ ( $ 1 \le x, y \le n $ , $ x \ne y $ ) — check if there exists a path between the vertices $ (x + last - 1)~mod~n + 1 $ and $ (y + last - 1)~mod~n + 1 $ , which goes only through currently existing edges, and set $ last $ to $ 1 $ if so and $ 0 $ otherwise. Good luck!输入输出格式
输入格式
The first line contains two integer numbers $ n $ and $ m $ ( $ 2 \le n, m \le 2 \cdot 10^5 $ ) — the number of vertices and the number of queries, respectively. Each of the following $ m $ lines contains a query of one of two aforementioned types. It is guaranteed that there is at least one query of the second type.
输出格式
Print a string, consisting of characters '0' and '1'. The $ i $ -th character should be the answer to the $ i $ -th query of the second type. Therefore the length of the string should be equal to the number of queries of the second type.
输入输出样例
输入样例 #1
5 9
1 1 2
1 1 3
2 3 2
1 2 4
2 3 4
1 2 4
2 3 4
1 1 3
2 4 3
输出样例 #1
1010
输入样例 #2
3 9
1 1 2
1 2 3
1 3 1
2 1 3
1 3 2
2 2 3
1 1 2
2 1 2
2 1 2
输出样例 #2
1101