大约是翻译了一下官方题解？

@Description@

对于一个整数序列 $P=(P_{1},\dots,P_{m})$，定义 $f(P)$ 为一个序列 $Q$ 满足：

• $Q_{i}=P_{i}+P_{i+1}$，其中 $i\in[1,m)$；
• $f(P)=(P_{1},Q_{1},\dots,P_{m-1},Q_{m-1},P_{m})$。

给出正整数 $a,b,N$，其中 $a,b\leqslant N$，令序列 $A=(a,b)$，令序列 $B$ 为一下操作的结果：

• 做 $N$ 次令 $A=f(A)$.
• 删除 $A$ 中大于 $B$ 的数。

求 $B_{l,\dots r}$。

@Solution@

◆ The Coefficient Sequence

构造最终的 $A$ 序列的过程是这样的：

$$ a,b \\ a,a+b,b \\ a,2a+b,a+b,a+2b,b \\ a,3a+b,2a+b,3a+2b,a+b,2a+3b,a+2b,a+3b,b \\ \dots $$

可以发现有对称性。此时我们先不关心 $a,b$ 以及 $N$ 的大小，反之，我们来观察其序列系数，也就是把每个元素看成 $xa+yb$，其系数的 $(x,y)$，上例的序列系数即

$$ (1,0),(0,1) \\ (1,0),(1,1),(0,1) \\ (1,0),(2,1),(1,1),(1,2),(0,1) \\ (1,0),(3,1),(2,1),(3,2),(1,1),(2,3),(1,2),(1,3),(0,1) \\ \dots $$

以下我们称其为 Coefficient Sequence。

◆ The properties of the Coefficient Sequence

现在我们来观察 Coefficient Sequence 的性质。

Observation 1：在 Coefficient Sequence 中相邻的两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$，都有： $x_{S}y_{T}-x_{T}y_{S}=1$。

使用数学归纳法（induction）即证。

Observation 2：对于两个 两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$，如果他们满足 $x_{S}y_{T}-x_{T}y_{S}=1$，那么它们在 Coefficient Sequence 中相邻，即 Observation 1 是充要条件。

不会证，大概意会一下吧。

Observation 3：对于一个二元组 $(x,y)$，如果 $\gcd(x,y)=1$，那么 $(x,y)$ 会出现在 Coefficient Sequence 中。

比较显然，以至于官方题解没有给出证明。

Observation 4：在任意时刻，所有在 Coefficient Sequence 中的 $(x,y)$ 总是呈从左到右的关于值 $\frac{y}{x}$ 递增（令 $\frac{x}{0}=\infty$）。

◆ The sequence $B$ in other words

现在描述序列 $B$ 变得更加容易，现在我们这样描述它：

对于所有二元组 $(x,y)$ 满足 $x,y,s.t.x,y\in\mathbb{N},\gcd(x,y)=1,ax+by\leqslant N$，我们对其按 $\frac{y}{x}$ 排序后形成一个二元组序列 $\{(x_{i},y_{i})\}$，则 $B_{i}=ax_{i}+by_{i}$。

◆ Computing $B_{n}$

现在我们来考虑原问题的简化版，我们来计算 $B_{n}$。让我们把这个描述成一个计数问题（通过二分 $\frac{y}{x}$）：

给定正整数 $a,b,N$，以及一个有理数 $c$（二分的值），求二元组 $(x,y)\neq(0,0)$ 的数量，其中 $(x,y)$ 满足

• $ax+by\leqslant N$；
• $\gcd(x,y)=1$；
• $\frac{y}{x}\leqslant c$。

我们令 $F(N)$ 为以上问题的答案，同时令 $G(N)$ 为去掉 $\gcd(x,y)=1$ 限制的答案。$G(N)$ 的式子可以很方便的写出来： $G(N)=\sum_{y=1}^{N}\max\{\lfloor\frac{N-by}{a}\rfloor-\lfloor\frac{y}{c}\rfloor+1,0\}$，同时我们还可以写出 $G(N)=\sum_{d=1}^{N}F(\lfloor\frac{N}{d}\rfloor)$。那么再根据 Möbius inversion formula，我们可以表示出 $F(N)=\sum_{d=1}^{N}\mu(d)G(\lfloor\frac{N}{d}\rfloor)$。于是计算该问题答案的复杂度就是 $\mathcal{O}(N)$。

但是此时我们知道了 $B_{n}$ 的 $\frac{y_{n}}{x_{n}}$，怎么知道 $(x_{n},y_{n})$ 呢？我们可以再做一个二分。观察出这样一个规律：若令 $l=(1,0),r=(0,1)$，那么中间位置就是 $l+r$。于是我们可以再次做一个二分，利用 $\frac{y}{x}$ 单调来做 check。

