B、Boxes

题目大意

你有 $n$ 个盒子，每个盒子内存在可能有黑球和白球中的一种，打开每个盒子都有一个代价 $w_i$ ，你还有一次询问裁判的机会，当然询问裁判代价为 $C$ ，你需要告诉裁判这 $n$ 个盒子每个盒子里面的球颜色，你需要花费的最小代价是多少？

Solution

考点：思维

首先我们不询问裁判的话，我们就要把 $n$ 个盒子全部打开，代价为 $\sum\limits_{i=1}^nw_i$

如果我们询问裁判，那么想想我们是不是最多只需要打开 $n-1$ 个盒子，并且如果用 $0$ 代表白球 $1$ 代表黑球如下分析。

考虑开 $0$ 次盒子结束，如果裁判告诉我们有 $n$ 个白球或者 $n$ 个黑球用二进制表示那就是 $0000$ 或 $1111$ 这样的时候结束，那么我们这次代价就只有 $C$ 。

考虑开 $1$ 次盒子结束，那么我们要先开最小花费的那个，并且结束的要求是 $1000$ 或者 $0111$ ，并且还需要对上裁判给你的颜色，所以这里应该概率多乘一个 $\frac{1}{2}$ ，那么这种概率计算为 $\frac{1}{2}^{n-1}$

考虑开 $2$ 次盒子结束，那么我们结束的要求就是 $.100$ 或者 $.011$ ，那么这种概率计算为 $\frac{1}{2}^{n-2}$

以此类推，把开盒子代价排序然后求前缀和处理就行了。

const int N = 1e6 + 7;
int n;
double C;
double p[N];

int solve() {
    cin >> n >> C;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; ++i) p[i] += p[i - 1];

    double res = C;
    for (int i = 1; i < n; ++i)  res += p[i] * pow(0.5, n - i);

    res = min(res, p[n]);
    printf("%.12f\n", res);
    return 1;
}

C、Cheating and Stealing

题目大意

你和对手进行乒乓球比赛，你们原本进行了 $n(1\le n\le 10^6)$ 局比赛， $W$ 代表你赢下了第 $i$ 局， $L$ 代表你输掉了第 $i$ 局。

现在我可以操控这个比赛规则，让游戏赛制变成在赢下 $i$ 球制，也就是我在赢下 $i$ 球后，如果和对手比分差值大于等于 $2$ 我就拿下一个小分，否则就是对手拿下一个小分，如果差值为 $0$ 或者 $1$ 那么接着进行下一局，那么我在 $i$ 球赛制下，进行完 $n$ 局比赛我能赢得的小分用 $f(i)$ 表示。

题目求 $\displaystyle \sum\limits_{i=1}^nf(i)*(n+1)^{i-1}$

Solution

考点：预处理模拟题

首先我们可以预处理出从 $[1,i]$ 这些位置里面有多少个 $W$ 和多少个 $L$ ，这样用前缀和的形式就可以找到任意区间内 $W$ 和 $L$ 的数量。

并且我们可以知道第 $i$ 个 $W$ 出现的下标在哪里，以及第 $i$ 个 $L$ 出现的下标在哪里。

那么当我们枚举这个 $i$ 球赛制的时候，我们就可以知道上一次加小分的位置在哪里，从这个位置往后 $i$ 个 $W$ 就是我下一次赢球的最小下标，同理可以找到对手赢球的最小下标。

将这两个下标取 $\min$ 之后局面就会出现两种；

要么有人已经拿下了这一个小分，那么直接看下是不是我赢下了这局比赛就行。
要么两人差距为 $1$ ，那么这时候再看下一局是谁赢下，如果比完下一局比分差值为 $2$ 了，同理统计下是不是我赢下了这局比赛，如果比完差值为 $0$ 了，我们就不能简单的再慢慢一步步往后挪，我们要预处理一个平局数组，找到当第 $j$ 局比赛平局的时候下一次分出胜负在那个局面下，用这个数组跳跃查找就行了。这个数组预处理也很容易，只需要倒序的处理 $n$ 局比赛的情况即可。

