TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5474
  • 题目
  • P5474火星商店问题
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s,512m
    问题描述

    火星上的一条商业街里按照商店的编号1,2 ,…,n ,依次排列着n个商店。商店里出售的琳琅满目的商品中,每种商品都用一个非负整数val来标价。每个商店每天都有可能进一些新商品,其标价可能与已有商品相同。
    火星人在这条商业街购物时,通常会逛这条商业街某一段路上的所有商店,譬如说商店编号在区间[L,R]中的商店,从中挑选1件自己最喜欢的商品。每个火星人对商品的喜好标准各不相同。通常每个火星人都有一个自己的喜好密码x。对每种标价为val的商品,喜好密码为x的火星人对这种商品的喜好程度与val异或x的值成正比。也就是说,val xor x的值越大,他就越喜欢该商品。每个火星人的购物卡在所有商店中只能购买最近d天内(含当天)进货的商品。另外,每个商店都有一种特殊商品不受进货日期限制,每位火星人在任何时刻都可以选择该特殊商品。每个商店中每种商品都能保证供应,不存在商品缺货的问题。
    对于给定的按时间顺序排列的事件,计算每个购物的火星人的在本次购物活动中最喜欢的商品,即输出val xor x的最大值。这里所说的按时间顺序排列的事件是指以下2种事件:
    事件0,用三个整数0,s,v,表示编号为s的商店在当日新进一种标价为v 的商品。
    事件1,用5个整数1,L,R,x,d,表示一位火星人当日在编号为L到R的商店购买d天内的商品,该火星人的喜好密码为x。

    nodgd提示:每个事件0表示新的一天,与后面连续的事件1在同一天。

    输入格式

    第1行中给出2个正整数n,m,分别表示商店总数和事件总数。
    第2行中有n个整数,第i个整数表示商店i的特殊商品标价。
    接下来的m行,每行表示1个事件。每天的事件按照先事件0,后事件1的顺序排列。

    输出格式

    将计算出的每个事件1的val xor x的最大值依次输出。

    样例输入

    4 6
    1 2 3 4
    1 1 4 1 0
    0 1 4
    0 1 3
    1 1 1 1 0
    1 1 1 1 1
    1 1 2 1 2

    样例输出

    5
    0
    2
    5

    提示

    n, m <= 100000

    数据中,价格不大于100000