P11234 题解

user100566 · 2024-11-01 14:53:09 · 题解

前言

本题解思路由 Lonely_Christmas 的题解发展而来，主要优化为避免了对战树形态变化导致的多次计算，代码为作者本人编写，已 AC。

废话: 本来是自己想要照着这个思路自己写代码的但是一直 WA，然后试图改进参考代码，但是无从入手一直卡 64, 128 的 TLE，最后推倒重来边写题解边写代码，调的居然还挺快。

题目分析

注意到一个重要事实：如果一个选手在报名人数为某值时能成为冠军，那么人数更少时也一定能成为冠军(当然这名选手要有"参赛资格")。
形式化的，对于选手 i，设 l 为 i 参加比赛的最小人数，则选手 i 可能获胜的 c 值是一个区间 [l, r]（可能是空区间）。

知道了所有选手的 [l, r] 后，根据选手编号在 [1, n] 内做区间加，做完后将 c_i 带入索引即为询问答案。只需要先差分再前缀加即可，复杂度 O(Tn)。

接下来考虑求 [l, r]，显然，l 是小于 i 的最大 2 的整数次幂 +1（注意 i=1 时 l=1）。
下面的代码预处理出了 l，不要低估求 l 的时长，这一优化相比传统求 l 方法直接把最大样例的运行时长缩短约 100ms。

预处理（这里指在具体测试数据之前完成的处理，复杂度不含 T）在本题降常甚至降复杂度中起关键作用，~~起码对于我的代码是这样~~。本题解的代码实现，基本上只要一个数据不需要用到 a_i 就直接预处理出来。

接下来只需要求出 r。
考虑选手 i 在报名选手数为 c(c\ge l) 时成为冠军的条件：

处理条件 1：

当 $c\ge i$ 时，记 $x_j $ 为 $i$ 第 $j$ 次守擂的对局**轮数**，若 $a_i\ge max(x)$，条件 1 还是一定成立。否则，存在最小的 $x_{j'}>a_i$，那么游戏轮数就不能达到 $x_{j'}$ 轮，**最大轮数**为 $x_{j'}-1$，这限制了 $r$ 的一个上界为 $2^{x_{j'}-1}$。编码时，可以预处理出所有 $i$ 的 $x$，然后对所有 $a_i \in [0, 16]$（更大的 $a_i$ 一定满足条件 1）求出**最大轮数**，时空复杂度 $O(n\log n)$，之后使用时直接索引即可。注意这一步预处理的复杂度**不含 $T$**，如果写在了 $T$ 里面，时间复杂度 $O(Tn\log n)$ 超时。

接下来只需要处理条件 2：

我们将对局建模为完美二叉树，树的高度为 K+1, [1, K] 层的结点表示 [1, K] 轮对局的获胜者(也可以理解为左子树和右子树的对局)，树的叶结点(K+1层)则为所有选手。~~如果不太熟悉完全二叉树的编码方式可以看这题：完全二叉树~~。

条件 2 不成立时，不妨设选手最后走到了 u，没能晋级到 \operatorname{parent}(u)=v 上，即卡在了 u\rightarrow v 上，那么原因很显然：u 不是对局 v 的擂主且 \operatorname{brother}(u)=w 一定能打赢比赛 u，我们不妨模拟选手一个一个一个报名的过程来解出条件 2 的限制。

设 R_t 表示结点 t 对应的对局轮数（叶子记为 0），p_t 表示结点 t 的获胜者的能力值（不确定时记为 -1），s_t 表示 t 打赢 \operatorname{parent}(t) 比赛时，c 的最大值（初始值为 \infty）。
当一名选手报名时，更新对应叶子结点的 p_t 为对应的 a，然后更新 s_{\operatorname{brother}(t)}, p_{\operatorname{parent}(t)}，如果 p_{\operatorname{parent}(t)} 被更新，还要进一步向上递归。

