WIKI

莫队

莫队算法是一种离线分块算法

如果能够$O(1)$的将 [l,r]的答案转移到[l,r+1][l,r-1][l+1,r][l-1,r] 就可以在 $O(n\sqrt n)$的时间内处理完所有的询问

莫队的精髓在于分块和转移

如果询问的大小和序列的长度同阶的话

那么时间上界就是$O(n\sqrt n)$

如果不是的话

块长取$\frac n {\sqrt m}$ 最优，此时时间复杂度上界为$O(n\sqrt m)$

关于莫队$O(1)$ 转移到临近区间的正确顺序

以上三种方式正确，其余顺序皆错误

国家集训队 小 Z 的袜子

code

// Luogu P1494 [国家集训队] 小 Z 的袜子
// https://www.luogu.com.cn/problem/P1494 2024-03-25 16:48:19

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
constexpr int N = 2E5 + 10;
int n, m, maxn, c[N], sum, ans1[N], ans2[N], cnt[N];
struct query {
  int l, r, id;
  bool operator<(const query &x) const {  // 重载<运算符
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];
void add(int i) {
  sum += cnt[i];
  cnt[i]++;
}
void del(int i) {
  cnt[i]--;
  sum -= cnt[i];
}
void solve() {
  cin >> n >> m;
  maxn = sqrtl(n);
  for (int i = 1; i <= n; i++) cin >> c[i];
  for (int i = 0; i < m; i++) {
    cin >> a[i].l >> a[i].r;
    a[i].id = i;
  }
  sort(a, a + m);
  for (int i = 0, l = 1, r = 0; i < m; i++) {
    if (a[i].l == a[i].r) {
      ans1[a[i].id] = 0;
      ans2[a[i].id] = 1;
    } else {
      while (l > a[i].l) add(c[--l]);
      while (r < a[i].r) add(c[++r]);
      while (l < a[i].l) del(c[l++]);
      while (r > a[i].r) del(c[r--]);
      ans1[a[i].id] = sum;
      ans2[a[i].id] = (r - l + 1) * (r - l) / 2;
    }
  }
  for (int i = 0; i < m; i++) {
    if (ans1[i] != 0) {
      int g = __gcd(ans1[i], ans2[i]);
      ans1[i] /= g, ans2[i] /= g;
    } else
      ans2[i] = 1;
    cout << ans1[i] << "/" << ans2[i] << "\n";
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}