时间复杂度为：\(O(n * \sqrt{m})\), n为数组长度，m为查询次数。
板子代码
int n, m, k;/*
a[]记录原数组。
B为块长。
res记录当前区间的答案。
c[]为辅助数组，帮助O(1)转移区间答案。
ans[]记录查询答案。
*/
int a[N];
int B, res, c[N], ans[N];/*
记录查询，以左端点所在块的块号为第一关键字，升序排序；
以右端点为第二关键字，根据块号奇偶性优化排序：（块号为奇数，升序；块号为偶数，降序）。
*/
struct query{int l, r, id;bool operator <(const query& x) const{if(l / B != x.l / B) return l < x.l;if((l / B) & 1) return r < x.r;else return r > x.r;}
}q[N];void add(int x){/* 区间外扩1格对答案的改变 */
}void del(int x){/* 区间收缩1格对答案的改变 */
}void solve(){/* 输入 */cin >> n >> m >> k;for(int i = 1; i <= n; i ++) cin >> a[i];/* 记录查询，离线处理。 */for(int i = 1; i <= m; i ++){cin >> q[i].l >> q[i].r;q[i].id = i;}/* 块长最优为 n / sqrt(m)， 能保证无论数据n，m是什么，时间复杂度都是O(n * sqrt(m))。 */B = n / sqrt(m);/* 边界判断，防止B为0的特殊情况，这个非常重要。 */if(B == 0) B = 1;/* 排序 */sort(q + 1, q + 1 + m);/*处理询问。 */for(int i = 1, l = 0, r = 0; i <= m; i ++){/* 顺序很重要，要先扩张区间，然后再收缩区间，防止l > r。 */while(l > q[i].l) add(a[--l]);while(r < q[i].r) add(a[++r]);while(l < q[i].l) del(a[l++]);while(r > q[i].r) del(a[r--]);ans[q[i].id] = res - 1;}/* 输出 */for(int i = 1; i <= m; i ++) cout << ans[i] << endl;
}
示例题目
示例代码
#include <bits/stdc++.h>
#define int long long
using namespace std;#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define PII pair<int, int>
#define lowbit(x) ((x) & (-(x)))
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << (x) << "\n";
#define vdebug(a) cout << #a << " = "; for(auto& x: a) cout << x << " "; cout << "\n";
#define vlrdebug(a, l, r) cout << #a << " = "; for(auto i = l; i <= r; i ++) cout << a[i] << " "; cout << "\n";
#define lc ((p) << 1)
#define rc ((p) << 1 | 1)const int N = 1e6 + 10, M = 1010;
const int mod = 1e9 + 7, MOD = 998244353;
const int INF = 0x3f3f3f3f;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};int n, m, k;
int a[N];
int B, res, c[N], ans[N];struct query{int l, r, id;bool operator <(const query& x) const{if(l / B != x.l / B) return l < x.l;if((l / B) & 1) return r < x.r;else return r > x.r;}
}q[N];void add(int x){res += 2 * c[x] + 1;c[x] ++;
}void del(int x){res -= 2 * c[x] - 1;c[x] --;
}void solve(){cin >> n >> m >> k;for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1; i <= m; i ++){cin >> q[i].l >> q[i].r;q[i].id = i;}B = n / sqrt(m);if(B == 0) B = 1;sort(q + 1, q + 1 + m);for(int i = 1, l = 0, r = 0; i <= m; i ++){while(l > q[i].l) add(a[--l]);while(r < q[i].r) add(a[++r]);while(l < q[i].l) del(a[l++]);while(r > q[i].r) del(a[r--]);ans[q[i].id] = res - 1;}for(int i = 1; i <= m; i ++) cout << ans[i] << endl;
}signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;// cin >> _;while(_ --) solve();return 0;
}
