P11234 [CSP-S 2024] 擂台游戏

· · 题解

观察到补充选手很强，补充选手作为擂主时可控制是否取胜。

观察到一个人贡献到 c 的一个后缀。设这个后缀为 (g_i,n]，即 i 获胜要编号 \ge g_i 的人都是补充选手。

考虑计算 g。先预处理 p_u：u 子树确定时的胜者，f_u：u 子树胜者是补充选手时，至少要 \ge f_u 的人都是补充选手。

算 g_i 时从叶子 i 跳到根，设当前点 u，u 兄弟为 v。

现在是 O(n\log n) 的。容易优化到线性，改变状态从上往下 dp。

设 g'_u：u 到根链要求子树内 g_i\le g'_u。h_u：u 到根链要求子树内 a_i\ge h_u。dp 时考虑把擂主儿子的 f 传给另一侧儿子的 g'，把当前点深度传给擂主儿子的 h。

算完后 ans_{g_u-1}\gets u 然后做后缀和。这是算原树右子树答案的方法，左子树部分是 \frac n2 的问题，递归下去同样做。总复杂度线性。

常数小优化：只有 g'_u\gt\frac{n'}2 才能贡献到 ans。因此 dp 时 g'\le\frac{n'}2 时退出。

#include<bits/stdc++.h>
using namespace std;

int read(){
    int x = 0; bool f = 0; char c = getchar();
    for(;!isdigit(c);c = getchar()) f |= (c == '-');
    for(;isdigit(c);c = getchar()) x = x * 10 + (c - '0');
    return f ? -x : x;
}

using ll = long long;

const int N = 3e5 + 5;

int C,n,m,k,K,A[N],a[N],b[N],c[N],clen,V[10];
int d[N],f[N],g[N],h[N],P[N],o[N],rt,n0,n1;
ll ans[N],ans1[N];
char s[N];

void build(int p){
    if(p * 2 > K) return P[p] = f[p] = p - (1 << k) + 1,void();
    int lc = p * 2,rc = lc + 1;
    build(lc),build(rc);
    d[p] = d[lc] + 1;
    P[p] = c[p] ? (a[P[rc]] >= d[p] ? P[rc] : P[lc]) : (a[P[lc]] >= d[p] ? P[lc] : P[rc]);
    f[p] = c[p] ? f[rc] : (a[P[lc]] >= d[p] ? f[lc] : f[rc]);
}

void dfs(int p){
    if(g[p] <= n1) return;
    if(p * 2 > K){
        int q = p - (1 << k) + 1;
        g[p] = min(g[p],a[q] < h[p] ? q : n0 + 1),o[q] = rt;
        return;
    }
    int lc = p * 2,rc = lc + 1;
    g[lc] = g[rc] = g[p],h[lc] = h[rc] = h[p];
    if(!c[p] && a[P[lc]] >= d[p]) g[rc] = min(g[rc],f[lc]);
    if(!c[p]) h[lc] = max(h[lc],d[p]);
    if(c[p] && a[P[rc]] >= d[p]) g[lc] = min(g[lc],f[rc]);
    if(c[p]) h[rc] = max(h[rc],d[p]);
    dfs(lc),dfs(rc);
}

int main(){
    n = read(),m = read();
    for(int i = 1;i <= n;++i) A[i] = read();
    for(int i = 1;i <= m;++i) b[i] = read();
    k = __lg(n - 1) + 1,K = (1 << (k + 1)) - 1;
    for(int i = 1;i <= k;++i){
        scanf("%s",s + 1);
        for(int j = strlen(s + 1);j;--j) c[++clen] = s[j] - '0';
    }
    reverse(c + 1,c + clen + 1);
    for(C = read();C--;){
        for(int i = 0;i < 4;++i) V[i] = read();
        for(int i = 1;i <= n;++i) a[i] = A[i] ^ V[i % 4],ans[i] = 0;
        build(1);
        for(int i = 1;i <= (1 << k);++i) ans[i] = 0,o[i] = -1;
        ans[1] = 1;
        for(int j = 0;j < k;++j){
            rt = 1 << j,n0 = 1 << (k - j),n1 = 1 << (k - j - 1);
            g[rt] = n0 + 1,h[rt] = 0,dfs(rt);
            for(int i = n0;i >= 1;--i) if(o[i] == rt){
                int t = g[i + (1 << k) - 1] - 1;
                if(t <= n0 && t > n1) ans[t] += i;
            }
            for(int i = n0 - 1;i > n1;--i) ans[i] += ans[i + 1];
        }
        ll sum = 0;
        for(int i = 1;i <= m;++i) sum ^= ans[b[i]] * i;
        printf("%lld\n",sum);
    }
    return 0;
}