这样我们发现每次枚举 $i$ 球赛制的话 $pos$ 最小往后移动 $i$ 步，那么总的移动次数大概就是 $\displaystyle \frac{n}{1}+\frac{n}{2}+\frac{n}{3}...\frac{n}{n}=n\log n$

时间复杂度就是 $O(n\log n)$

#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
const int N = 1e6 + 7;
ll n, m;
char s[N];
int cntw[N], cntl[N];
int posw[N << 1], posl[N << 1];

int tiebreak[N];

int solve() {
    n = read();
    scanf("%s", s + 1);

    ms(posw,0x3f);ms(posl,0x3f);
    for (int i = 1; i <= n; ++i) {
        cntw[i] = cntw[i - 1];
        cntl[i] = cntl[i - 1];
        if (s[i] == 'W') {
            ++cntw[i];
            posw[cntw[i]] = i;
        }
        else {
            ++cntl[i];
            posl[cntl[i]] = i;
        }
    }

    tiebreak[n - 1] = tiebreak[n] = n + 1; // 平局数组
    for (int i = n - 2; i >= 1; --i) {
        tiebreak[i] = s[i + 1] == s[i + 2] ? i + 2 : tiebreak[i + 2];
    }

    int res = 0, xs = 1;

    for (int i = 1; i <= n; ++i) {
        int l = 0, r = 0;
        int cnt = 0;
        while (l < n) {
            int W = posw[cntw[r] + i];
            int L = posl[cntl[r] + i];
            r = min(L, W);
            if (r > n)    break;

            if (abs((cntw[r] - cntw[l]) - (cntl[r] - cntl[l])) >= 2) {
                if (cntw[r] - cntw[l] > cntl[r] - cntl[l])
                    ++cnt;
                l = r;
                continue;
            }

            // 之前的r一定有人领先1分
            ++r; // 要么平局 要么赢下
            if (r > n)    break;

            if (abs((cntw[r] - cntw[l]) - (cntl[r] - cntl[l])) >= 2) {
                if (cntw[r] - cntw[l] > cntl[r] - cntl[l])
                    ++cnt;
                l = r;
                continue;
            }

            r = tiebreak[r];
            if (r > n)    break;
            if (cntw[r] - cntw[l] > cntl[r] - cntl[l])
                ++cnt;
            l = r;
        }
        res = (res + cnt * xs) % MOD;
        xs = xs * (n + 1) % MOD;
    }

    print(res);


    return 1;
}

D、Double Strings

题目大意

给你两个字符串 $A,B$ ，长度在 $5·10^3$ 级别，询问在两者的全部子序列中，长度相等，并且 $a<b$ 的数量有多少个？

Solution

考点：相同子序列数量

如果直接考虑 $a<b$ ，因为子序列并不知道第几个位置不同，所以这个并不好处理，但是我们一定可以把这个的子序列分成 $3$ 段。

第一段：子序列前 $i-1$ 个字符都相同。

第二段： $a_i<b_i$

第三段：剩余长度任意挑选子序列。

先考虑如何求解任意两个位置 $A[1:i],B[1:j]$ 相同子序列数量，这个用动态规划处理。

我们用 $f_{i,j}$ 代表以 $A$ 前 $i$ 个字符， $B$ 前 $j$ 个字符的相同子序列数量，那么我们可以写出下面的转移方程。

$f_{i,j} = f_{i-1,j}+f_{i,j-1}-f_{i-1,j-1} \ \ \ \ \ \ \ A_i\neq B_j\\f_{i,j}=f_{i-1,j}+f_{i,j-1}-f_{i-1,j-1}+(f_{i-1,j-1}+1)\ \ \ \ \ \ \ \ A_i=B_j$

当 $A_i\neq B_j$ 的时候减掉的是重复计算的，当 $A_i=B_j$ 的时候加上的是一定选他们结尾的时候前面相同的，加上前面一个不选。

好了我们已经 $O(|A|·|B|)$ 预处理出了 $f_{i,j}$ 数组了，下面就要考虑后面长度任选怎么处理。

如果我们枚举到 $A$ 串后面还剩长度为 $x$ ， $B$ 串后面长度为 $y$ ，那么等价与求 $\displaystyle \sum\limits_{i=0}^{\min(x,y)}C_x^i*C_y^i$