顺带一提，这个还可以使用 类欧几里得 来计算。

◆ Computing $B_{l,\dots,r}$

可以发现这个东西可以知二求一，于是求出 $B_{l},B_{l+1}$ 就行了。当然也可以求出 $B_{l},B_{r}$ 然后做二分搜索。

Description

  Link.

  有 $n$ 棵树，每棵的高度为 $a(i)$，看到一棵树对答案的贡献为 $a(i-1)+a(i)+a(i+1)$（未定义范围为 $0$），求使得答案最小的砍树顺序的数量。

Solution

  口胡瑇师。不过这个 F 比上次的 Lagrange 插值阳间多了。

  考虑每一个元素的贡献次数。发现这个次数的区间是 $[1,3]$，对应树 $i$ 在树 $i-1/i+1$ 之前 / 之后砍倒的情况。

  那么我们直接贪心，使得答案最小的砍树顺序一定是：

• $a(i)<a(i+1)$ 先砍 $i+1$，再砍 $i$；
• otherwise：先砍 $i$，再砍 $i+1$。

  然后就可以 DP 仂。设 $f(i,j)$ 为树 $i$ 在是第 $j$ 个被砍的排列数，注意这里的 $j$ 是相对的。

• $a(i-1)=a(i)$：$f(i,j)=\sum_{k=1}^{i}f(i-1,k)$；
• $a(i-1)<a(i)$：$f(i,j)=\sum_{k=j}^{i}f(i-1,k)$；
• $a(i-1)>a(i)$：$f(i,j)=\sum_{k=1}^{j}f(i-1,k)$。

  使用前缀和优化。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
    return f?-x:x;
}
const int N=4100,MOD=1e9+7;
ll dp[N][N],sum[N],a[N];
signed main() {
    int n=read();
    for(int i=1; i<=n; ++i) a[i]=read();
    dp[1][1]=1;
    for(int i=2; i<=n; ++i) {
        for(int j=1; j<i; ++j) (sum[j]=sum[j-1]+dp[i-1][j])%=MOD;
        for(int j=1; j<=i; ++j)
            if(a[i]==a[i-1]) dp[i][j]=sum[i-1];
            else if(a[i]>a[i-1]) dp[i][j]=(sum[i-1]-sum[j-1]+MOD)%MOD;
            else dp[i][j]=sum[j-1];
    }
    ll ans=0;
    for(int i=1; i<=n; ++i) (ans+=dp[n][i])%=MOD;
    printf("%lld\n",ans);
    return 0;
}

Description

  Link.

  有 $n$ 棵树，每棵的高度为 $a(i)$，看到一棵树对答案的贡献为 $a(i-1)+a(i)+a(i+1)$（未定义范围为 $0$），求使得答案最小的砍树顺序的数量。

Solution

  口胡瑇师。不过这个 F 比上次的 Lagrange 插值阳间多了。

  考虑每一个元素的贡献次数。发现这个次数的区间是 $[1,3]$，对应树 $i$ 在树 $i-1/i+1$ 之前 / 之后砍倒的情况。

  那么我们直接贪心，使得答案最小的砍树顺序一定是：

• $a(i)<a(i+1)$ 先砍 $i+1$，再砍 $i$；
• otherwise：先砍 $i$，再砍 $i+1$。

  然后就可以 DP 仂。设 $f(i,j)$ 为树 $i$ 在是第 $j$ 个被砍的排列数，注意这里的 $j$ 是相对的。

• $a(i-1)=a(i)$：$f(i,j)=\sum_{k=1}^{i}f(i-1,k)$；
• $a(i-1)<a(i)$：$f(i,j)=\sum_{k=j}^{i}f(i-1,k)$；
• $a(i-1)>a(i)$：$f(i,j)=\sum_{k=1}^{j}f(i-1,k)$。

  使用前缀和优化。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
    return f?-x:x;
}
const int N=4100,MOD=1e9+7;
ll dp[N][N],sum[N],a[N];
signed main() {
    int n=read();
    for(int i=1; i<=n; ++i) a[i]=read();
    dp[1][1]=1;
    for(int i=2; i<=n; ++i) {
        for(int j=1; j<i; ++j) (sum[j]=sum[j-1]+dp[i-1][j])%=MOD;
        for(int j=1; j<=i; ++j)
            if(a[i]==a[i-1]) dp[i][j]=sum[i-1];
            else if(a[i]>a[i-1]) dp[i][j]=(sum[i-1]-sum[j-1]+MOD)%MOD;
            else dp[i][j]=sum[j-1];
    }
    ll ans=0;
    for(int i=1; i<=n; ++i) (ans+=dp[n][i])%=MOD;
    printf("%lld\n",ans);
    return 0;
}

