P2137 Gty的妹子树

    • 230通过
    • 1.6K提交
  • 题目提供者 YuMiko_Stereo
  • 评测方式 云端评测
  • 标签 平衡树 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    我曾在弦歌之中听过你,

    檀板声碎,半出折子戏。

    舞榭歌台被风吹去,

    岁月深处尚有余音一缕……

    Gty神(xian)犇(chong)从来不缺妹子……

    他来到了一棵妹子树下,发现每个妹子有一个美丽度……

    由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。

    他想知道某个子树中美丽度大于k的妹子个数。

    某个妹子的美丽度可能发生变化……

    树上可能会出现一只新的妹子……

    题目描述

    维护一棵初始有n个节点的有根树(根节点为1),树上节点编号为1-n,每个点有一个权值wi。

    支持以下操作:

    0 u x 询问以u为根的子树中,严格大于x的值的个数。(u^=lastans,x^=lastans)

    1 u x 把u节点的权值改成x。(u^=lastans,x^=lastans)

    2 u x 添加一个编号为"当前树中节点数+1"的节点,其父节点为u,其权值为x。(u^=lastans,x^=lastans)

    最开始时lastans=0。

    输入输出格式

    输入格式:

    输入第一行包括一个正整数n(1<=n<=30000),代表树上的初始节点数。

    接下来n-1行,每行2个整数u,v,为树上的一条无向边。

    任何时刻,树上的任何权值大于等于0,且两两不同。

    接下来1行,包括n个整数wi,表示初始时每个节点的权值。

    接下来1行,包括1个整数m(1<=m<=30000),表示操作总数。

    接下来m行,每行包括三个整数 op,u,x:

    op,u,x的含义见题目描述。

    保证题目涉及的所有数在int内。

    输出格式:

    对每个op=0,输出一行,包括一个整数,意义见题目描述。

    输入输出样例

    输入样例#1: 复制
    2
    1 2
    10 20
    1
    0 1 5
    
    输出样例#1: 复制
    2
    
    输入样例#2: 复制
    2
    1 2
    10 20
    1
    0 1 10
    
    输出样例#2: 复制
    1
    

    说明

    时间限制每个测试点1s

    空间限制128M

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