#P4605. 崂山白花蛇草水

    ID: 1362 传统题 5000ms 512MiB 尝试: 810 已通过: 138 难度: 9 上传者: 标签>难度分类省选/NOI-数据结构动态开点线段树线段树上二分K-D Tree按维度中位数划分包围盒剪枝离线与分治二进制分组重构CF2600

崂山白花蛇草水

崂山白花蛇草水

题目描述

Aleph 兑现了喝崂山白花蛇草水的诺言,Bob 又提出了一个问题。Bob 在平面整点堆放饮料,每堆的瓶数就是该点的权值。

平面初始为空。每次可以在一个整点添加一个正整数权值,或者查询一个包含边界的矩形中,已放置的整点权值按从大到小排列后的第 kk 项。每次放置的权值独立参与排名,相同权值也分别计数。原题约定每个整点最多放置一次,本题库的部分数据在同一整点有多次放置。

输入格式

第一行两个正整数 n,qn,q,表示横纵坐标的上限和操作次数。接下来 qq 行,每行描述一个操作。

  • 1 x y v 表示在 (x,y)(x,y) 放置一个权值为 vv 的点。
  • 2 x1 y1 x2 y2 k 表示查询 x1≤x≤x2x_1\le x\le x_2 且 y1≤y≤y2y_1\le y\le y_2 的范围内第 kk 大的权值。

除第一行和每个操作开头的操作类型外,读取的每个参数都要与 lastans\mathrm{lastans} 按位异或,得到参数的实际值。lastans\mathrm{lastans} 初始为 00。每次查询输出整数后,令 lastans\mathrm{lastans} 等于该整数。若查询失败,则将 lastans\mathrm{lastans} 置为 00。插入操作不改变 lastans\mathrm{lastans}。

输出格式

每次查询输出一行。若存在第 kk 大的权值,输出该值。否则输出 NAIVE!ORZzyz.。

10 7
1 1 1 1
1 2 2 3
1 4 1 2
1 3 4 4
2 1 1 4 1 3
2 2 2 3 5 4
2 2 1 4 4 2
NAIVE!ORZzyz.
NAIVE!ORZzyz.
3

数据范围

1≤n≤5000001\le n\le500000,1≤x,y≤n1\le x,y\le n,1≤v≤1091\le v\le10^9,1≤x1≤x2≤n1\le x_1\le x_2\le n,1≤y1≤y2≤n1\le y_1\le y_2\le n,1≤k≤q1\le k\le q。

测试点 qq
1–2 1000
3–7 50000
8–12 100000

题意由 Aleph 提出,题面与测试数据由 jinlifu1999 提供。