Description

Link.

有一个块 $n\times m$ 的矩形，有 $q$ 次操作，每次把矩形横 / 竖着切一刀，问切完后的最大矩形面积。

Solution

一个不同于大多数人、总时间复杂度 $\mathcal{O}(n\log_{2}n)$，每次回答 $\mathcal{O}(\alpha(n))$ 的做法，瓶颈在排序。

显然答案是最大行列相乘。首先我们把询问离线，然后逆序处理。你发现这相当于把切开变成了合并，最大值不降，于是可以直接维护。

具体来说就是维护两个并查集，分别是行和列，然后再维护集合内元素个数，然后就直接合并。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
    return f?-x:x;
}
const int N=200100;
signed main() {
    int m=read(),n=read(),q=read();
    static int far[N],fac[N],szr[N],szc[N];
    iota(far+1,far+m+1,1);
    iota(fac+1,fac+n+1,1);
    for(int i=1;i<=m;++i) szr[i]=1;
    for(int i=1;i<=n;++i) szc[i]=1;
    auto findr=[&](int x) {while(x!=far[x]) x=far[x]=far[far[x]]; return x;};
    auto findc=[&](int x) {while(x!=fac[x]) x=fac[x]=fac[fac[x]]; return x;};
    auto merger=[&](int x,int y) {x=findr(x),y=findr(y); (x!=y)&&(szr[y]+=szr[x],szr[x]=0,far[x]=y);};
    auto mergec=[&](int x,int y) {x=findc(x),y=findc(y); (x!=y)&&(szc[y]+=szc[x],szc[x]=0,fac[x]=y);};
    static int op[N],X[N];
    vector<int> hx,vx;
    for(int i=1; i<=q; ++i) {
        char Op[4];
        scanf("%s",Op);
        op[i]=Op[0]=='H';
        X[i]=read();
        (op[i])&&(X[i]=n-X[i]);
        (op[i])&&(hx.push_back(X[i]),1);
        (!op[i])&&(vx.push_back(X[i]),1);
    }
    sort(hx.begin(),hx.end());
    sort(vx.begin(),vx.end());
    hx.insert(hx.begin(),0);
    vx.insert(vx.begin(),0);
    hx.push_back(n);
    vx.push_back(m);
    for(unsigned int i=1; i<hx.size(); ++i)
        for(int j=hx[i-1]+2; j<=hx[i]; ++j) mergec(j-1,j);
    for(unsigned int i=1; i<vx.size(); ++i)
        for(int j=vx[i-1]+2; j<=vx[i]; ++j) merger(j-1,j);
    ll mxr=0,mxc=0;
    for(int i=1; i<=m; ++i) mxr=max(mxr,(ll)szr[findr(i)]);
    for(int i=1; i<=n; ++i) mxc=max(mxc,(ll)szc[findc(i)]);
    vector<ll> ans;
    ans.push_back(mxr*mxc);
    for(int i=q; i>1; --i) {
        if(op[i]) mergec(X[i]+1,X[i]),mxc=max(mxc,(ll)szc[findc(X[i])]);
        else merger(X[i],X[i]+1),mxr=max(mxr,(ll)szr[findr(X[i])]);
        ans.push_back(mxr*mxc);
    }
    reverse(ans.begin(),ans.end());
    for(ll x:ans) printf("%lld\n",x);
    return 0;
}

Description

Link.

给出一个长度为 $n$ 的序列 $a$，求 $\sum_{i=1}^{n}[\forall j\in[1,i)\cup(i,n],a_{j}\nmid a_{i}]$。

Solution

首先特判序列中有 $1$ 的情况。

然后调和级数把每个数的倍数开桶记录。

最后扫一遍序列，看该元素在桶里面出现的次数不超过一就有贡献。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=0; char ch=getchar();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
    return f?-x:x;
}
const int N=200100,M=1000000;
int a[N],bc[M];
signed main()
{
    int n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    int cnt=0,ans=0;
    for(int i=1;i<=n;++i) (a[i]==1)&&(++cnt);
    if(cnt) return printf("%d\n",cnt>1?0:1),0;
    for(int i=1;i<=n;++i) for(int j=a[i];j<=M;j+=a[i]) ++bc[j];
    for(int i=1;i<=n;++i) (bc[a[i]]<=1)&&(++ans);
    printf("%d\n",ans);
    return 0;
}