B. Sample Game

题意：有一个随机数生成器，每个数生成的概率为$p_i$，不断生成直到最后一个数小于先前的任意一个数时停止，共生成x个数，问$x^2$的期望

首先可以把$x^2$分解为$1+3+\cdots+(2x+1)$，即从每一步的增量考虑转移方法，若当前长度为x，则增量为2x+1，考虑增量的期望$E(2x+1)=2E(x)+1$，于是只要借助$E(x)$就能进行转移了

因此可以先处理出$f[i]$表示第一个数为$i$时的期望长度$E(x)$，$f[i]=(\sum\limits_{j=i+1}^nf[j]p_j+p_if[i]+\sum\limits_{j=1}^{i-1}p_j)+1$

再通过$f[i]$计算$f2[i]$，表示第一个数为$i$时长度平方的期望$E(x^2)$，$f2[i]=\sum\limits_{j=i+1}^n p_j(f2[j]+2f[j]+1)+p_i(f2[i]+2f[i]+1)+4\sum\limits_{j=1}^{i-1}p_j$

答案为$ans=\sum\limits_{i=1}^nf2[i]p_i$

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define per(x,y,z) for (int x=y;x>=z;x--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f, NN = 1e9 + 5;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(int a, int b) { return 1ll * a * b % MOD; }
int bin(int x, int p) {
    int res = 1;
    for (int b = x; p; p >>= 1, b = mul(b, b))
        if (p & 1) res = mul(res, b);
    return res;
}

int n, f[N], f2[N], invs, pre[N], w[N], sum, ans, inv[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    invs = bin(sum, MOD - 2);
    for (int i = 1; i <= n; i++) w[i] = mul(w[i], invs), pre[i] = add(pre[i - 1], w[i]), inv[i] = bin(sub(1, w[i]), MOD - 2);
    for (int i = n; i >= 1; i--) {
        int res = 0;
        for (int j = i + 1; j <= n; j++) res = add(res, mul(w[j], f[j]));
        res = add(res, pre[i - 1]);
        res = add(res, 1);
        res = mul(res, inv[i]);
        f[i] = res;
    }
    for (int i = n; i >= 1; i--) {
        int res = 0;
        for (int j = i + 1 ; j <= n; j++) res = add(res, mul(w[j], f2[j]));
        for (int j = i + 1; j <= n; j++) res = add(res, mul(w[j], add(mul(f[j], 2), 1)));
        res = add(res, mul(pre[i - 1], 4));
        res = add(res, mul(w[i], add(mul(2, f[i]), 1)));
        res = mul(res, inv[i]);
        f2[i] = res;
        ans = add(ans, mul(f2[i], w[i]));
    }
    cout << ans << endl;
    return 0;
}

E. Tree Xor

题意：给定一棵树，每条边有边权，每个点的点权在一个区间$[l_i,j_i]$内，要求一条边所连的两个点的点权异或值为该边边权，问树点权的方案数

从根节点出发，深搜时每经过一条边就把值$val$和该边权异或，转化为n个这样的式子：$x xor v_i\in[l_i,r_i]$，问同时满足这n个式子的x有多少种

结合字典树可以发现，对于一个式子，满足的x至多在$O(\log)$个连续的区间内（同前几场的$c xor a\leq b$问题），然后题目要求实际上就是把这n种限制取并集，一个简单的方法是，在字典树上访问所有$n\log n$个区间，给这些区间的子树上+1，然后最后dfs一遍统计有多少个点访问了n次。当然也可以用线段树维护区间最大值和最大值访问次数之类的方法去做。

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define per(x,y,z) for (int x=y;x>=z;x--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f, NN = 1e9 + 5;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

double add(double a, double b) { return a + b; }
double sub(double a, double b) { return a - b; }
double mul(double a, double b) { return a * b; }
int qpow(int x, int p) {
    int res = 1;
    for (int b = x; p; p >>= 1, b = mul(b, b))
        if (p & 1) res = mul(res, b);
    return res;
}

int n, a[N], rt;

struct Edge {
    int to, v;
};
vector<Edge> G[N];

struct Query {
    int w, l, r;
};

struct Segment_tree {
    #define mid ((l + r) >> 1)
    int lson[N << 6], rson[N << 6], mxv[N << 6], cnt[N << 6], lz[N << 6];
    int tot;
    void pushdn(int o) {
        mxv[lson[o]] += lz[o];
        mxv[rson[o]] += lz[o];
        lz[lson[o]] += lz[o];
        lz[rson[o]] += lz[o];
        lz[o] = 0;
    }
    void Merge(int o) {
        mxv[o] = max(mxv[lson[o]], mxv[rson[o]]);
        int c = 0;
        if (mxv[o] == mxv[lson[o]]) c += cnt[lson[o]];
        if (mxv[o] == mxv[rson[o]]) c += cnt[rson[o]];
        cnt[o] = c;
    }
    int newnode(int l, int r) {
        int o = ++tot;
        cnt[o] = r - l + 1;
        mxv[o] = 0;
        return o;
    }
    void modify_upper(int o, int l, int r, int p, int w, int R) {
        if (p == -1) {
            mxv[o]++;
            return;
        }
        if (!lson[o]) lson[o] = newnode(l, mid);
        if (!rson[o]) rson[o] = newnode(mid + 1, r);
        pushdn(o);
        int u = w >> p & 1, v = R >> p & 1;
        if (u == 1) {
            if (v == 1) {
                mxv[rson[o]]++;
                lz[rson[o]]++;
                modify_upper(lson[o], l, mid, p - 1, w, R);
            } else {
                modify_upper(rson[o], mid + 1, r, p - 1, w, R);
            }
        } else {
            if (v == 1) {
                mxv[lson[o]]++;
                lz[lson[o]]++;
                modify_upper(rson[o], mid + 1, r, p - 1, w, R);
            } else {
                modify_upper(lson[o], l, mid, p - 1, w, R);
            }
        }
        Merge(o);
    }

    void modify_lower(int o, int l, int r, int p, int w, int L) {
        if (p == -1) {
            mxv[o]++;
            return;
        }
        if (!lson[o]) lson[o] = newnode(l, mid);
        if (!rson[o]) rson[o] = newnode(mid + 1, r);
        pushdn(o);
        int u = w >> p & 1, v = L >> p & 1;
        if (u == 1) {
            if (v == 1) {
                modify_lower(lson[o], l, mid, p - 1, w, L);
            } else {
                mxv[lson[o]]++;
                lz[lson[o]]++;
                modify_lower(rson[o], mid + 1, r, p - 1, w, L);
            }
        } else {
            if (v == 1) {
                modify_lower(rson[o], mid + 1, r, p - 1, w, L);
            } else {
                mxv[rson[o]]++;
                lz[rson[o]]++;
                modify_lower(lson[o], l, mid, p - 1, w, L);
            }
        }
        Merge(o);
    }
    int query() {
        if (mxv[1] == n * 2) return cnt[1];
        else return 0;
    }
}seg;


pii b[N];

vector<Query> Q;

void dfs(int x, int val, int ff) {
    Q.push_back({val, b[x].first, b[x].second});
    for (auto T : G[x]) {
        if (T.to == ff) continue;
        dfs(T.to, val ^ T.v, x);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &b[i].first, &b[i].second);
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    dfs(1, 0, -1);
    seg.tot = 1;
    seg.mxv[1] = 0, seg.cnt[1] = 1 << 30;
    for (auto x : Q) {
        seg.modify_upper(1, 0, (1 << 30) - 1, 29, x.w, x.r);
        seg.modify_lower(1, 0, (1 << 30) - 1, 29, x.w, x.l);
    }
    printf("%d\n", seg.query());
    return 0;
}

J. Average

题意比较简单，最后问题求得是给定一个数列a，求长度$\leq k$的连续区间，使得区间平均值最大，即$\max \sum_\limits{i=l}^ra_i\frac{1}{r-l+1}$

方法是二分答案，二分一个平均值$ans$，然后判断是否存在一个长度超过k的区间满足$\sum\limits_{i=l}^ra_i\ge (r-l+1)ans$，转化一下即$\sum\limits_{i=l}^r a_i-ans\ge 0$

所以只要把数列每个位置都减去ans，然后判断是否有一个长度超过k的区间求和>0即可，这步记录每个位置的最小前缀和，$O(n)$完成