树上分块。

第一种是随机撒点，在树上随机撒 $\frac{n}{S}$ 个点，关键点间期望距离不超过 $S$。优势很明显，当 $S$ 取根号的时候，可以处理出所有关键点间的信息，然后跳根号次就可以跳出一条路径。这个做题的方法很可洞见。

第二种是王室联邦式分块，方法是，在 dfs 过程中将子树大小能够划到一块的就划，设 $S$ 为阈值，则每块大小为 $[S, 3S]$，块个数 $\frac{n}{S}$ 左右。优势是每个点最近的为关键点的祖先的距离为 $O(S)$。这个做题的方法也是处理出关键点的信息，然后将询问拆成 $x \rightarrow a \rightarrow b \rightarrow y$，其中 $a$，$b$ 分别是 $x$，$y$ 的最近关键点祖先。

第三种是 top cluster，我显然不会。

莫队的重学。

普通莫队的排序有很多讲究，以后只写回滚莫队好了，至少复杂度是稳定的。这是莫队的排序关键字：$(\textit{bel}_{ \text{left endpoint }}, \text{ right endpoint})$。

回滚莫队和莫队还是有点区别的，具体而言就是对序列分块，块内询问暴力，跨块询问就根据左端点所在的块分类，将左端点在一个块内的询问拉出来，按照右端点排序，这样移动右端点就是单调的，而左端点每次从（所在）块的右端点 $+1$ 的位置开始暴力跑，平衡了复杂度。

上面说的是只加不减莫队，只减不加莫队和这个有点区别。

首先还是按左端点所在块分类，然后右端点按降序排，莫队维护的区间右端点就从序列末端往前单调地跑就行了。只减不加莫队的区别在于，块内询问我们不必暴力了，直接跟着跑就行了。

举个例子，$\texttt{[}\texttt{(}_1\texttt{)}_1\texttt{(}_2\texttt{)}_2\texttt{]}$（方括号代表一个块，角标用以区分不同询问），如果是只加不减莫队的话，维护的右指针根本跑不到块内（从右端点开始单调向右跑），而只减不加莫队的右指针可以跑进来。注意两种莫队的左端点都是暴力的，所以不需要考虑。

高维莫队真的很没意思，就是强行加了一维时间轴，排序的方法是：

if (bel[x.l] != bel[y.l]) return x.l < y.l;
else if (bel[x.r] != bel[y.r]) return x.r < y.r;
return x.tim < y.tim;

如果有什么厉害的排序 trick 或其他 trick 或高庙题记得放上来。

link。

一个 dp（拜谢 ly）和切入点都略有不同的做法，并不需要观察啥性质。

原问题针对子序列进行规划，自然地想到转而对前缀进行规划。接下来我们考虑一个前缀 $[1, i]$ 以及一个 $j \in [1, i]$ 对答案的贡献，可以写出 $\displaystyle \textit{cont}(j \text{ to } [1, i]) = [\max_{i < k} a_k > a_j] \times \text{the number of LISs containing } j \text{ indexed in } [1, i]$。

这个可以做两个 dp 解决，第一个好解决的静态 dp，即结束在 $j$ 的 LIS 方案数；第二个 dp 有些烦：$j$ 在动，我们考虑的前缀 $[1, i]$ 也在移动。

到这里其实换一下着手点第二个 dp 就变成静态的了，即考虑位置 $j$，直接算 $(j, i)$ 的贡献即可，其中 $i$ 是「满足 $a_i > a_j$ 的最大的 $i$」。于是我们的第二个 dp 就可以被描述为从 $j$ 开始，结束在 $i$ 之前（不包括，因为要保证 $\max_{i < k} a_k > a_j$）的 LIS 方案数。答案即 $\displaystyle \sum_{i=1}^n dp_i \times dp'_i$。

第二个 dp 的具体实现，还需要一个辅助的 dp，其定义是第二个 dp 的定义中去掉贡献范围上界（即 $i$），转移画画图就能理解了。

用下 Fenwick Tree 啥的就能 $O(n \log_2 n)$ 了。

using modint = modint1000000007;
int n, a[200100], pos[200100], id[200100];
modint dp[200100], dp2[200100], dp3[200100], bit[200100], bit2[200100];
void cng(int x, modint w) {
    for (; x<=n; x+=x&-x) {
        bit[x] += w;
    }
}
modint qry(int x) {
    modint res = 0;
    for (; x; x-=x&-x) {
        res += bit[x];
    }
    return res;
}
void cng2(int x, modint w) {
    for (; x<=n; x+=x&-x) {
        bit2[x] += w;
    }
}
modint qry2(int x) {
    modint res = 0;
    for (; x; x-=x&-x) {
        res += bit2[x];
    }
    return res;
}
void solve() {
    cin >> n;
    bastr<int> dsc;
    for (int i=1; i<=n; ++i) {
        cin >> a[i];
        dsc += a[i];
    }
    sort(dsc.begin(), dsc.end());
    dsc.erase(unique(dsc.begin(), dsc.end()), dsc.end());
    for (int i=1; i<=n; ++i) {
        a[i] = lower_bound(dsc.begin(), dsc.end(), a[i])-dsc.begin()+1;
    }
    iota(id+1, id+n+1, 1);
    sort(id+1, id+n+1, [&](int x, int y) {
        return a[x] < a[y];
    });
    for (int i=1,now=n; i<=n; ++i) {
        while (now >= 1 && a[now] <= a[id[i]]) {
            now--;
        }
        pos[id[i]] = now;
    }
    for (int i=1; i<=n; ++i) {
        bit[i] = 0;
    }
    for (int i=1; i<=n; ++i) {
        dp[i] = qry(a[i]-1)+1;
        cng(a[i], dp[i]);
    }
    for (int i=1; i<=n; ++i) {
        bit[i] = bit2[i] = 0;
    }
    modint ans = 0;
    for (int i=n; i>=1; --i) {
        dp2[i] = qry(cs(dsc)-a[i])+1;
        cng(cs(dsc)-a[i]+1, dp2[i]);
        if (pos[i] > i) {
            dp3[i] = qry(cs(dsc)-a[pos[i]]+1)+qry2(a[pos[i]]-1)-qry2(a[i]);
            cng2(a[i], dp3[i]);
        }
        else {
            dp3[i] = 0;
        }
        ans += dp[i]*dp3[i];
    }
    cout << ans.val() << "\n";
}

