已完成今日二维分块大学习。

· · 题解

::::info[题意]

参照没有“本质不同”限制的做法，莫队二次离线，考虑如何转移。以 r-1\rightarrow r 的情况为例。

记 i 的前驱、后继分别为 \text{pr}_i,\text{nx}_i。记 w([l,r],x) 为 [l,r] 内 >x 的颜色数。若 \text{pr}_{r}>l，则对于仅出现在 (\text{pr}_{r},r) 内且 >a_{r} 的颜色，均可以与 a_{r} 构成一种新的逆序对，一共有 w([l,r-1],a_r) - w([l,\text{pr}_{r}],a_r) 种，而注意到 \text{pr}_r 对 w([l,\text{pr}_r],a_r) 没有贡献，因此可以写成 w([l,r-1],a_r) - w([l,\text{pr}_{r}-1],a_{\text{pr}_r})。否则答案为 w([l,r-1],a_r)。

空间可以通过在 l 上挂一个区间做到线性。现在问题变成 \mathcal{O}(n\sqrt q) 次查询一个区间内大于某个值的颜色数。显然要求 \mathcal{O}(1)。

考虑从 n 到 1 扫描线，把 (i,a_i) 看成平面上的点，表示这种颜色 a_i 出现在下标 i 的位置。每种颜色在其最左边出现的位置统计贡献，加入一个点后删除其后继的贡献。我们发现贡献都被统一成了 w([l,r-1],a_r) 的形式。这个式子的答案是下标在 [l,r-1] 内且值大于 a_r 的点的个数。由于我们只加入了下标 \ge l 的点，因此第一个限制可以改写成下标小于 r。这样就变成了 2-\text{side} 矩形数点。为了方便我们可以通过翻转值域等方式转化成右上角矩形数点。并且此时我们将大于号均改成大于等于号，由于下标互不相同，一次查询只可能会多算 (r,a_r) 这个点。再记录一下每个点是否被加入来减去多余的贡献即可。

下文用“询问的点”指代以该点为左下角的右上角矩形的询问。

考虑加入一个点后会对哪些上述形式的询问产生贡献，显然是其左下矩形的范围。问题来到 \mathcal{O}(n) 次矩形加。

接下来进入二维分块。可以参考其他题解的插图。简单来说就是对两维分别以 n^{0.75} 和 n^{0.5} 为块长分块（没把常数写进去，注意要让大的块包含小的块），那么平面上会形成四种矩形块：

那么我们可以将矩形加的范围拆成左下角的一类块、一类块右侧的二类块、一类块上侧的三类块、一类块右上方的四类块各 \mathcal{O}(\sqrt n) 个，以及剩下的“L” 字形区域。考虑对于这五种区域的标记，使得对于任意一个有询问的点，其对应五种标记的和为询问的答案。

对四类整块打标记。至于剩下的“L”形区域比较棘手。考虑钦定 a 种重复出现的数靠右的更大，将序列 a 变成一个排列 b。不改变扫描线加入点的方式，仅将加入和询问的点从 (i,a_i) 改成 (i,b_i)，不会影响询问的答案。因为在 b 中相同的数左边更小，不会落到 >b_r 的区域中，而原本与 a_r 不同的数对询问的贡献不变。

这样一来，所有询问的点的横纵坐标互不相同。考虑加入一个点会对哪些询问产生贡献，由于“L”形区域的宽度为 \mathcal{O}(\sqrt n)，因此这个范围内的询问个数也只可能有 \mathcal{O}(\sqrt n) 种。枚举每种横纵坐标对应的询问即可。注意不要把转角区域重复贡献。

这样一来就可以做到 \mathcal{O}(\sqrt n) 矩形加 \mathcal{O}(1) 单点查。然后就做完了。

时间复杂度 \mathcal{O}(n\sqrt q)。空间复杂度 \mathcal{O}(q)。不卡常。

::::info[AC 代码]

