牛客练习赛81

自闭了

A 小 Q 与异或

~~被签到卡死了~~

先排序, 出现两个位置相同数不同 -1

否则(p_i)这个位置的值为前面的前缀和也就是(x_{i- 1}), 则当前位置为

(a_i = x_{i - 1} igoplus {x_i}),

然后时处理 ([p_{i - 1} + 1, p_i - 1]) 之间数的问题

注意到(a_{p_i} = 0) 且 $ p_{i - 1} + 1 == p_i $ - 1

否则当([p_{i - 1} + 1, p_i]) 之间有偶数个数, 则区间内每个数异或(1<<30), 刚刚好

([p_{i - 1} + 1, p_i]) 之间有奇数个数

(a_{p_i} != 0), 那么([p_{i - 1} + 1, p_i - 1]) 之间的数异或 (1<<30) 即可
(a_{p_i} == 0), 让(a_{p_{i - 1} + 1} = x_{i - 1}), 则前缀和为(0)了, 区间为偶数了很好处理

然后就是各种 wa, 最后才发现

对于第二种情况, (x_{i - 1} = 0) 没有考虑啊啊啊啊啊

所以最终, 对于([p_{i - 1} + 1, p_i]) 之间有奇数个数

强制(a_{p_{i - 1} + 1} igoplus = 1, a_{p_x} igoplus = 1) 强制把 (a_{p_i} != 0) 然后区间还变成了偶数

int a[N];
PII b[N];

int main() {
    IOS; cin >> n >> m;
    rep (i, 1, m) cin >> b[i].fi >> b[i].se;
    sort(b + 1, b + 1 + m);
    rep (i, 1, m) {
        if (b[i].fi == b[i - 1].fi) {
            if (b[i].se ^ b[i - 1].se) return cout << -1, 0;
            continue;
        }
        a[b[i].fi] = b[i - 1].se ^ b[i].se;
        if (!a[b[i].fi] && b[i].fi == b[i - 1].fi + 1) return cout << -1, 0;
        if (b[i].fi - b[i - 1].fi - 1 & 1) 
            rep (j, b[i - 1].fi + 1, b[i].fi) a[j] ^= (1 << 30);
        else {
            a[b[i - 1].fi + 1] ^= 1; a[b[i].fi] ^= 1;
            rep (j, b[i - 1].fi + 1, b[i].fi - 1) a[j] ^= (1 << 30);
        }
    }
    rep (i, 1, n) cout << (a[i] ? a[i] : 1 << 30) << ' ';
    return 0;
}

B 小 Q 与彼岸花

数据小了, 最优的复杂度是分块 + trie, 复杂度为(n imes sqrt{n} imes logS), S为值域

既然数据水了, 就写了(n^2 imes logS)

ll a[N];
int tr[N * 10][2], tot;

int newNode() { ++tot; tr[tot][0] = tr[tot][1] = 0; return tot; }

void insert(int x) {
    for (int p = 0, i = 10; ~i; p = tr[p][x >> i & 1], --i)
        if (!tr[p][x >> i & 1]) tr[p][x >> i & 1] = newNode();
}

int find(int x) {
    int mx = 0;
    for (int p = 0, i = 10; ~i; --i)
        if (tr[p][x >> i & 1 ^ 1]) mx ^= 1 << i, p = tr[p][x >> i & 1 ^ 1];
        else p = tr[p][x >> i & 1];
    return mx;
}

int main() {
    IOS; cin >> n >> m;
    rep (i, 1, n) cin >> a[i];
    rep (i, 1, m) {
        int l, r, mx = 0; cin >> l >> r;
        tr[0][0] = tr[0][1] = tot = 0;
        rep (i, l, r) insert(a[i]);
        rep (i, l, r) umax(mx, find(a[i]));
        cout << mx << '
';
    }
    return 0;
}

D 小 Q 与树

平衡树启发式合并

好久不写平衡树了, 磕磕绊绊

const int N = 2e5 + 5, mod = 998244353;

ll ans = 0;

struct FHQ {
    int tr[N][2], sz[N], pri[N], a[N][3], s[N][3], rt[N];
    void push_up(int p) {
        sz[p] = (1ll + sz[tr[p][0]] + sz[tr[p][1]]) % mod;
        rep(i, 0, 2) s[p][i] = ((ll)s[tr[p][1]][i] + s[tr[p][0]][i] + a[p][i]) % mod;
    }
    void split(int p, int k, int& x, int& y) {
        if (!p) x = y = 0;
        else {
            if (a[p][1] <= k) x = p, split(tr[p][1], k, tr[p][1], y);
            else y = p, split(tr[p][0], k, x, tr[p][0]);
            push_up(p);
        }
    }
    int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (pri[x] < pri[y]) tr[x][1] = merge(tr[x][1], y);
        else tr[y][0] = merge(x, tr[y][0]), swap(x, y);
        push_up(x); return x;
    }
    void cal(int lc, int u, int t) {
        if (!u) return;
        cal(lc, tr[u][0], t); cal(lc, tr[u][1], t);
        int x, y; split(t, a[u][1], x, y);
        ans = (ans + (ll)s[x][2] + (a[u][0] - 2ll * a[lc][0] % mod) * s[x][1] % mod) % mod;
        ans = (ans + (s[y][0] + (a[u][0] - 2ll * a[lc][0]) % mod * sz[y] % mod) * a[u][1] % mod) % mod;
        merge(x, y);
    }
    void unit(int& p, int t) {
        if (!t) return;
        unit(p, tr[t][0]); unit(p, tr[t][1]);
        tr[t][0] = tr[t][1] = 0; push_up(t);
        int x, y; split(p, a[t][1], x, y);
        p = merge(x, merge(t, y));
    }
} T;

int n, m, _, k, cas;
VI h[N];

void dfs(int x, int fa) {
    T.a[x][0] = T.a[fa][0] + 1; T.a[x][2] = (ll)T.a[x][0] * T.a[x][1] % mod;
    for (int& y : h[x]) if (y ^ fa) dfs(y, x);
}

void dfs1(int x, int fa) {
    for (auto& y : h[x]) if (y ^ fa) dfs1(y, x);
    T.unit(T.rt[x], x);
    for (auto& y : h[x]) if (y ^ fa) {
        if (T.sz[T.rt[x]] < T.sz[T.rt[y]]) swap(T.rt[x], T.rt[y]);
        T.cal(x, T.rt[y], T.rt[x]); T.unit(T.rt[x], T.rt[y]);
    }
}

int main() {
    IOS; cin >> n; srand(time(0));
    rep(i, 1, n) cin >> T.a[i][1], T.pri[i] = rand();
    rep(i, 2, n) { int u, v; cin >> u >> v; h[u].pb(v); h[v].pb(u); }
    dfs(1, 0);
    dfs1(1, 0); cout << (2 * ans % mod + mod) % mod;
    return 0;
}