上面这个式子可以做个等价变换，首先我们知道 $C_x^i=C_x^{x-i}$ ，那么就变成了我有两堆球，我要在左边拿出 $x-i$ 个球，右边拿出 $i$ 个球的方案数总和，并且提供这个乘法之后求合我们可以判断这些球都是完全不一样的，那不就等价于我一共有 $x+y$ 个球，要拿出 $x$ 个球的方案数吗，所以我们得到 $\displaystyle\sum_{i=0}^{\min(x,y)}C_x^i*C_y^i=C_{x+y}^x$

接下来就只要计算答案就行了，总的时间复杂度是 $O(|A|·|B|)$ 。

const int N = 5e3 + 7;
ll n, m;
int f[N][N];

ll jc[N << 1], inv[N << 1];
void init() {
    jc[0] = 1;
    for (int i = 1; i < N * 2; ++i)    jc[i] = jc[i - 1] * i % MOD;
    inv[N * 2 - 1] = qpow(jc[N * 2 - 1], MOD - 2, MOD);
    for (int i = N * 2 - 2; ~i; --i)    inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m) {
    return jc[n] * inv[m] % MOD * inv[n - m] % MOD;
}

char s[N], t[N];

int solve() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i] == t[j]) {
                f[i][j] = (f[i - 1][j] + f[i][j - 1] + 1) % MOD;
            }
            else {
                f[i][j] = ((f[i - 1][j] + f[i][j - 1]) % MOD - f[i - 1][j - 1] + MOD) % MOD;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i] < t[j]) {
                res = (res + (f[i - 1][j - 1] + 1) * C(n - i + m - j, n - i) % MOD) % MOD;
            }
        }
    }
    print(res);

    return 1;
}

F、Finding Points

题目大意

按逆时针给出凸包上的 $n$ 个点，你要在凸包里面找到一个点 $P$ ，让 $\angle A_iPA_{i+1}$ 的最小值最大，然后输出这个最大的最小值。

Solution

考点：三分

比较明显的容易发现如果我们固定 $x$ ，那么 $y$ 的相关函数一定是一个单峰函数。

同理固定 $y$ ，那么 $x$ 的相关函数也一定是单峰函数。

那么就直接用三分套三分就可以求解了，复杂度 $O(n\log_3^2 W)$ 。

const int INF = 0x3f3f3f3f;
const int N = 100 + 7;
const double PI = acos(-1);
ll n, m;
pai p[N];

double xmax = -INF, xmin = INF, ymax = -INF, ymin = INF;

pai operator - (const pai& a, const pai& b) {
    return { a.first - b.first,a.second - b.second };
}

double operator * (const pai& a, const pai& b) {
    return a.first * b.first + a.second * b.second;
}

double getLen(pai a) {
    return sqrt(a * a);
}

double getAngle(pai a, pai b) {
    return acos(a * b / getLen(a) / getLen(b));
}

double check(pai x) {
    double res = INF;
    for (int i = 1; i <= n; ++i) {
        res = min(res, getAngle(p[i] - x, p[i + 1] - x));
    }
    return res;
}

double calc(double x) {
    double l = ymin, r = ymax;
    for (int i = 1; i <= 100; ++i) {
        double lmid = l + (r - l) / 3.0;
        double rmid = r - (r - l) / 3.0;
        if (check({ x,lmid }) > check({ x,rmid })) {
            r = rmid;
        }
        else {
            l = lmid;
        }
    }
    return check({ x,l });
}

int solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        auto& [x, y] = p[i];
        x = read(), y = read();
        xmax = max(xmax, x);
        xmin = min(xmin, x);
        ymax = max(ymax, y);
        ymin = min(ymin, y);
    }
    p[n + 1] = p[1];

    double l = xmin, r = xmax;

    for (int i = 1; i <= 100; ++i) {
        double lmid = l + (r - l) / 3.0;
        double rmid = r - (r - l) / 3.0;
        if (calc(lmid) > calc(rmid)) {
            r = rmid;
        }
        else {
            l = lmid;
        }
    }

    printf("%.12f\n", calc(l) * 180 / PI);


    return 1;
}

