剪贴板 qdcryg0a

```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 - '0'; ch = getchar(); } return s * f; } const int N = 1e6 + 10; const int M = 5e5 + 10; const int B = 1e5 + 10; typedef long long ll; int n, m, sq; int a[N], f[N], tot, mx; int bl, t[N], lb[B], rb[B]; int s1[B], ts1[N]; ll s2[B], ts2[N]; ll tr1[N], tr2[N], p[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; 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 < M; i += lbt(i)) { tr1[i]++, tr2[i] += k; } } ll qry(int x, int tp) { ll res = 0; for (int i = x; i; i -= lbt(i)) { res += (tp ? tr2[i] : tr1[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++) { f[i] = a[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 + n + 1, a[i]) - f; mx = max(mx, a[i]); } mx += 20; 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(mx); for (int i = 1; i <= mx; i++) { t[i] = (i - 1) / bl + 1; if (t[i] != t[i - 1]) { lb[t[i]] = i, rb[t[i - 1]] = i - 1; } } rb[t[mx]] = mx; for (int i = 1; i <= n; i++) { //cout << qry(a[i] - 1, 0) << ' '; p[i] = 1ll * (qry(a[i] - 1, 0) + 1) * f[a[i]] + (qry(M - 1, 1) - qry(a[i], 1)); upd(a[i], f[a[i]]); //cout << p[i] << ' '; } 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]]; res += p[k]; if (a[k] + 1 > rb[tk]) res -= s2[tk + 1]; else res -= s2[tk + 1] + ts2[a[k] + 1]; if (a[k] - 1 < lb[tk]) res -= 1ll * (s1[tk - 1]) * f[a[k]]; else res -= 1ll * (s1[tk - 1] + ts1[a[k] - 1]) * f[a[k]]; } aq[qr[i][j].id] += res * qr[i][j].tp; } int ti = t[a[i]]; for (int j = ti; j <= t[n]; j++) s1[j]++; for (int j = a[i]; t[j] == ti; j++) ts1[j]++; for (int j = ti; j; j--) s2[j] += f[a[i]]; for (int j = a[i]; t[j] == ti; j--) ts2[j] += f[a[i]]; } memset(s1, 0, sizeof s1); memset(s2, 0, sizeof s2); memset(ts1, 0, sizeof ts1); memset(ts2, 0, sizeof ts2); memset(tr1, 0, sizeof tr1); memset(tr2, 0, sizeof tr2); for (int i = n; i; i--) { p[i] = 1ll * (qry(a[i] - 1, 0) + 1) * f[a[i]] + (qry(M - 1, 1) - qry(a[i], 1)); upd(a[i], f[a[i]]); } 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]]; res += p[k]; if (a[k] + 1 > rb[tk]) res -= s2[tk + 1]; else res -= s2[tk + 1] + ts2[a[k] + 1]; if (a[k] - 1 < lb[tk]) res -= 1ll * (s1[tk - 1]) * f[a[k]]; else res -= 1ll * (s1[tk - 1] + ts1[a[k] - 1]) * f[a[k]]; } aq[ql[i][j].id] += res * ql[i][j].tp; } int ti = t[a[i]]; for (int j = ti; j <= t[n]; j++) s1[j]++; for (int j = a[i]; t[j] == ti; j++) ts1[j]++; for (int j = ti; j; j--) s2[j] += f[a[i]]; for (int j = a[i]; t[j] == ti; j--) ts2[j] += f[a[i]]; } for (int i = 1; i <= m; i++) { ans[q[i].id] = (cur += aq[i]); } for (int i = 1; i <= m; i++) { printf("%lld\n", ans[i]); } return 0; } ```