题解：P11234 [CSP-S 2024] 擂台游戏（暂无数据）

· · 题解

P11234 题解

考场做法。

题目大意

太复杂，自己看题面吧。

题目分析

直线考虑怎么线性。

先把整个过程看成一个完全二叉树。

一个人能走到最后有两个条件：自己擂主时能力值要够大，别人擂主时别人的能力值要够小。第一个条件很容易，预处理出每个点到根最后一次当擂主的轮数就行。第二个条件则需要预处理出每个子树最小能让能力值多小的人胜出。

实际上每个子树只有两种可能：胜出者固定为某个人，或者胜出者的能力值可以取当前轮数以上的任意值。记 f_u 表示子树 u 的胜出者能力值，f_u=-1 表示可以任取，记 h_u 表示节点 u 的轮数，不妨设左孩子是擂主，则：

f_u=\begin{cases}f_{ls}&f_{ls}\ge h_u\\-1&f_{ls}=-1\\f_{rs}&otherwise\end{cases}

容易发现在 n 个人逐渐加入的过程中，任意一个点的 f 总是初始是 -1，某一时刻变为 \ge0 的值后一直不变。所以在 n 个人逐渐加入时，从对应的叶子节点向上更新 f，直到某个点处 f 不变，复杂度是线性的。

那么当一个节点的 f 值变为 \ge0 时，如果下一轮中这个节点是擂主且 f_u\ge h_{fa}，那么 u 的兄弟节点的子树中的所有人就再也不可能走到最后。这时候可以再维护一个 g_u 表示加入第几个人之后，子树 u 中的人就再也不可能走到最后了。n 个人都加入后，求出每个点到树根路径上的 g 最小值，即 g_u=\min(g_u,g_{fa})，得出叶子节点处的 g，也就是每个人在哪个时间前还有可能走到最后。

求出叶子节点的 g 后，一个人对于答案的贡献就是一个前缀加。差分一下可以实现线性求出所有询问的答案。

整个过程是这样的：初始 f=-1，从 1\sim n 逐个加入每个人，将 f_u 改为 a_i，并向上更新。如果某个点的擂主被确定，则用当前时间更新另一颗子树的 g。结束后把 g 推下来，对于每个人做一个前缀加。

人数太少时树的结构会变化，只需要每次人数达到 2^k 时重做一遍就行。

总复杂度线性。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100001;
int n,m,k;
int a[N];
int c[N];
char d[N*2];
int f[N*4],g[N*4],h[N*4],b[N*4];
void dfs(int i,int t){
    f[i]=-1,g[i]=t+1;
    if(i>=(1<<k))return;
    int j=(i<<1)+d[i]-'0';
    h[j]=h[j^1]=h[i]-1;
    if(b[i])b[j]=b[j^1]=b[i];
    else b[j]=h[i],b[j^1]=0;
    dfs(j,t),dfs(j^1,t);
}
void upd(int i,int t){
    if(!i)return;
    if(f[i]!=-1)return;
    int j=(i<<1)+d[i]-'0';
    if(f[j]>=h[i])f[i]=f[j],g[j^1]=min(g[j^1],t);
    else if(f[j]!=-1)f[i]=f[j^1];
    if(f[j]!=-1)upd(i>>1,t);
}
void get(int i){
    if(i>=(1<<k))return;
    int j=(i<<1)+d[i]-'0';
    g[j]=min(g[j],g[i]);
    g[j^1]=min(g[j^1],g[i]);
    get(j),get(j^1);
}
ll s[N*2],res[N*2];
void solve(int t){
    int p=1<<(k-t);
    h[p]=t,b[p]=0;
    dfs(p,1<<t);
    for(int i=1;i<=n;i++){
        int j=i+(1<<k)-1;
        if(a[i]<b[j])g[j]=min(g[j],i);
        f[j]=a[i];
        upd(j>>1,i);
    }
    get(p);
    for(int i=1;i<=(1<<t);i++)s[i]=0;
    for(int i=1;i<=(1<<t);i++){
        int j=i+(1<<k)-1;
        s[g[j]-1]+=i;
    }
    for(int i=(1<<t);i>=1;i--){
        s[i-1]+=s[i];
        res[i]=s[i];
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    while((1<<k)<n)k++;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>c[i];
    for(int i=k-1;i>=1;i--)
        for(int j=0;j<(1<<i);j++)
            cin>>d[(1<<i)+j];
    cin>>d[1];
    int T;
    cin>>T;
    while(T--){
        int x[4];
        cin>>x[0]>>x[1]>>x[2]>>x[3];
        for(int i=1;i<=n;i++)a[i]^=x[i%4];
        for(int i=k;i>=0;i--)solve(i);
        ll ans=0;
        for(int i=1;i<=m;i++)ans^=i*res[c[i]];
        cout<<ans<<'\n';
        for(int i=1;i<=n;i++)a[i]^=x[i%4];
    }
    return 0;
}

谢谢观看！