TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3270
  • 题目
  • P3270可持久化并查集
    限制 : 时间限制 : 10000 MS   空间限制 : 565536 KB
    问题描述

    一开始有n个整数集合,第k个集合是{k}。m次操作,操作有三种:
    1.把x所在集合与y所在集合并起来。如果本来就在一个集合就无视这个操作。
    2.回到第k次操作后的状态。如果k=0就是回到初始状态。
    3.查询x和y是否在同一个集合。如果在输出“1”,不在输出“0”。
    强制在线,假设现在是第M次操作,上一次答案是lastans,加密规则如下:
    1.输入xx,yy,则x=(xx-1+lastans12345)%n+1,y=(yy-1+lastans23456)%n+1。
    2.输入kk,则k=(kk+lastans*34567)%M。
    3.同1。

    输入格式

    第一行两个数n,m。
    接下来m行每行一个操作。

    输出格式

    每次查询输出一行答案。

    样例输入

    6 6
    1 1 3
    1 4 2
    3 4 3
    1 4 3
    3 2 3
    3 5 4

    样例输出

    0
    1
    0

    提示

    1<=n,m<=200000


    来源  感谢nodgd