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

· · 题解

[CSP-S 2024] 擂台游戏

看了看题解，全是从上往下做的，但是我就喜欢从下往上。

首先我们对于每个 [2^i+1,2^{i+1}] 的区间单独处理，因为树的形态是一致的，如果单次能做到 O(2^i) 就能做到 O(Tn)。

我们考虑某个 2^{k-1}\lt n\leq 2^k，那每个叶子结点都有一条往上的链，是包赢的。也就是说，无论 (n,2^k] 内的节点如何选，这些节点都是某个定制。

举个例子：

其中最下面的是权值，其余的是 g，那么每个点包赢的区间为：

好，那么好，一个点 u 可以赢的充要条件是什么呢？

  1. 该点包赢区间上方不能有其他包赢的点。
  2. 该点到根路径上，对于他是 x 左儿子且 g=0 的情况以及他是右儿子且 g=1 的情况，需要满足 a_u\geq dep_x，dep_x 是从下往上的深度。

这为什么是对的呢？

  1. 对于没有包赢的点，他的权值可以是任意。
  2. 上面的第二点保证了存在一种权值放置方法使得可以到根。

男人！我说的什么罐头？

那么我们先将一个点 u 的权值设为满足第二条的话就为 u 否则为 0，再建个线段树。

然后我们就从 2^{k-1}+1 到 2^k 进行枚举，每个点对于包赢的情况再线段树上一直往上跳，记左右儿子为 ls,rs。

  1. 如果作为 rs_u 跳到一个点 u，且 ls_u 是对于 v 包赢的，那么减掉 v 的权值。
  2. 如果作为 ls_u 跳到一个点 u，就减掉 rs_u 内所有点的权值，然后下一次枚举的时候直接从 rs_u 内最右的点的下一个开始枚举。
  3. 如果作为 rs_u 跳不动了，但是 ls_u 由于 rs_u 跳不动而跳的动了，那么就减掉 rs_u 包赢的权值，ls_u 接着向上跳。

我们发现每个点最多会被跳到一次，所以做下来复杂度是线性的，那么此题救以 O(Tn) 做完了。

但是考场上没写出来，怎么回事呢，曼巴出去！

更新：加个代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <ctime>
#include <random>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
//#define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;
using namespace __gnu_pbds;
bool Mbe;

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
int read() {
    int s = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
        f ^= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9')
        s = s * 10 + c - '0', c = getchar();
    return f ? s : -s;
}
template<typename T>void chkmax(T &x, const T &y) { x = max(x, y); }
template<typename T>void chkmin(T &x, const T &y) { x = min(x, y); }

const int N = 1000005;
int n, m, lim;
int q[N], a[N], aa[N], K, pw[N], winer[32][100005], val[N], id[N], mx[N], le[N], ri[N], g[32][100005];
ll pre[N], now, ans[N];
pii rev[N];
int stk[N], hd, tl;
void build(int l, int r, int k, int t, int ma) {
    ri[t] = r;
    rev[t] = MP(k, r / pw[k]);
    val[t] = 0;
    if (l == r) return mx[l] = ma, id[l] = t, void();
    int mid = (l + r) >> 1;
    build(l, mid, k - 1, t << 1, ma ? ma : (!g[k][r / pw[k]]) * k);
    build(mid + 1, r, k - 1, t << 1 | 1, ma ? ma : g[k][r / pw[k]] * k);
}
void add(int u, int f) { if (a[u] >= mx[u]) now += f * u; }
int lst;
void update(int u, int U) {
    add(val[u] = lst = U, 1);
    while (u > 1) {
        int fat = u >> 1;
        int k = rev[fat].fi, c = g[k][rev[fat].se], lt = fat << 1;
        if (u == lt) {
            if (!c && a[U] >= rev[fat].fi)
                val[fat] = U, now -= pre[ri[fat]] - pre[ri[fat] - pw[k - 1]];
            else break;
        } else {
            if ((c && a[U] >= k) || (!c && a[val[lt]] < k)) {
                if (val[lt]) add(val[lt], -1);
                val[fat] = U;
            } else if (val[lt] && !val[fat] && c && a[U] < k) {
                add(U, -1);
                U = val[lt];
                val[fat] = U;
            } else break;
        }
        u = fat;
        lst = ri[u];
    }
}
void insert(int u) {
    now -= u;
    int x = id[u];
    update(x, u);
}
void work(int L, int R, int k) {
    now = pre[pw[k]] - pre[pw[k - 1]];
    build(1, (1 << k), k, 1, 0);
    int x = winer[k - 1][1];
    if (!g[k][1] && a[x] >= k) {
        rep(i, L, min(R, n))ans[i] = x;
        return;
    }
    add(x, 1);
    val[2] = x;
    rep(i, L, min(R, n)) {
        insert(i);
        rep(j, i, lst)ans[j] = now;
        i = lst;
    }
}
void solve() {
    ans[1] = 1;
    rep(i, 1, n)winer[0][i] = i;
    rep(i, 1, K)rep(j, 1, n / pw[i])if (winer[i - 1][j * 2 - 1] && winer[i - 1][j * 2]) {
        if (!g[i][j]) {
            if (a[winer[i - 1][j * 2 - 1]] >= i)
                winer[i][j] = winer[i - 1][j * 2 - 1];
            else
                winer[i][j] = winer[i - 1][j * 2];
        } else {
            if (a[winer[i - 1][j * 2]] >= i)
                winer[i][j] = winer[i - 1][j * 2];
            else
                winer[i][j] = winer[i - 1][j * 2 - 1];
        }
    }
    rep(i, 1, K)work((1 << (i - 1)) + 1, (1 << i), i);
    ll Ans = 0;
    rep(i, 1, m)Ans ^= ((ll)i * ans[q[i]]);
    printf("%lld\n", Ans);
}

bool Med;
signed main() {
    fprintf(stderr, "%.3lfMb\n", (&Mbe - &Med) / 1024. / 1024.);
    n = read(), m = read();
    pw[0] = 1;
    rep(i, 1, 31)pw[i] = pw[i - 1] * 2;
    rep(i, 1, n)aa[i] = read();
    rep(i, 1, m)q[i] = read();
    for (;; K++) if ((1 << K) >= n) break;
    rep(i, 1, K) {
        char c = getchar();
        rep(j, 1, (1 << (K - i))) {
            while (c < '0' || c > '1') c = getchar();
            g[i][j] = c - '0';
            c = getchar();
        }
    }
    lim = (1 << K);
    rep(i, 1, lim)pre[i] = pre[i - 1] + i;
    for (int T = read(); T--;) {
        int X[4];
        rep(i, 0, 3)X[i] = read();
        rep(i, 1, n)a[i] = aa[i] ^ X[i % 4];
        solve();
    }
    return 0;
}