题解 ABC293G【Triple Index】

莫队板子。

类似于 小 B 的询问，在移动指针过程中，维护每个数出现次数 \(cnt_i\)，同时维护 \(\sum\binom{cnt_i}{3}\) 即可。

取序列分块块长 \(B=\frac{n}{\sqrt{m}}\)，有最优复杂度 \(\mathcal O(n\sqrt{m})\)。

在 ABC G 看到过好几次莫队板子，ABC 怎么这么喜欢莫队板子。

// Problem: G - Triple Index
// Contest: AtCoder - AtCoder Beginner Contest 293
// URL: https://atcoder.jp/contests/abc293/tasks/abc293_g
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
	uniform_int_distribution<ll> dist(L, R);
	return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const ll N = 2e5+5;

ll n, m, a[N], L[N], R[N], pos[N], sz, tot, buc[N], now, ans[N];

struct Query {
	ll l, r, id;
	Query(ll a=0, ll b=0, ll c=0) : l(a), r(b), id(c) {}
	friend bool operator<(const Query& a, const Query& b) {
		if(pos[a.l] != pos[b.l]) return a.l < b.l;
		return (pos[a.l] & 1) ? (a.r < b.r) : (a.r > b.r);
	}
}q[N];

void initBlock() {
	sz = n / sqrt(m);
	chkmax(sz, 1LL);
	chkmin(sz, n);
	while(++tot) {
		L[tot] = R[tot-1] + 1;
		R[tot] = min(sz*tot, n);
		rep(i, L[tot], R[tot]) pos[i] = tot;
		if(R[tot] == n) break;
	}
}

void ins(ll x) {
	now -= buc[x] * (buc[x] - 1) / 2 * (buc[x] - 2) / 3;
	++buc[x];
	now += buc[x] * (buc[x] - 1) / 2 * (buc[x] - 2) / 3;
}

void del(ll x) {
	now -= buc[x] * (buc[x] - 1) / 2 * (buc[x] - 2) / 3;
	--buc[x];
	now += buc[x] * (buc[x] - 1) / 2 * (buc[x] - 2) / 3;
}

int main() {
	scanf("%lld%lld", &n, &m);
	rep(i, 1, n) scanf("%lld", &a[i]);
	initBlock();
	rep(i, 1, m) scanf("%lld%lld", &q[i].l, &q[i].r), q[i].id = i;
	sort(q+1, q+1+m);
	ll l = 1, r = 0;
	rep(i, 1, m) {
		while(l > q[i].l) ins(a[--l]);
		while(r < q[i].r) ins(a[++r]);
		while(l < q[i].l) del(a[l++]);
		while(r > q[i].r) del(a[r--]);
		ans[q[i].id] = now;
	}
	rep(i, 1, m) printf("%lld\n", ans[i]);
	return 0;
}