这里有一个重要事实：p_t 只会被一次更新为非 -1 值，实际上 p 的定义已经证明了这一点：只要 p_t 没有唯一确定值，p_t 就应该为 -1。因此由平摊分析可知上述模拟过程复杂度 O(Tn)。

注意这里有一个正确性结论：如果 p_{\operatorname{brother}(t)}=-1，那么 t 一定可以在对局 \operatorname{parent}(t) 中获胜，简要证明：如果 p_{\operatorname{brother}(t)}=-1，那么 p_{\operatorname{brother}(t)} 一定可以取到 R_{\operatorname{parent}(t)}-1（可以直接枚举所有情况证明），此时 \operatorname{brother}(t) 失败，t 获胜。

做完每个结点的 s 值后，还需要对于每个叶子结点求出其到根结点的 s 值的最小值才能得出条件 2 的限制。

这一步的复杂度要带 T ，自叶子向上到根复杂度为 O(Tn\log n)，不能接受。我们可以直接自顶向下更新 \min，复杂度 O(Tn)。

但是，从上面传下来的 min 值是否会因为当前轮数没有涉及到上面结点的比赛而导致 WA 呢？
这是不需要担心的。高层结点 u 的 s 值更新是 \operatorname{brother}(u)=w 的 p 值改变导致的，如果 w 为编号更大的子树（右子树），传下来的 \min 值偏大是没有关系的，如果 w 为左子树，既然当前轮数同时涉及到了 u, w，那么 u， w 之间的对局一定在当前轮数中被涉及到，还是正确的。

总结思路

读取非测试数据，预处理条件 1，预处理 R, l。
读取测试数据，更新 a_i。
重置 s, p。
模拟 [1, n] 的报名过程，模拟过程中更新 s, p。
向下更新 s。
对于所有可能的选手，计算贡献区间 [l, r]，差分维护加。
计算所有询问的答案，输出最终答案。
回到 2.。

代码

虽然长达 4000 字节，但是对阅读者友好。
下面的代码提示了一些可能出错的地方，请放心食用。
用了快读优化，最大样例运行时长上界约 700ms。

#include <cstdio>
#include <algorithm>
using namespace std; 
inline int read(){
    char c = getchar();
    while(c<48||c>57) c=getchar();
    int x = 0;
    while(48<=c&&c<=57){
        x = (x<<3)+(x<<1)+c-48;
        c = getchar();
    }
    return x;
}
typedef long long int64;
// 深度 x+1 的前缀，dpref(x)+i 为深度 x 中排行 i 的结点编号 
#define dpref(x) ((1<<(x))-1)
// 深度 x+1 的结点数 
#define dsize(x) (1<<(x))
#define fa(x) ((x)>>1)
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define bro(x) ((x)^1)
// x 是左(0)/右(1)子树 
#define lr(x) ((x)&1)

int n, m, a[100001], c[100001];
int K, d[131072];
int T, X[4]; 

void init();
void solve();

int main(){
    n = read(); m = read();
    for(K=1; (1<<K)<n; ++K);
    for(int i=1; i<=n; ++i) a[i] = read();
    for(int i=1; i<=m; ++i){
        c[i] = read();
    }
    char buffer[65537];
    for(int R=1; R<=K; ++R){
        scanf("%s", buffer);
        for(int G=1; G<=dsize(K-R); ++G){
            d[dpref(K-R)+G] = buffer[G-1]=='1';
        }
    }

    init();

    T = read();
    while(T--){
        for(int i=0; i<4; ++i) X[i] = read();
        for(int i=1; i<=n; ++i) a[i] ^= X[i%4];
        solve();
        // 技巧: 异或运算的自逆性 (a^b)^b = a 
        for(int i=1; i<=n; ++i) a[i] ^= X[i%4];
    }
    return 0;
}

// maxround[i][j] ~ 选手 i 的实力为 j 时，满足条件 1 的最大轮数 
int maxround[100001][17];
// cround[i] ~ i 对应的比赛结点的轮数(r)
int cround[262144];
// 获胜的 c 上界(s) 
int ceiling[262144];
// 获胜者能力值(p) 
int power[262144];
// larray[i] 即 i 对应的 l 值，预处理降常 
int larray[131073];

