前言

今天zty带来的是 P11234 [CSP-S 2024] 擂台游戏 ，大家给个赞呗，zty放寒假的更新呢是会多起来的大概一天三四个吧,zty最近在冲榜大家多加支持
先 赞 后 看 养 成 习 惯

先 赞 后 看 养 成 习 惯
演示用编译器及其标准
Dev C++ 6.7.5 Red panda C++14

正文

[CSP-S 2024] 擂台游戏

题目描述

小 S 想要举办一场擂台游戏，如果共有 $2^k$ 名选手参加，那么游戏分为 $k$ 轮进行：

• 第一轮编号为 $1,2$ 的选手进行一次对局，编号为 $3,4$ 的选手进行一次对局，以此类推，编号为 $2^k-1,2^k$ 的选手进行一次对局。
• 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
• 以此类推，第 $k-1$ 轮在只保留第 $k-2$ 轮的 $4$ 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
• 第 $k$ 轮即为半决赛两位胜者的决赛。

确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 $a_1,a_2,\dots ,a_{2^k}$，能力值为 $[0,2^{31}-1]$ 之内的整数。对于每场比赛，会先抽签决定一个数 $0/1$，我们将第 $R$ 轮的第 $G$ 场比赛抽到的数记为 $d_{R,G}$。抽到 $0$ 则表示表示编号小的选手为擂主，抽到 $1$ 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 $a\ge R$。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。

现在，小 S 先后陆续收到了 $n$ 位选手的报名信息，他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 $1,2,\dots ,n$。小 S 关心的是，补充尽量少的选手使总人数为 $2$ 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和是多少。

形式化地，设 $k$ 是最小的非负整数使得 $2^k\ge n$，那么应当补充 $(2^k-n)$ 名选手，且补充的选手的能力值可以任取 $[0,2^{31}-1]$ 之内的整数。如果补充的选手有可能取胜，也应当计入答案中。

当然小 S 觉得这个问题还是太简单了，所以他给了你 $m$ 个询问 $c_1,c_2,\dots ,c_m$。小 S 希望你帮忙对于每个 $c_i$ 求出，在只收到前 $c_i$ 位选手的报名信息时，这个问题的答案是多少。

输入格式

本题的测试点包含有多组测试数据。 但不同测试数据只是通过修改 $a_1,a_2,\dots ,a_n$ 得到，其他内容均保持不变，请参考以下格式。其中 $\oplus$ 代表异或运算符，$a\mathrm{mod}b$ 代表 $a$ 除以 $b$ 的余数。

输入的第一行包含两个正整数 $n,m$，表示报名的选手数量和询问的数量。

输入的第二行包含 $n$ 个非负整数 $a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }$，这列数将用来计算真正的能力值。

输入的第三行包含 $m$ 个正整数 $c_1,c_2,\dots ,c_m$，表示询问。

设 $K$ 是使得 $2^K\ge n$ 的最小的非负整数，接下来的 $K$ 行当中，第 $R$ 行包含 $2^{K-R}$ 个数（无空格），其中第 $G$ 个数表示第 $R$ 轮的第 $G$ 场比赛抽签得到的 $d_{R,G}=0/1$。

注意，由于询问只是将人数凑齐到 $2^k\ge c_i$，这里的 $k\le K$，因此你未必会用到全部的输入值。

接下来一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来共 $T$ 行，每行描述一组数据，包含 $4$ 个非负整数 $X_0,X_1,X_2,X_3$，该组数据的能力值 $a_i=a_i^{\prime }\oplus X_{i\mathrm{mod}4}$，其中 $1\le i\le n$。

输出格式

共输出 $T$ 行，对于每组数据，设 $A_i$ 为第 $i$（$1\le i\le m$）组询问的答案，你只需要输出一行包含一个整数，表示 $(1\times A_1)\oplus (2\times A_2)\oplus \cdots \oplus (m\times A_m)$ 的结果。

样例 #1

样例输入 #1

5 5
0 0 0 0 0
5 4 1 2 3
1001
10
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 1

样例输出 #1

5
19
7
1

提示

【样例 1 解释】

共有 $T=4$ 组数据，这里只解释第一组。$5$ 名选手的真实能力值为 $[1,0,0,2,1]$。$5$ 组询问分别是对长度为 $5,4,1,2,3$ 的前缀进行的。

1. 对于长度为 $1$ 的前缀，由于只有 $1$ 号一个人，因此答案为 $1$。
2. 对于长度为 $2$ 的前缀，由于 $2$ 个人已经是 $2$ 的幂次，因此不需要进行扩充。根据抽签 $d_{1,1}=1$ 可知 $2$ 号为擂主，由于 $a_2<1$，因此 $1$ 号获胜，答案为 $1$。
3. 对于长度为 $3$ 的前缀，首先 $1$ 号、$2$ 号比赛是 $1$ 号获胜（因为 $d_{1,1}=1$，故 $2$ 号为擂主，$a_2<1$），然后虽然 $4$ 号能力值还不知道，但 $3$ 号、$4$ 号比赛一定是 $4$ 号获胜（因为 $d_{1,2}=0$，故 $3$ 号为擂主，$a_3<1$），而决赛 $1$ 号、$4$ 号谁获胜都有可能（因为 $d_{2,1}=1$，故 $4$ 号为擂主，如果 $a_4<2$ 则 $1$ 号获胜，$a_4\ge 2$ 则 $4$ 号获胜）。综上所述，答案为 $1+4=5$。
4. 对于长度为 $4$ 的前缀，我们根据上一条的分析得知，由于 $a_4\ge 2$ ，所以决赛获胜的是 $4$ 号。
5. 对于长度为 $5$ 的前缀，可以证明，可能获胜的选手包括 $4$ 号、$7$ 号、$8$ 号，答案为 $19$。

