Submission #39624764

---

Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 5;
int n, m, a[maxn], bl[maxn];
ll ans[maxn], sum, cnt[maxn];
struct qry {
    int l, r, id;
} q[maxn];
void add(int x) {
    sum -= cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) / 6;
    cnt[x]++;
    sum += cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) / 6;
}
void del(int x) {
    sum -= cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) / 6;
    cnt[x]--;
    sum += cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) / 6;
}
int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
    cin >> n >> m;
    int B = sqrt(n);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        bl[i] = (i - 1) / B + 1;
    }
    for(int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        return bl[x.l] != bl[y.l] ? x.l < y.l : x.r < y.r;
    });
    int l = 1, r = 0;
    for(int i = 1; i <= m; i++) {
        while(r < q[i].r) {
            add(a[++r]);
        }
        while(l > q[i].l) {
            add(a[--l]);
        }
        while(r > q[i].r) {
            del(a[r--]);
        }
        while(l < q[i].l) {
            del(a[l++]);
        }
        ans[q[i].id] = sum;
    }
    for(int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
//    while(q--) {
//        int l, r;
//        cin >> l >> r;
//        ll ans = 0;
//        for(int i = 1; i <= 2e5; i++) {
//            ll x = 0;
//            for(int j = l; j <= r; j++) {
//                x += a[j] == i;
//            }
//            ans += (x * x * x - x * x * 3 + x * 2) / 6;
//        }
//        cout << ans << '\n';
//    }
	return 0;
}

Submission Info

Judge Result