#include <bits/stdc++.h>
#define eb emplace_back
#define me memset
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; c < 48 || c > 57; c = getchar()) if (c == 45) f = -1;
    for (; c > 47 && c < 58; c = getchar()) x = x * 10 + c - 48; x *= f;
}
template<class T> void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
template<class T> void print(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
}
using namespace std; typedef long long ll; const int N = 100005, M = 500005;
int n, q, a[N], b[N], c[N], pr[N], nx[N], B, ps[N], X[N], Y[N], rx[N], ry[N];
struct QR { int l, r, v, id; } Q[M]; ll ans[M], df[M]; vector<QR> g1[N], g2[N];
struct BLOCK {
    int B1, B2, s1[500][500], s2[500][500], s3[500][500], s4[500][500],
        s5[N], id1[N], id2[N], bl1[N], br1[N], bl2[N], br2[N], vs[N];
    void I() {
        B1 = pow(n, 0.75); B2 = sqrt(n);
        for (int i = 1; i <= n; ++i) id1[i] = (i - 1) / B1 + 1;
        for (int i = 1; i <= id1[n]; ++i) {
            bl1[i] = br1[i - 1] + 1; br1[i] = min(n, i * B1);
            for (int p = bl1[i], r; p <= br1[i]; p += B2) {
                r = min(br1[i], p + B2 - 1); ++id2[0];
                for (int j = p; j <= r; ++j) id2[j] = id2[0];
                bl2[id2[0]] = p; br2[id2[0]] = r;
            }
        }
    }
    void C() {
        me(s1, 0, sizeof s1); me(s2, 0, sizeof s2); me(s3, 0, sizeof s3);
        me(s4, 0, sizeof s4); me(s5, 0, sizeof s5); me(vs, 0, sizeof vs);
    }
    void U(int id, int v) {
        vs[id] += v; int x = X[id], y = Y[id];
        for (int i = 1; i < id1[x]; ++i)
            for (int j = 1; j < id1[y]; ++j) s1[i][j] += v;
        for (int i = id2[bl1[id1[x]]]; i < id2[x]; ++i)
            for (int j = 1; j < id1[y]; ++j) s2[i][j] += v;
        for (int j = id2[bl1[id1[y]]]; j < id2[y]; ++j)
            for (int i = 1; i < id1[x]; ++i) s3[i][j] += v;
        for (int i = id2[bl1[id1[x]]]; i < id2[x]; ++i)
            for (int j = id2[bl1[id1[y]]]; j < id2[y]; ++j) s4[i][j] += v;
        for (int i = bl2[id2[x]]; i <= x; ++i)
            if (Y[rx[i]] <= y) s5[rx[i]] += v;
        for (int j = bl2[id2[y]]; j <= y; ++j)
            if (X[ry[j]] < bl2[id2[x]]) s5[ry[j]] += v;
    }
    int Q(int i) {
        return s1[id1[X[i]]][id1[Y[i]]] + s2[id2[X[i]]][id1[Y[i]]] - vs[i] +
               s3[id1[X[i]]][id2[Y[i]]] + s4[id2[X[i]]][id2[Y[i]]] + s5[i];
    }
} ds;
void solve1() {
    for (int i = 1; i <= n; ++i) rx[i] = X[i] = ry[Y[i] = n - b[i] + 1] = i;
    for (int i = 1; i <= n; ++i) {
        if (pr[i]) ds.U(pr[i], -1); ds.U(i, 1);
        for (auto [l, r, v, id] : g1[i])
            for (int j = l, s = 0; j <= r; ++j) {
                s = ds.Q(j); if (nx[j] < i) s -= ds.Q(nx[j]); df[id] += v * s;
            }
    }
}
void solve2() {
    for (int i = 1; i <= n; ++i) rx[X[i] = n - i + 1] = ry[Y[i] = b[i]] = i;
    for (int i = n; i >= 1; --i) {
        if (nx[i] <= n) ds.U(nx[i], -1); ds.U(i, 1);
        for (auto [l, r, v, id] : g2[i])
            for (int j = l, s = 0; j <= r; ++j) {
                s = ds.Q(j); if (pr[j] > i) s -= ds.Q(pr[j]); df[id] += v * s;
            }
    }
}
signed main() {
    read(n); for (int i = 1; i <= n; ++i) read(a[i]), ++c[a[i]]; ds.I();
    for (int i = 1; i <= n; ++i)
        c[i] += c[i - 1], pr[i] = ps[a[i]], ps[a[i]] = i;
    read(q); B = n / sqrt(q); for (int i = 1; i <= n; ++i) ps[i] = n + 1;
    for (int i = n; i >= 1; --i)
        b[i] = c[a[i]]--, nx[i] = ps[a[i]], ps[a[i]] = i;  
    for (int i = 1; i <= q; ++i)
        read(Q[i].l), read(Q[i].r), Q[i].id = i, Q[i].v = Q[i].l / B;
    stable_sort(Q + 1, Q + q + 1, [&](QR x, QR y) {
        return x.v != y.v ? x.v < y.v : x.v & 1 ? x.r < y.r : x.r > y.r;
    });
    for (int i = 1, l = 1, r = 0; i <= q; ++i) {
        if (l > Q[i].l) g1[r].eb(QR{Q[i].l, l - 1, 1, i}), l = Q[i].l;
        if (r < Q[i].r) g2[l].eb(QR{r + 1, Q[i].r, 1, i}), r = Q[i].r;
        if (l < Q[i].l) g1[r].eb(QR{l, Q[i].l - 1, -1, i}), l = Q[i].l;
        if (r > Q[i].r) g2[l].eb(QR{Q[i].r + 1, r, -1, i}), r = Q[i].r;
    }
    solve1(); ds.C(); solve2();
    for (int i = 1; i <= q; ++i) ans[Q[i].id] = ans[Q[i - 1].id] + df[i];
    for (int i = 1; i <= q; ++i) print(ans[i]); return 0;
}

::::