莫队

莫队

#define _CRT_SECURE_NO_WARNINGS
#define suro
#include <bits/stdc++.h>
using namespace std;
#ifndef suro
define endl '\n'
#endif
#define INF 0x7fffffff
#define inf 0x3f3f3f3f
    typedef long long LL;
#define int long long
const int N = 2e5 + 10;//M = 500;  // mod = 998244353;
​
int a[N];
array<int, 3> que[N];
int ans[N];
int cnt[N];
int n, m, tmp;
bool cmp(array<int, 3> a, array<int, 3> b) {
    if (a[0] / M != b[0] / M)
        return a[0] / M < b[0] / M;
    else {
        if ((a[0] / M) & 1)
            return a[1] < b[1];
        else
            return a[1] > b[1];
    }
}
auto add(int i) {
    tmp += cnt[a[i]] * (cnt[a[i]] - 1) / 2;
    cnt[a[i]]++;
}
auto del(int i) {
    cnt[a[i]]--;
    tmp -= cnt[a[i]] * (cnt[a[i]] - 1) / 2;
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        que[i] = {l, r, i};
    }
    sort(que + 1, que + m + 1, cmp);
    int l = 1, r = 0;
    tmp = 0;
    for (int i = 1; i <= m; i++) {
        while (r < que[i][1]) {
            add(++r);
        }
        while (l > que[i][0]) {
            add(--l);
        }
        while (r > que[i][1]) {
            del(r--);
        }
        while (l < que[i][0]) {
            del(l++);
        }
        ans[que[i][2]] = tmp;
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
​
    int T;
    // std::cin >> T;
    T = 1;
    while (T--) {
        solve();
    }
#ifdef suro
    system("pause");
#endif
    return 0;
}