G、Greater Integer, Better LCM

题目大意

给你 $a,b,c$ ，你要让 $lcm(a+x,b+y)=c$ 的前提下，最小的 $x+y$ 是什么，并且给出的 $c$ 是分解质因数的形式， $c=\prod\limits p_i^{q_i}$ 。

$1\le a,b,c\le 10^{32},\sum\limits_{i=1}^nq_i\le18$

Solution

考点：二进制枚举

看到这个 $c$ 给的这么形式化，就要围绕这个去弄，而且幂次之和不超过 $18$ ，很明显的让我们去二进制枚举。

那么我们就可以暴力的 $dfs$ 预处理出当前状态 $s$ ，可以的全部花费，那么要更新还有一个前提，就是之前的 $prod$ 最起码应该大于 $a$ ，才可以更新前半部分，大于 $b$ 才可以更新后半部分，我们这样暴力乱搞之后对于花费大于 $a,b$ 的全部状态的最小花费都可以找出来。

接下来我们只需要再把这些东西的子集更新一下，注意因为我们 $dfs$ 乱搞的时候有一个 $\ge a$ 的条件，可能 $001$ 这个状态就无法大于等于 $a$ ，这时候保留的仍然是一个无穷大的值，但是我们用 $001$ 这个状态更新应该可以由 $111$ 转移来的，所以我们要倒序的枚举一下子集，保证每个状态都找到最小值。

接下来去枚举这 $n$ 个幂次，左右怎么分保证 $n$ 个数都是 $1$ 的最小值了。

找出这个最小值，再减掉 $a+b$ 就是最终答案了。

#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
inline __int128 read() { __int128 s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(__int128 x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; __int128 tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
const int N = (1<<18) + 7;
int n, m;
int p[20], q[20];
__int128 fa[N], fb[N], a, b, c;

void dfs(int dep, __int128 prod, int s) {
    if (dep == n) {
        if (prod >= a)    fa[s] = min(fa[s], prod);
        if (prod >= b)    fb[s] = min(fb[s], prod);
        return;
    }
    for (int i = 0; i <= q[dep]; ++i) {
        if (i == q[dep])    s |= (1 << dep);
        dfs(dep + 1, prod, s);
        prod *= p[dep];
    }
}

int solve() {
    n = read();
    m = (1 << n) - 1;
    for (int i = 0; i < n; ++i) {
        p[i] = read(), q[i] = read();
    }
    a = read(), b = read(), c = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < q[i]; ++j)    c *= p[i];
    }

    __int128 inf = c * 2;

    ms(fa, 0x3f), ms(fb, 0x3f);
    dfs(0, 1, 0);

    for (int i = m; i >= 1; --i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                fa[i ^ (1 << j)] = min(fa[i ^ (1 << j)], fa[i]);
                fb[i ^ (1 << j)] = min(fb[i ^ (1 << j)], fb[i]);
            }
        }
    }

    __int128 res = inf;
    for (int i = 0; i <= m; ++i) {
        res = min(res, fa[i] + fb[i ^ m]);
    }
    print(res - a - b);

    return 1;
}

H、Holding Two

题目大意

你要构造一个 $n·m$ 的 $01$ 矩阵，保证同行同列同对角的 $3$ 个位置不能是同一个字符。

Solution

考虑下面这样的构造

001100110011
110011001100
001100110011
110011001100

int solve() {
    int n = read(), m = read();
    for (int i = 0; i < n; ++i) {
        if (i & 1) {
            for (int j = 0; j < m; ++j) {
                char ch = j % 4 <= 1 ? '0' : '1';
                putchar(ch);
            }
        }
        else {
            for (int j = 0; j < m; ++j) {
                char ch = j % 4 <= 1 ? '1' : '0';
                putchar(ch);
            }
        }
        puts("");
    }

    return 1;
}

J、Jewels

题目大意

你有 $n(1\le n\le 300)$ 个宝藏，他们分布在一些三维点 $(x_i,y_i,z_i)$ ，他们还有一个各自的上升速度 $t_i$ ，他们第 $k$ 秒所在的位置为 $(x_i,y_i,z_i+k·t_i)$ 。你拿掉宝藏的代价为 $x_i+y_i+z_i+k·t_i$ ，你每秒只可以拿掉一个宝藏，问拿完 $n$ 个宝藏的最小代价是多少？

