Problem

V 君、I 君、和 Y 君是好朋友。

I 君最近开了一家商店，商店里准备了 (n) 种物品（编号为 (0sim n-1) 中的整数），每种物品均有无限个可供出售，每种物品的单价是 (0) 或者 (1)。

V 君想知道每个物品的价格，他已经通过某种超自然力量知道，这 (n) 个物品里，价格是 (1) 的物品恰好有奇数/偶数个，且 至少存在一个物品的价格是 (1)。

然而， V 君并不想自己去问 I 君，他选择了这样一种方法：他准备了 (+infty) 的钱给 Y 君。然后让 Y 君帮他跑腿：每一次，他会给 Y 君指定两个非空物品 集合 (S,T)（同一个集合内的物品必须两两不同，即每种物品在每个集合类最多包含一个），Y 君会跑到商店，分别买下这两个集合的物品，把他们送回来，并告诉 V 君哪个集合的物品价格之和更高。但是，当 两集合价格之和相等 的时候，Y 君会按照 I 君的指示来回答 V 君。（博主解释一下：就相当于返回任意一种情况，可以是最坏情况）

带着很多物品跑腿是一个很累的事情，因此，我们定义一次跑腿的体力消耗是 (|S|+|T|)（(|S|,|T|) 表示集合大小）。

你的任务是：写一个程序，帮助 V 君决定如何合理地让 Y 君跑腿，从而推算出每种物品的价值。Y 君的体力有限，你当然不能让他过于劳累，也即，你不能让他的总体力消耗超过某个预设的阈值 (m)。

需要实现：

void find_price(int task_id, int n, K, int ans[]);

(m task\_id) 表示子任务标号，(n) 如上，(K) 表示价格为 (1) 的物品，若为奇数则 (=1)，若为偶数则 (=0)。

你可以调用

int query(int S[], int nS, int T[], int nT)

其中 ({m nS}=|S|)，({m nT}=|T|)。如果 (S) 中价格总和更大，返回 (0)；如果 (T) 中价格总和更大，返回 (1)；否则返回任意值（(0) 或者 (1) 均可）。

多组数据。

• 子任务 1：(nle 5)，(mle 100)；
• 子任务 2：(nle 10^3)，(mle 10^6)；
• 子任务 3：(nle 10^5)，(mle 100)，保证 (forall i<j<k)，若 (ans_i=ans_k)，则必有 (ans_j=ans_i)；
• 子任务 4：(nle 10^4)，(mle 2 imes 10^5)；
• 子任务 5：(nle 5 imes 10^4)，(mle 350100)；
• 子任务 6：(nle 10^5)，(mle 500100)。

Sol

博主花了不少时间才切此题，在这里写一写“心动历程”～～

第一下想到要先找一个 (1)，然后拿这个 (1) 做事嘿嘿…

有一个很粗暴的想法：分治一下，假设区间 ([l,r]) 中含有 (1)，然后选取一个 (mid)，判断 ([l,mid]) 和 ([mid+1,r]) 中谁的 (1) 多，每次往多的部分走，最后总能找到 (1)。这样的代价约为 (2n)。

(1) 能做什么？能判断出来一个集合 (>1)，或者 (<1)。但如何知道其是否 (=1)？

非常悲观的一件事是：我们无法简单通过比较大小得知。即使我们拥有无穷多的 (1)，通过二分，每次取出来 (a) 个 (1)，与 (S) 比较，最终停止，只能推断出 ({m val}(S)in{b,b+1})，想确定其是 (b) 还是 (b+1) 我们无能为力。

但，注意到这样的一件事：({m val}(S)+{m val}(T)in{c,c+1,c+2})（同向不等式的合并），({m val}(Scup T)in{d,d+1})，发现分开查询和合并查询可以推断出一种不存在的情况。这并没有什么用，但至少启迪我们 要利用集合间的关系去寻找答案，而不是去揣摩它真正的取值是多少。

想象一下 (n=2)，你只有 ({1,x})。发现 (x) 的取值光靠查询是查不出来的，所以出题人良心地给了 (K)，根据 (1) 数量的奇偶性推出来 (x)。

想象一下 (n=3)，你只有 ({1,x,y})，这次奇偶性不能直接救你，你必须至少知道 (x) 和 (y) 中至少一个的 真实取值，最后才能利用奇偶性得出答案。幸运的是，我们可以做到！

构造两次查询：(({x},{y})) 和 (({1},{x,y}))。前者知道 (x)、(y) 的大小关系，后者若返回 (0)，则 (x) 和 (y) 中 必然有一个 (0)，若返回 (1) 则 (x) 和 (y) 中 必然有一个 (1)！

假设 (xle y)，若含有 (0)，则 (x) 必为 (0)；若含有 (1)，则 (y) 必为 (1)！

