剪贴板 e4z7z1g4 - 洛谷保存站

```cpp
#include <bits/stdc++.h>
using namespace std;

int rd() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 3) + (s << 1) + ch - 48;
        ch = getchar(); 
    }
    return s * f;
}

const int N = 2e5 + 10;
const int B = 410;
typedef long long ll;
int n, m, sq;
int a[N], f[N], tot;
int tr[N], p[N];
int bl, t[N], lb[B], rb[B];
int s[B], bs[N];
ll aq[N], cur, ans[N];

struct query1{
    int l, r, id;
    bool operator < (const query1 &o) const {
        if (l / sq != o.l / sq) return l < o.l;
        if (l / sq & 1) return r < o.r;
        else return r > o.r; 
    }
}q[N];
struct query2{
    int l, r, id, tp;
};
vector <query2> ql[N], qr[N];

int lbt(int x) { return x & (-x); }
void upd(int x, int k) {
    for (int i = x; i <= n + 1; i += lbt(i)) tr[i] += k;
}
int qry(int x) {
    if (!x) return 0;
    int res = 0;
    for (int i = x; i; i -= lbt(i)) res += tr[i];
    return res;
}

signed main() {
    //freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) {
        a[i] = f[i] = rd();
    }
    sort(f + 1, f + n + 1);
    tot = unique(f + 1, f + n + 1) - f - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(f + 1, f + tot + 1, a[i]) - f;
    }
    for (int i = 1; i <= m; i++) {
        int l = rd(), r = rd();
        q[i] = {l, r, i};
    }
    sq = sqrt(m);
    sort(q + 1, q + m + 1);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        if (r < q[i].r) qr[l].push_back({r + 1, q[i].r, i, 1});
        if (r > q[i].r) qr[l].push_back({q[i].r + 1, r, i, -1});
        r = q[i].r;
        if (l < q[i].l) ql[r].push_back({l, q[i].l - 1, i, -1});
        if (l > q[i].l) ql[r].push_back({q[i].l, l - 1, i, 1});
        l = q[i].l;
    }
    bl = sqrt(n);
    for (int i = 1; i <= n; i++) {
        t[i] = (i - 1) / bl + 1;
        if (t[i] != t[i - 1]) {
            lb[t[i]] = i, rb[t[i - 1]] = i - 1;
        }
    }
    lb[1] = 1, rb[t[n]] = n;
    for (int i = 1; i <= n; i++) {
        p[i] = i - 1 - qry(a[i]);
        upd(a[i], 1);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < qr[i].size(); j++) {
            ll res = 0;
            for (int k = qr[i][j].l; k <= qr[i][j].r; k++) {
                int tk = t[a[k]];
                if (a[k] + 1 > rb[tk]) res += p[k] - s[tk + 1];
                else res += p[k] - s[tk + 1] - bs[a[k] + 1];
            }
            res = 1ll * res * qr[i][j].tp;
            aq[qr[i][j].id] += res;
            //cout << res << ' ';
        }
        int ti = t[a[i]];
        for (int j = ti; j; j--) s[j]++;
        for (int j = a[i]; t[j] == ti; j--) bs[j]++;
    }
    memset(tr, 0, sizeof tr);
    for (int i = n; i; i--) {
        p[i] = qry(a[i] - 1);
        upd(a[i], 1);
    }
    memset(s, 0, sizeof s);
    memset(bs, 0, sizeof bs);
    for (int i = n; i; i--) {
        for (int j = 0; j < ql[i].size(); j++) {
            ll res = 0;
            for (int k = ql[i][j].l; k <= ql[i][j].r; k++) {
                int tk = t[a[k]];
                if (a[k] - 1 < lb[tk]) res += p[k] - s[tk - 1];
                else res += p[k] - s[tk - 1] - bs[a[k] - 1];
            }
            res = 1ll * res * ql[i][j].tp;
            aq[ql[i][j].id] += res;
            //cout << res << ' ';
        }
        int ti = t[a[i]];
        for (int j = ti; j <= t[n]; j++) s[j]++;
        for (int j = a[i]; t[j] == ti; j++) bs[j]++;
    }
    for (int i = 1; i <= m; i++) {
        cur += aq[i];
        ans[q[i].id] = cur;
    }
    for (int i = 1; i <= m; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
} 
```

正在渲染内容...