P5354 [Ynoi2017]由乃的OJ

    • 466通过
    • 1.8K提交
  • 题目提供者 noip 毒瘤
  • 评测方式 云端评测
  • 标签 2017 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    题目描述

    由乃正在做她的OJ。现在她在处理OJ上的用户排名问题。

    OJ上注册了n个用户,编号为1~”,一开始他们按照编号排名。由乃会按照心情对这些用户做以下四种操作,修改用户的排名和编号:然而由乃心情非常不好,因为Deus天天问她题。。。

    因为Deus天天问由乃OI题,所以由乃去学习了一下OI,由于由乃智商挺高,所以OI学的特别熟练

    她在RBOI2016中以第一名的成绩进入省队,参加了NOI2016获得了金牌保送

    Deus:这个题怎么做呀?
    yuno:这个不是NOI2014的水题吗。。。
    Deus:那如果出到树上,多组链询问,带修改呢?
    yuno:诶。。。???
    Deus:这题叫做睡觉困难综合征哟~

    虽然由乃OI很好,但是她基本上不会DS,线段树都只会口胡,比如她NOI2016的分数就是100+100+100+0+100+100。。。NOIP2017的分数是100+0+100+100+0+100

    所以她还是只能找你帮她做了。。。

    给你一个有n个点的树,每个点的包括一个位运算opt和一个权值x,位运算有&,l,^三种,分别用1,2,3表示。

    每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点,每经过一个点i,v就变成v opti xi,所以他想问你,最后到y时,希望得到的值尽可能大,求最大值?给定的初始值v必须是在[0,z]之间。

    每次修改包含三个数x,y,z,意思是把x点的操作修改为y,数值改为z

    输入输出格式

    输入格式:

    第一行三个数n,m,k。k的意义是每个点上的数,以及询问中的数值z都 <2^k。之后n行,每行两个数x,y表示该点的位运算编号以及数值

    之后n - 1行,每行两个数x,y表示x和y之间有边相连

    之后m行,每行四个数,Q,x,y,z表示这次操作为Q(1位询问,2为修改),x,y,z意义如题所述

    输出格式:

    对于每个操作1,输出到最后可以造成的最大刺激度v

    输入输出样例

    输入样例#1: 复制
    5 5 3
    1 7
    2 6
    3 7
    3 6
    3 1
    1 2
    2 3
    3 4
    1 5
    1 1 4 7
    1 1 3 5
    2 1 1 3
    2 3 3 3
    1 1 3 2
    输出样例#1: 复制
    7
    1
    5
    输入样例#2: 复制
    2 2 2
    2 2
    2 2
    1 2
    2 2 2 2
    1 2 2 2
    输出样例#2: 复制
    3

    说明

    对于30%的数据,n,m <= 1

    对于另外20%的数据,k <= 5

    对于另外20%的数据,位运算只会出现一种

    对于100%的数据,0 <= n , m <= 100000 , k <= 64

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