// 模拟法求 maxround ，复杂度 O(nlogn) 
void make_maxround(){
    for(int i=1; i<=n; ++i){
        for(int j=0; j<K; ++j){
            maxround[i][j] = K;
        }
        int curr = dpref(K)+i;
        int competion = fa(curr);
        // 双指针，即使不用，写成 O(n(logn)^2) 也是可以接受的 
        int p = 0;
        for(int round=1; round<=K; ++round){
            if(d[competion]==lr(curr)){
                for(int j=p; j<round; ++j){
                    maxround[i][j] = round-1;
                }
                p = round;
            }
            curr = competion;
            competion = fa(curr);
        }
    }
}
// 求 cround ，复杂度 O(n)
void make_cround(int id, int round){
    cround[id] = round;
    if(id<=dpref(K)){
        make_cround(ls(id), round-1);
        make_cround(rs(id), round-1);
    }
}
void make_larray(){
    // 注意，i=1 时 ， l=1 
    larray[1] = 1;
    for(int i=2; i<=(1<<K); ++i){
        int l = 1;
        if(i!=1){
            for(; l<i; l<<=1);
            l = (l>>1)+1;
        }
        larray[i] = l;
    }
}
void init(){
    make_maxround();
    make_cround(1, K);
    make_larray();
}

// 重置 ceiling(s), power(p)
void clear(int id){
    ceiling[id] = n;
    power[id] = -1;
    if(id<=dpref(K)){
        clear(ls(id));
        clear(rs(id));
    }
}

// 更新 power[id] 后计算影响 
void update(int id, int time){
    if(id==1) return;
    // 注意不要遗漏能确定 power(fa[id]) 的情况 
    if(d[fa(id)]==lr(id)){
        if(power[id]>=cround[fa(id)]){
            ceiling[bro(id)] = min(ceiling[bro(id)], time-1);
            power[fa(id)] = power[id];
            update(fa(id), time);
        }else if(power[bro(id)]!=-1){
            power[fa(id)] = power[bro(id)];
            update(fa(id), time);
        }
    }else if(power[bro(id)]!=-1 && power[bro(id)]<cround[fa(id)]){
        power[fa(id)] = power[id];
        update(fa(id), time);
    }
}
// 向下传递 ceiling 
void push_down(int id){
    if(id<=dpref(K)){
        ceiling[ls(id)] = min(ceiling[ls(id)], ceiling[id]);
        ceiling[rs(id)] = min(ceiling[rs(id)], ceiling[id]);
        push_down(ls(id));
        push_down(rs(id));
    }
}

int64 result[100002];
void solve(){
    clear(1);
    for(int i=1; i<=n; ++i){
        power[dpref(K)+i] = a[i];
        update(dpref(K)+i, i);
        // 注意 result 差分数组也要清空 
        result[i] = 0;
    }
    push_down(1);
    for(int i=1; i<=dsize(K); ++i){
        int l = larray[i];
        // 条件 2 
        int r = ceiling[dpref(K)+i];
        // 条件 1 ，注意前提是 a[i] 是确定的值，a[i]>=K 时不会限制 
        if(i<=n && r>=i && a[i]<K){
            // min(r) 是必要的，条件 1 限制的上界可能大于条件 2 限制的上界 
            r = min(r, 1<<maxround[i][a[i]]);
            // 注意，当且仅当 r>=i 时才能用条件 1 限制 r ，应该 min(i-1) 修正 
            r = max(r, i-1);
        }
        if(r>=l){
            result[l] += i;
            result[r+1] -= i;
        }
    }
    for(int i=1; i<=n; ++i){
        result[i] += result[i-1];
    }
    int64 ans = 0;
    for(int i=1; i<=m; ++i){
        ans ^= result[c[i]]*i;
    }
    printf("%lld\n", ans);
}