【模板】Wavelet Matrix - 题目

内存限制：64 MiB 时间限制：8000 ms 标准输入输出

题目类型：VJudge（洛谷）评测方式：VJudge

上传者：匿名

提交提交记录统计讨论题解

请注意本题并不寻常的数据范围与时空限制。

给定一个长度为的序列。次查询，给定：

若，查询区间内有多少个数小于。
若，查询区间内第小的数。

强制在线。

由于 IO 量过大，数据使用随机生成。你可以使用以下方式获取以及每次询问的：

typedef unsigned uint;
const int MAXN = 4e6 + 10;
const uint mask = 0x5f3759dfu;

uint seed, lst;

inline uint rnd() {
	seed ^= lst ^ mask;
	seed ^= seed << 13;
	seed ^= seed >> 7;
	seed ^= seed << 17;
	seed ^= lst ^ mask;
	return seed;
}

int n, m; uint a[MAXN];

int main() {
    scanf("%d%d%u", &n, &m, &seed);
    for (int i = 1; i <= n; i++) a[i] = rnd();
    for (int i = 1; i <= m; i++) {
    	uint op = rnd() & 1, l = rnd() % n + 1, r = rnd() % n + 1;
    	if (l > r) swap(l, r);
    	if (op) {
    		uint k = rnd() % (r - l + 1) + 1;
    		// do sth...
		} else {
			uint k = rnd();
			// do sth...
		}
	}
}

其中表示上一次询问的答案，初始为。

一行一个非负整数，表示所有查询的答案的异或和。

样例输入 1

5 5 114514

样例输出 1

1562674565

样例输入 2

114 514 1919

样例输出 2

903488587

样例输入 3

5000 5000 998244353

样例输出 3

1845377756

样例输入 4

2000000 2000000 1004535809

样例输出 4

1498751009

样例输入 5

4000000 4000000 1000000007

样例输出 5

981318194

【样例 1 解释】

解密后的输入如下：

5 5
3453473247 1341133007 2686835293 4244725722 2878739094
0 3 5 4197138810
1 2 5 2
1 2 3 2
1 1 5 2
1 3 5 3

其中第一行为，第二行为，接下来行为询问。

【数据范围】

本题开启捆绑测试。

		分值

对于的数据，，。同一个 Subtask 内数据有梯度。

请注意常数因子对程序时空效率的影响。尤其注意与之间亦有分别。

编辑器加载中 …

或者，上传代码文件

Powered by SYZOJ. Modified by Zemu (UnratedCheater).

项目源码 · 陶片放逐 · 新ICP备2026003452号-2

当前版本：V1.7.2-premium

#215231. 【模板】Wavelet Matrix

题目描述

输入格式

输出格式

样例