P3302 [SDOI2013]森林

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

题解

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

    推荐的相关题目 显示

    题目背景

    如果你能提供题面或者题意简述,请直接在讨论区发帖,感谢你的贡献。

    题目描述

    给一个森林,森林有n个节点m条边。

    现在有两种操作:

    1.Q x y k 表示询问x-y这条链上点权的第k小。保证x,y在同一个连通块里。

    2.L x y 表示链接x,y两点。保证x,y在不同的连通块里。

    总共有T次操作,要求强制在线,last表示上一次的答案,每次x,y,k都要异或last.last初始为0.

    对于所有的数据,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类违反进行处理。