P3690 【模板】Link Cut Tree (动态树)

    • 3.7K通过
    • 9.6K提交
  • 题目提供者 zcysky 白羽
  • 评测方式 云端评测
  • 标签 Link-Cut Tree,LCT 动态树 树链剖分,树剖 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    动态树

    题目描述

    给定n个点以及每个点的权值,要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

    0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

    1:后接两个整数(x,y),代表连接x到y,若x到y已经联通则无需连接。

    2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。

    3:后接两个整数(x,y),代表将点x上的权值变成y。

    输入输出格式

    输入格式:

    第1行两个整数,分别为n和m,代表点数和操作数。

    第2行到第n+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。

    第n+2行到第n+m+1行,每行三个整数,分别代表操作类型和操作所需的量。

    输出格式:

    对于每一个0号操作,你须输出x到y的路径上点权的xor和。

    输入输出样例

    输入样例#1: 复制
    3 3 
    1
    2
    3
    1 1 2
    0 1 2 
    0 1 1
    输出样例#1: 复制
    3
    1
    

    说明

    数据范围: $ 1 \leq N, M \leq 3 \cdot {10}^5 $

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。