可喜可贺！我们找出了一个通用的做法：每次找出来两个未知情况的数 (x,y)，每次花费 (5) 的代价确定二者中的一个数的真正取值。未知的数字有 (n-1) 个，我们需要使用这个方法 (n-2) 次，直到剩余最后一个不知道答案的数字，再利用奇偶性就能得到答案了！这部分操作次数约为 (5n)。

加上找 (1)，总共需要 (7n) 次左右。发现能过掉子任务 1、2、4、5，加起来有 57 Pts。这个 子任务 3 是咋回事啊？看起来很需要二分！

通过比较 (0) 号和 (n-1) 号元素可以得到 (1) 在哪里，以及序列的顺序（(0ightarrow 1) 或者 (1ightarrow 0)）。这里假设顺序 (0ightarrow 1)。同样我们可以通过 (({1},{ans_x,ans_{x+1}}))，由于 (ans_xle ans_{x+1})，我们不仅能知道谁为 (0) 谁为 (1)，而且还能知道接下来二分的方向。最后仍然不确定一个元素，根据奇偶性查出来即可。操作次数约为 (3log n)。

此时就有 69 Pts 了，我们应该选择跑路继续想一想 (7n) 做法的瓶颈，如果我们能够去掉那个 (2n) 的找 (1) 过程就好了。可不可以不需要 (1)？把 (({1},{x,y})) 使用 (({a},{x,y})) 代替（(a) 是随便挑的，可能为 (0)，可能为 (1)）？

我们来分析一下 (({0},{x,y})) 的影响（也就是我们把 (0) 当成 (1) 来看，结果的偏差），这里仍然让 (xle y)。如果返回值为 (0)，我们会把 (x) 当 (0)，这一步在换成 (0) 也没有影响；但如果返回值为 (1)，我们会把 (y) 当成 (1)，但事实上 (y) 也可以为 (0) 了。

接下来的想法就很巧妙了！我们假设查询的结果为 (1)，仍然把 (y) 看成 (1)，并且将 (a) 换成 (y)，往后继续操作。把曾经的 (a) 按照顺序构成序列，发现它们按照 真实值 是单调的！

这值得我们惊呼！最后再对着这个序列做 子任务 3，把真实值求出来，是不是就只剩下一个数字不确定了？利用奇偶性！做完了！总操作次数约为 (5n+3log n)。

实现细节请诸位小心，别像我一样过了后 5 个 subtask 挂了 1。

#include <bits/stdc++.h>
#include "shop.h"
#define pb push_back
const int N = 5e5 + 5;
int S[N], T[N];
int qry1(int a, int b) {
	S[0] = a, T[0] = b;
	return query(S, 1, T, 1);
}
int qry2(int a, int b, int c) {
	S[0] = a, T[0] = b, T[1] = c;
	return query(S, 1, T, 2);
}
std::vector<int> vec;
void find_price(int task_id, int n, int K, int ans[]) {
	vec.clear();
	if (task_id == 3) {
		int now = qry1(0, n - 1) ? n - 1 : 0;
		ans[now] = 1;
		for (int i = 0; i < n; i++)
			if (i != now) vec.pb(i);
		if (now == 0) std::reverse(vec.begin(), vec.end());
		int l = 0, r = vec.size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (qry2(now, vec[mid], vec[mid + 1])) r = mid; else l = mid + 1;
		}
		for (int i = 0; i < l; i++) ans[vec[i]] = 0;
		for (int i = l + 1; i < n - 1; i++) ans[vec[i]] = 1;
		int sum = n - l - 1;
		ans[vec[l]] = (sum & 1) ^ K;
	} else {
		int now = 0, tmp = 0;
		for (int i = 1; i < n; i++) {
			int x = tmp, y = i;
			if (!qry1(x, y)) std::swap(x, y);
			if (qry2(now, x, y)) {
				ans[y] = 1; tmp = x;
				vec.pb(now), now = y;
			} else {
				ans[x] = 0; tmp = y;
			}
		}
		if (qry1(now, tmp)) vec.pb(now), now = tmp;
		ans[now] = 1;
		for (int i = 1; i < vec.size(); i++)
			if (vec[i] == 0) { vec.erase(vec.begin() + i); break; }
		int l = 0, r = vec.size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (qry2(now, vec[mid], vec[mid + 1])) r = mid; else l = mid + 1;
		}
		for (int i = 0; i < l; i++) ans[vec[i]] = 0;
		for (int i = l + 1; i < vec.size(); i++) ans[vec[i]] = 1;
		if (tmp != now) {
			int x = vec[l], y = tmp;
			if (x != y) {
				if (!qry1(x, y)) std::swap(x, y);
				if (qry2(now, x, y)) ans[y] = 1, tmp = x;
				else ans[x] = 0, tmp = y;
			}
		}
		else if (vec.size()) tmp = vec[l];
		int sum = 0;
		for (int i = 0; i < n; i++)
			if (i != tmp) sum += ans[i];
		ans[tmp] = (sum & 1) ^ K;
	}
}