ABC293G莫队维护区间元素数量组合计数

求区间出现符合要求的三元组数量：3个不同位置，元素的值相同。

#include <bits/stdc++.h>
#define N 200050
using namespace std;
int n, m, i, j, k, p, l, r, x, y, a[N], c[N];
long long s, ans[N];
struct AB{
    int x, y, i, p;
    bool operator < (const AB &A) const{
        if(p != A.p) return p < A.p;
        return y < A.y;
    }
} d[N];
void add(int x){
    if(++c[x] > 2) s += 3ll*(c[x]-1)*(c[x]-2)/6;
}//出现至少3个，增加差值：选3个，最高位变成3
void del(int x){
    if(--c[x] > 1) s -= 3ll*c[x]*(c[x]-1)/6;
}//减少前至少3个，减少差值：选3个除以6
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    p = sqrt(n);
    for(i=1; i<=m; i++){
        scanf("%d%d", &d[i].x, &d[i].y);
        d[i].i = i, d[i].p = d[i].x / p;
    }
    sort(d+1, d+m+1);
    l = r = c[a[1]] = 1, s = 0;
    for(i=1; i<=m; i++){
        x = d[i].x, y = d[i].y;
        while(r < y) add(a[++r]);
        while(l > x) add(a[--l]);
        while(l < x) del(a[l++]);
        while(r > y) del(a[r--]);
        ans[d[i].i] = s;
    }//先扩展区间，再缩小区间
    for(i=1; i<=m; i++){
        printf("%lld\n", ans[i]);
    }
    return 0;
}