P3302 [SDOI2013]森林

    • 370通过
    • 2.1K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 主席树 深度优先搜索,DFS 线段树 2013 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

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

    推荐的相关题目 显示

    题目描述

    小Z有一片森林,含有N个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有M条边。

    小Z希望执行T个操作,操作有两类:

    1. Q x y k查询点x到点y路径上所有的权值中,第k小的权值是多少。此操作保证点x和点y连通,同时这两个节点的路径上至少有k个点。
    2. L x y在点x和点y之间连接一条边。保证完成此操作后,仍然是一片森林。

    为了体现程序的在线性,我们把输入数据进行了加密。设lastans为程序上一次输出的结果,初始的时候lastans为0。

    • 对于一个输入的操作Q x y k,其真实操作为Q x^lastans y^lastans k^lastans
    • 对于一个输入的操作L x y,其真实操作为L x^lastans y^lastans。其中^运算符表示异或,等价于pascal中的xor运算符。

    请写一个程序來帮助小Z完成这些操作。

    对于所有的数据,n,m,T<= $8*10^4$ .

    输入输出格式

    输入格式:

    第一行包含一个正整数testcase,表示当前测试数据的测试点编号。保证1<=testcase<=20。

    第二行包含三个整数N,M,T,分别表示节点数、初始边数、操作数。

    第三行包含N个非负整数表示 N个节点上的权值。

    接下来 M行,每行包含两个整数x和 y,表示初始的时候,点x和点y 之间有一条无向边。

    接下来 T行,每行描述一个操作,格式为”Q x y k“或者”L x y “,其含义见题目描述部分。

    输出格式:

    对于每一个第一类操作,输出一个非负整数表示答案。

    输入输出样例

    输入样例#1: 复制
    1
    8  4 8
    1  1 2 2 3 3 4 4
    4  7
    1  8
    2  4
    2  1
    Q 8 7 3 Q 3 5 1
    Q 10 0 0
    L 5 4
    L 3 2 L 0 7
    Q 9 2 5 Q 6 1 6
    输出样例#1: 复制
    2 
    2
    1
    4
    2

    说明

    对于第一个操作 Q 8 7 3,此时 lastans=0,所以真实操作为Q 8^0 7^0 3^0,也即Q 8 7 3。点8到点7的路径上一共有5个点,其权值为4 1 1 2 4。
    这些权值中,第三小的为 2,输出 2,lastans变为2。

    对于第二个操作 Q 3 5 1 ,此时lastans=2,所以真实操作为Q 3^2 5^2 1^2 ,也即Q 1 7 3。点1到点7的路径上一共有4个点,其权值为 1 1 2 4 。
    这些权值中,第三小的为2,输出2,lastans变为 2。之后的操作类似。

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