A

考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）

B

把未被锁定的位置从大到小排序即可。因为无论如何放最后一个未锁定的位置的前缀和不会变，那么肯定先把所有最大的都用上去尽量 cover 掉小的贡献。

C

dp。设 $f_{i,0/1}$ 表示打了前 $i$ 关，轮到玩家还是玩家的朋友打的最小代价，直接枚举转移即可。

D

假设两个位置选择的分别是 $x_1,x_2(x_1 < x_2)$，把坐标排好序后肯定存在一个分解点 $mid$，满足 $i \leq mid$ 都走到 $x_1$，并且 $i > mid$ 都走到 $x_2$。设第 $i$ 个坐标位置 $p_i$，发现这样的代价为 $p_n-p_1-(p_{mid+1}-p_{mid})$，所以实际上是要你支持插入，删除，维护相邻差的最大值，用两个 multiset 就可以了。

E

根据期望的线性性，我们只需要计算每一个 boss 对玩家的期望伤害即可。

boss 可以分为两类：一类是会削玩家护盾耐久的，一类是螳臂当车的。

对于会削玩家护盾耐久的，设这样的 boss 有 $m$ 个，能打到玩家的概率是 $\frac{m-a_i}{m}$（因为它在这 $m$ 个数的相对排名只有 $m$ 种情况，后面 $m-a_i$ 种是合法的）

对于螳臂当车的 boss，设这样的 boss 有 $k$ 个，能打到玩家的概率是 $\frac{m+1-a_i}{m+1}$。（因为它只能选择 $m+1$ 个空插进去，后面 $m+1-a_i$ 个空是合法的）

分开乘起来就行。多组询问只需要离线排序，变成了维护每次将一个削玩家耐久的变成螳臂当车的boss的操作，记录一下权值和就行了。

F

发现一个结论：对于任何一对 $x_1y_1 = x_2y_2(x_1 < x_2)$，都存在一对正整数 $a < b$，满足 $x_2 = \frac{x_1}{a}b,y_2 = \frac{y_1}{b}a$。

因为 $a|x_1,b|y_1$，所以有效的 $(a,x_1)$ 只有 $O(n \log n)$ 对。

现在我们去固定 $x_1$，考虑 $y_1$ 的种种限制：首先要保证 $y_1 \leq m$，其次还要保证 $\lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor$。

我们考虑枚举一对 $(a,x_1)$，现在相当于要求快速询问是否存在一对 $(b,y_1)$ 满足如下条件：

$$ \begin{aligned} y_1 \leq m\\ \lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor\\ \frac{x_1}{a}b \leq n\\ a < b \end{aligned} $$

显然我们会贪心选择能选择的 $b$ 中最小的去判断第三个限制是否成立。

第一个和第二个限制可以通过从小到大枚举 $x$ 双指针解决，第四个限制可以维护当前所有可选值的 set 解决，复杂度 $O(n \log^2 n)$。

G

确定性做法

我们考虑枚举右端点，维护每个左端点是否合法。

我们的目标是让对于每一种颜色，如果左端点区间是合法的，贡献就是 $0$，否则贡献是 $1$。

那么一个左端点合法当且仅当这个位置的值是 $0$。

我们每次加入一个点 $i$，设它前面第一个，第二个，第三个，第四个和它相等的是 $p_1,p_2,p_3,p_4$，我们只需要让 $(p_1,i]+1$，$(p_3,p_2]-1$，$(p_4,p_3]+1$ 即可。

线段树维护最小值和最小值个数，支持区间加即可。

基于这个做法我把题目小小加强了一下链接（不确定正确性

详细维护方式可以见代码：

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;
int a[MAXN],n;
#define lc ((x)<<1)
#define rc ((x)<<1|1)

int mn[MAXN<<2],cnt[MAXN<<2],tag[MAXN<<2];

inline void pushup(int x){
    mn[x] = std::min(mn[lc],mn[rc]);cnt[x] = 0;
    if(mn[x] == mn[lc]) cnt[x] += cnt[lc];
    if(mn[x] == mn[rc]) cnt[x] += cnt[rc];
}

inline void cover(int x,int d){
    mn[x] += d;tag[x] += d;
}

inline void pushdown(int x){
    if(tag[x]){
        cover(lc,tag[x]);
        cover(rc,tag[x]);
        tag[x] = 0;
    }
}

inline void modify(int x,int l,int r,int L,int R,int d){
    if(L > R) return;
    if(l == L && r == R){
        cover(x,d);return;
    }
    int mid = (l + r) >> 1;pushdown(x);
    if(R <= mid) modify(lc,l,mid,L,R,d);
    else if(L > mid) modify(rc,mid+1,r,L,R,d);
    else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
    pushup(x);
}

inline void build(int x,int l,int r){
    if(l == r){
        cnt[x] = 1;mn[x] = 1e9;return;
    }
    int mid = (l + r) >> 1;
    build(lc,l,mid);build(rc,mid+1,r);
    pushup(x);
}

int lst[MAXN],pre[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i);
    FOR(i,1,n){
        pre[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    build(1,1,n);LL ans=  0;
    FOR(i,1,n){
        int p1 = pre[i],p2 = pre[p1],p3 = pre[p2],p4 = pre[p3];
        modify(1,1,n,i,i,-1e9);
        modify(1,1,n,p1+1,i,1);
        if(p2) modify(1,1,n,p3+1,p2,-1);
        if(p3) modify(1,1,n,p4+1,p3,1);
        if(mn[1] == 0) ans += cnt[1];
    }
    printf("%lld\n",ans);
    return 0;
}

基于随机的做法

出现三次不难联想到三进制不进位加法。我们对于每个数字随机一个 $60$ 维模 $3$ 意义下的向量，前缀和后两个位置前缀和相同就表示这一段区间所有出现次数 $\bmod 3=0$，但是我们想要的是 $=3$，我们只需要用双指针维护出满足所有颜色出现次数 $\leq 3$ 的区间即可。

出题人说：