因此，该组测试数据的答案为 $(1\times 19)\oplus (2\times 4)\oplus (3\times 1)\oplus (4\times 1)\oplus (5\times 5)=5$。

【样例 2】

见选手目录下的 arena/arena2.in 与 arena/arena2.ans。

这组样例满足特殊性质 A。

【样例 3】

见选手目录下的 arena/arena3.in 与 arena/arena3.ans。

这组样例满足特殊性质 B。

【样例 4】

见选手目录下的 arena/arena4.in 与 arena/arena4.ans。

【样例 5】

见选手目录下的 arena/arena5.in 与 arena/arena5.ans。

【数据范围】

对于所有测试数据，保证：$2\le n,m\le 10^5$，$0\le a_i,X_j<2^{31}$，$1\le c_i\le n$，$1\le T\le 256$。

测试点	$T=$	$n,m\le$	特殊性质 A	特殊性质 B
$1\sim 3$	$1$	$8$	否	否
$4,5$	$1$	$500$	是	否
$6\sim 8$	$1$	$500$	否	是
$9,10$	$1$	$5000$	否	否
$11,12$	$1$	$10^5$	是	否
$13\sim 15$	$1$	$10^5$	否	是
$16,17$	$4$	$10^5$	否	否
$18,19$	$16$	$10^5$	否	否
$20,21$	$64$	$10^5$	否	否
$22,23$	$128$	$10^5$	否	否
$24,25$	$256$	$10^5$	否	否

特殊性质 A：保证询问的 $c_i$ 均为 $2$ 的幂次。

特殊性质 B：保证所有的 $d_{R,G}=0$。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls x<<1
#define rs x<<1|1
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define ll long long
using namespace std;
const int N = (1 << 17) + 5;
int mx[20][N << 2], lg[N], aa[N], ok[N], a[N], c[N], n, m, nn = 1;
bool vis[N];
ll ans[N], sum;
struct node {
	ll sum;
	int x;
	bool tp, d;
} t[N << 2];
inline void build(int x, int l, int r) {
	if (l == r) {
		t[x].x = l;
		return ;
	}
	int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
	build(lson);
	build(rson);
	int win = a[t[x << 1 | d].x] >= k;
	t[x].x = t[x << 1 | (d ^ !win)].x;
	if (!d && win)t[x].tp = 1, ok[r]++, ok[mid]--;
	else t[x].tp = 0;
}
inline void build2(int x, int l, int r, int *mx) {
	t[x].sum = (l + r) * (r - l + 1ll) / 2;
	if (l == r)return ;
	int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
	if (~mx[x])mx[ls] = mx[rs] = mx[x];
	else mx[x << 1 | d] = k;
	build2(lson, mx);
	build2(rson, mx);
}
inline void up(int x) {
	sum += !vis[x] * x;
	vis[x] = 1;
}
inline int rd() {
	char c;
	int f = 1;
	while (!isdigit(c = getchar()))if (c == '-')f = -1;
	int x = c - '0';
	while (isdigit(c = getchar()))x = x * 10 + (c ^ 48);
	return x * f;
}
inline char gc() {
	char c;
	while ((c = getchar()) <= ' ');
	return c;
}
int main() {
	// freopen("arena.in","r",stdin);
	// freopen("arena.out","w",stdout);
	n = rd();
	m = rd();
	for (int i = 1; i <= n; i++)aa[i] = rd();
	for (int i = 1; i <= m; i++)c[i] = rd();
	while (nn < n)nn <<= 1;
	for (int i = 2; i <= nn; i++)lg[i] = lg[i >> 1] + 1;
	for (int i = nn / 2; i; i >>= 1)
		for (int j = i; j < i * 2; j++)
			t[j].d = gc() - '0';
	memset(mx, -1, sizeof mx);
	for (int s = 0; (1 << s) <= nn; s++)
		build2(1 << s, 1, nn>>s, mx[s]);
	for (int T = rd(); T--;) {
		int yh[4] = {rd(), rd(), rd(), rd()};
		for (int i = 1; i <= n; i++)a[i] = aa[i] ^ yh[i & 3];
		memset(ok, 0, sizeof ok);
		build(1, 1, nn);
		for (int i = nn, rt = 1, s = 0; i; i--) {
			if ((1 << lg[i]) == i) {
				if (i != nn)rt <<= 1, s++;
				for (int j = 1; j <= i; j++)vis[j] = 0;
				sum = 0;
				up(t[rt].x);
			}
			ans[i] = sum;
			if (ok[i] += ok[i + 1])continue;
			up(i);
			int x = i + nn - 1;
			while (x != rt) {
				int d = x & 1;
				x >>= 1;
				if (!d)
					if (t[x].tp)sum += t[rs].sum;
					else break;
				else if (a[t[ls].x] >= mx[s][ls])up(t[ls].x);
			}
		}
		ll num = 0;
		for (int i = 1; i <= m; i++)num ^= i * ans[c[i]];
		printf("%lld\n", num);
	}
	return 0;
}

后记

作者：zty郑桐羽呀
联系方式：（不挂了，有事私信）
兄弟们给个赞呗
先 赞 后 看 养 成 习 惯