Solution

考点：最小权值匹配

很明显每秒只可以拿掉一个宝藏，拿完 $n$ 个宝藏一定要 $n-1$ 秒，那么我们把 $0\to n-1$ 秒看成 $n$ 个点，这 $n$ 个物品也看成 $n$ 个点，那么就变成了一张有完全图的二分图。跑最小权值匹配问题，可以用 $KM$ 算法，我先用了下我自己的 $mcmf$ 算法跑最小费用最大流给 $T$ 飞了 $…$ 枯了。然后就去听群友的建议抄了一个常数比较优秀的mcmf算法。

封装的还是很好的，常数非常优秀只跑到 $400ms$ 左右。

const int N = 600 + 7;
namespace atcoder {

    template <class Cap, class Cost> struct mcf_graph {
    public:
        mcf_graph() {}
        mcf_graph(int n) : _n(n), g(n) {}

        int add_edge(int from, int to, Cap cap, Cost cost) {
            assert(0 <= from && from < _n);
            assert(0 <= to && to < _n);
            int m = pos.size();
            pos.push_back({ from, g[from].size() });
            int from_id = g[from].size();
            int to_id = g[to].size();
            if (from == to) to_id++;
            g[from].push_back(_edge{ to, to_id, cap, cost });
            g[to].push_back(_edge{ from, from_id, 0, -cost });
            return m;
        }

        struct edge {
            int from, to;
            Cap cap, flow;
            Cost cost;
        };

        edge get_edge(int i) {
            int m = pos.size();
            assert(0 <= i && i < m);
            auto _e = g[pos[i].first][pos[i].second];
            auto _re = g[_e.to][_e.rev];
            return edge{
                pos[i].first, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,
            };
        }
        std::vector<edge> edges() {
            int m = pos.size();
            std::vector<edge> result(m);
            for (int i = 0; i < m; i++) {
                result[i] = get_edge(i);
            }
            return result;
        }

        std::pair<Cap, Cost> flow(int s, int t) {
            return flow(s, t, std::numeric_limits<Cap>::max());
        }
        std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
            return slope(s, t, flow_limit).back();
        }
        std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
            return slope(s, t, std::numeric_limits<Cap>::max());
        }
        std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
            assert(0 <= s && s < _n);
            assert(0 <= t && t < _n);
            assert(s != t);
            std::vector<Cost> dual(_n, 0), dist(_n);
            std::vector<int> pv(_n), pe(_n);
            std::vector<bool> vis(_n);
            auto dual_ref = [&]() {
                std::fill(dist.begin(), dist.end(),
                    std::numeric_limits<Cost>::max());
                std::fill(pv.begin(), pv.end(), -1);
                std::fill(pe.begin(), pe.end(), -1);
                std::fill(vis.begin(), vis.end(), false);
                struct Q {
                    Cost key;
                    int to;
                    bool operator<(Q r) const { return key > r.key; }
                };
                std::priority_queue<Q> que;
                dist[s] = 0;
                que.push(Q{ 0, s });
                while (!que.empty()) {
                    int v = que.top().to;
                    que.pop();
                    if (vis[v]) continue;
                    vis[v] = true;
                    if (v == t) break;
                    for (int i = 0; i < g[v].size(); i++) {
                        auto e = g[v][i];
                        if (vis[e.to] || !e.cap) continue;
                        Cost cost = e.cost - dual[e.to] + dual[v];
                        if (dist[e.to] - dist[v] > cost) {
                            dist[e.to] = dist[v] + cost;
                            pv[e.to] = v;
                            pe[e.to] = i;
                            que.push(Q{ dist[e.to], e.to });
                        }
                    }
                }
                if (!vis[t]) {
                    return false;
                }

                for (int v = 0; v < _n; v++) {
                    if (!vis[v]) continue;
                    dual[v] -= dist[t] - dist[v];
                }
                return true;
            };
            Cap flow = 0;
            Cost cost = 0, prev_cost_per_flow = -1;
            std::vector<std::pair<Cap, Cost>> result;
            result.push_back({ flow, cost });
            while (flow < flow_limit) {
                if (!dual_ref()) break;
                Cap c = flow_limit - flow;
                for (int v = t; v != s; v = pv[v]) {
                    c = std::min(c, g[pv[v]][pe[v]].cap);
                }
                for (int v = t; v != s; v = pv[v]) {
                    auto& e = g[pv[v]][pe[v]];
                    e.cap -= c;
                    g[v][e.rev].cap += c;
                }
                Cost d = -dual[s];
                flow += c;
                cost += c * d;
                if (prev_cost_per_flow == d) {
                    result.pop_back();
                }
                result.push_back({ flow, cost });
                prev_cost_per_flow = d;
            }
            return result;
        }

    private:
        int _n;

        struct _edge {
            int to, rev;
            Cap cap;
            Cost cost;
        };

        std::vector<std::pair<int, int>> pos;
        std::vector<std::vector<_edge>> g;
    };

}
using namespace atcoder;
mcf_graph<int64_t, int64_t> mc(N);

