P11234 [CSP-S 2024] 擂台游戏 题解

前言

作者在考场上用了约 1h 把前三道题做完了，然后用了约半小时想了带 \(\log\) 的做法，但是我决定放手一搏去想线性的做法，于是又想了有 1h 之后觉得想到了正解，然后我就一直写到了考试结束，但是最终没有调出来遗憾离场，因此写个题解来纪念一下。

题解

首先因为 \(n,m\) 是同阶的，所以肯定是考虑把所有位置的答案全部算出来。首先，设 \(N\) 表示第一个不小于 \(n\) 的 \(2\) 的整数次幂，我们用 \(N-n\) 个 \(0\) 去补齐剩下的位置，第一步肯定是把所有轮获胜的人用一棵线段树建出来，这一步是好做的。

现在考虑依次求出每个位置的答案 \(ans_i\)，我第一想法是正着去扫，但是感觉不太好做，所以决定倒着去扫。有一个显然的结论就是，如果一个位置从一个确定的数变成了任意值，那么原来在答案里的人现在依然在答案里，也就是说，对于二进制位数相同的一段，\(ans_i\) 是不增的，于是现在就考虑计算如果一个位置由确定值变成了任意值，有哪些新的可能的答案。当然，对于二进制位数不同的段，每次都要清空并重新计算，以下仅考虑对于同一个段的计算。

首先，我们线段树先预处理出了每个结点是哪一个人会获胜，对于当前的段，答案里肯定有本来就会获胜的那一个人，所以先讲其计入答案（注意，以下说的计入答案都指的是先判断这个人是否已被计入答案再加，因为可能有重复）。

接着，如果对于一个线段树的结点，满足以下条件，我们就将其称为坏点：这个区间的 \(d=0\)，且编号小的人会获胜。如果一个结点是坏点，那么对于这个结点右儿子中包含的所有的人，他们由确定值变为不确定值对答案都是没有贡献的，因为到这个结点的时候他们一定都会被打败（所有人是从后往前一个一个变为不确定的，所以一个人变之后前面的所有人的值依然是确定的）。那么我们可以给整个区间打上标记，表示这个区间都没有贡献。如果扫到了一个被打标记的人，就直接跳过。

否则的话，这个人一定是有贡献的，因为只要将他的初始值设为 \(\infty\)，他就一定会赢，将他计入答案。接着考虑哪些人也会跟着计入答案，我们考虑从当前这个人代表的叶子结点不断往上跳。设当前点为 \(x\)，父亲为 \(fa_x\)，我们分 \(x\) 是左儿子还是右儿子两种情况来考虑：

• \(x\) 是右儿子，那么 \(fa_x\) 的左儿子结点的胜者 \(y\) 就有可能会被记入答案，具体的，我们对于每一个结点都需要再记录一个值 \(mx\)，表示根到结点的所有对局中，选到自己的所有对局中轮数最大的是多少，这个也可以在预处理中简单计算。那么如果 \(a_y\ge mx\)，\(y\) 就能被计入答案，因为我们可以将所有的不确定值设为刚好在与 \(y\) 对局时输掉，这样就能获胜。
• \(x\) 是左儿子且 \(fa_x\) 是一个坏点，那么此时 \(fa_x\) 的右儿子中的所有人都应该被计入答案，可以理解为这些人原来有个限制使得他们不能获胜，现在这个限制没了，所以这些人都可以获胜了。
• \(x\) 是左儿子且 \(fa_x\) 不是一个坏点，那么在继续往上跳的贡献都已经被 \(fa_x\) 的右儿子计算过了，直接 break。

于是，我们就计算完了所有的贡献，每次在一个人变之前，让 \(ans_i\) 赋为当前的答案即可。考虑时间复杂度，首先建树什么的都是线性的，然后对于计算答案的部分，我们考虑每一个线段树的结点，它不可能同时被左儿子和右儿子访问（因为被左儿子访问要求这是个坏点，但是如果是坏点的话右儿子直接被打上标记跳过了），所以每个结点都只会访问一次，所以复杂度是 \(\mathcal{O}(Tn)\) 的。

另外，还有一个需要注意的问题：如果每一个二进制位数不同的段都预处理 \(mx\) 的话常数太大了，我们发现每个结点的 \(d\) 是一开始给定的，所以这个只需要在 \(T\) 组数据前预处理即可。其他细节，比如读入之类的具体可以看代码。

代码

#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;
}

总结

这是一道细节很多的好题，我觉得考场上至少再给我个 1h 才能写出来，但是我觉得能想出来已经很不错了，NOIP 再战吧！