link。

容易发现，如果将 $x$ 写作 $\displaystyle \prod_{i = 1}^k p_i^{\alpha_i}$ 的形式，$\displaystyle J(x) = 1+\sum p_i^{\alpha_i}+\sum\sum p_i^{\alpha_i}p_j^{\alpha_j}+\dots = \sum_{T \in 2^S} \sum_{i \in T} p_i^{\alpha_i}$，其中 $S = \{1, \dots, k\}$。写到这里可以发现 Joker function 是个 multiplicative function，所以 Joker function 又可以写作 $\displaystyle J(x) = \prod_{i = 1}^k J(p_i^{\alpha_i}) = \prod_{i = 1}^k \left(p_i^{\alpha_i}+1\right)$。

考虑 dp，设 $f[i][j]$ 表示用前 $i$ 个因数通过上述形式凑出 $j$ 的方案数，转移很平凡，具体看代码。这个 dp 可以用数据结构来存。这个 dp 复杂度的保证在于 $\displaystyle \max_{i \in [1, 10^{12}]} {\sigma_0(i)} = 6720$，这就叫人比较无语。至于判断一个数是否是 $p^k+1$ 的形式，可以根号分治来做，记阈值为 $T = 10^6$，对于 $\leqslant T$ 的元素，可以线性筛出所有质数，标记所有质数的次幂，数量级粗略是 $O(T\log T)$，完全跑不满；对于 $> T$ 的元素，因为 $(T+1)^2 > 10^{12}$，所以只需要判断是否为质数即可，Miller Rabin 或者其他 nb 的判素数方法即可。写不来 MR 所以直接蒯了个 mrsrz 的。

namespace Miller_Rabin{
    const int P[]={2,3,7,97,19260817};
    inline LL mul(LL a,LL b,const LL&md){
        LL tmp=a*b-(LL)((long double)a*b/md+.5)*md;
        return tmp+(tmp>>63&md);
    } 
    inline LL pow(LL a,LL b,const LL&md){
        LL ret=1;
        for(;b;b>>=1,a=mul(a,a,md))if(b&1)ret=mul(ret,a,md);
        return ret;
    }
    bool test(LL a,LL p){
        LL x=p-1;
        int d=0;
        while(!(x&1))++d,x>>=1;
        LL t=pow(a,x,p);
        while(d--){
            const LL ls=t;
            t=mul(t,t,p);
            if(t==1&&ls!=1&&ls!=p-1)return 0;
        }
        return t==1;
    }
    bool check(LL n){
        if(n<2)return 0;
        if(n==2||n==3||n==7||n==97||n==P[4])return 1;
        for(int i=0;i<5;++i)if(n%P[i]==0)return 0;
        for(int i=0;i<5;++i)
        if(!test(P[i]%n,n))return 0;
        return 1;
    }
}
using Miller_Rabin::check;
LL A;
bitset<1000100> tag;
int prm[1000100], cnt;
map<LL, int> mp; // a in it iff a = p^k
bastr<LL> offset[2000100];
void sieve(int n) {
    for (int i=2; i<=n; ++i) {
        if (!tag.test(i)) {
            prm[++cnt] = i;
        }
        for (int j=1; j<=cnt && i<=n/prm[j]; ++j) {
            tag.set(i*prm[j]);
            if (i%prm[j] == 0) {
                break;
            }
        }
    }
    for (int i=1; i<=cnt; ++i) {
        for (LL j=prm[i]; j<=1e12; j*=prm[i]) {
            mp[j] = i;
        }
    }
}
void executer() {
    cin >> A;
    map<LL, LL> dp[2];
    bastr<int> eff;
    for (LL i=1; i<=A/i; ++i) {
        if (A%i == 0) {
            if (mp.count(i-1)) {
                offset[mp[i-1]] += i;
                eff += mp[i-1];
            }
            if (i*i != A) {
                if (mp.count(A/i-1)) {
                    offset[mp[A/i-1]] += A/i;
                    eff += mp[A/i-1];
                }
                else if (check(A/i-1)) {
                    offset[++cnt] += A/i;
                    eff += cnt;
                }
            }
        }
    }
    sort(eff.begin(), eff.end());
    eff.erase(unique(eff.begin(), eff.end()), eff.end());
    dp[0][1] = 1;
    int cur = 1;
    for (auto u : eff) {
        dp[cur] = dp[cur^1];
        for (auto v : dp[cur^1]) {
            for (auto p : offset[u]) {
                if (A/p >= v.first && A%(v.first*p) == 0) {
                    dp[cur][v.first*p] += v.second;
                }
            }
        }
        cur ^= 1;
    }
    cout << dp[cs(eff)&1][A] << "\n";
}