A85304 [CSP‑S2024]擂台游戏 精简题解

题意

每次询问给定 $c$，只看前 $c$ 个选手。取最小 $k$ 满足 $2^k\ge c$，补 $2^k-c$ 个虚拟选手，总人数为 $2^k$。

共 $k$ 轮比赛。第 $R$ 轮第 $G$ 场有抽签 $d_{R,G}$：

• $(d=0)$：编号小的为主擂；$(d=1)$：编号大的为主擂。
• 主擂获胜条件：自身能力值 $\ge R$，对手能力无影响。

虚拟选手能力可以任意指定。只要存在赋值方案能拿到总冠军，该选手编号计入答案。
询问要输出所有可能夺冠选手的编号总和。
多组数据：$a_i$ 由固定数组异或生成；抽签数组全局不变。虚拟选手也要计入答案。

核心结论

对真实选手 $x\le c$，要能夺冠，每一轮 $R$：

1. 若本场 $x$ 是主擂：必须 $a_x\ge R$。
2. 若本场主擂是对手：
   • 对手是虚拟选手：无约束。
   • 对手是真实选手：必须该对手 $a_{opp}<R$，否则对手必赢，$x$ 无法夺冠。

虚拟选手一定可以夺冠，直接把 $(c+1) \sim 2^k$ 的编号全部加到答案。

预处理

对所有编号 $pos$、所有可能的 $k$，预处理每一轮 $R$：
该轮比赛的主擂对手编号 $(opp[pos][R])$。只依赖抽签 $d$，与测试数据无关。

算法流程

1. 读入数据，预处理 $opp$ 表。
2. 每组测试数据生成 $a$ 数组。
3. 本组询问离线，按 $c$ 从小到大处理，维护合法真实选手的编号和。
4. 处理询问 $c$：
   • 求 $k$，$S=2^k$。
   • 答案 = 合法真实选手和 + $(c+1)$ 到 $S$ 的编号和。
5. 按原顺序输出答案。

易错点

1. 不要漏虚拟选手的编号和。
2. 获胜条件是 $\ge R$，不是 $(>R)$。
3. 每个询问独立求 $k$，不一定用题目给出的全局最大 $K$。
4. 多组数据抽签数组不变，仅 $a$ 数组变化。

最后看代码：

#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()
{
    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;
}