int solve() {
    int n = read();
    int be = 0, ed = 2 * n + 2;
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        int x = read(), y = read(), z = read(), v = read();
        mc.add_edge(0, i, 1, 0);
        mc.add_edge(n + i, ed, 1, 0);
        res += x * x + y * y;
        long long dep = z;
        for (int j = 1; j <= n; ++j) {
            mc.add_edge(i, n + j, 1, dep * dep);
            dep += v;
        }
    }
    print(res + mc.flow(be, ed).second);

    return 1;
}

K、King of Range

题目大意

给你长度为 $n(1\le n\le 10^5)$ 的序列 $a_i$ ，并且有 $Q(1\le Q\le 200)$ 次查询，每次查询给出一个 $k(1\le k\le 10^9)$ ，询问在 $a$ 中有多少个区间的最大值减掉最小值严格大于 $k$ 。

Solution

考点：双指针+ $ST$ 表

考虑到区间不会修改，那么查找区间最值这个问题就用 $ST$ 表维护就可以。

然后再看最大值减掉最小值严格大于 $k$ ，如果在 $[i,r]$ 这个区间符合要求，那么是不是在 $[r,n]$ 这些右区间都是合法的，因为随着数的加入，区间最大值一定不会变小，区间最小值一定不会变大，所以并不会变得不符合要求。

那么我们从左到右枚举 $i$ ，可以看出这个 $r$ 也是单调的，我们用 $ST$ 表维护这个 $r$ 就可以了。

时间复杂度 $O(n·m+n\log n)$ 。

const int N = 1e5 + 7;

int st1[N][21], st2[N][21], Log2[N], a[N];

void pre() {
    Log2[1] = 0;
    Log2[2] = 1;
    for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}

int queryMax(int l, int r) {
    int s = Log2[r - l + 1];
    return max(st1[l][s], st1[r - (1 << s) + 1][s]);
}

int queryMin(int l, int r) {
    int s = Log2[r - l + 1];
    return min(st2[l][s], st2[r - (1 << s) + 1][s]);
}

void sol() {
    pre();
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)   a[i] = st1[i][0] = st2[i][0] = read();
    int t = Log2[n]; //区间最长的2次方
    for (int j = 1; j <= t; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]),
            st2[i][j] = min(st2[i][j - 1], st2[i + (1 << (j - 1))][j - 1]);
    while (m--) {
        int k = read();
        ll ans = 0;
        int r = 1;
        for (int i = 1; i <= n; ++i) {
            while (r <= n && queryMax(i, r) - queryMin(i, r) <= k)
                ++r;
            if (r == n + 1)    break;
            //cout << r << endl;
            ans += n - r + 1;
        }
        print(ans);
    }
}

2021牛客暑期多校训练营5

B、Boxes

题目大意

Solution

C、Cheating and Stealing

题目大意

Solution

D、Double Strings

题目大意

Solution

F、Finding Points

题目大意

Solution

G、Greater Integer, Better LCM

题目大意

Solution

H、Holding Two

题目大意

Solution

J、Jewels

题目大意

Solution

K、King of Range

题目大意

Solution