Submission #41154823

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int B;
bool func(const pair<int, int>& lhs, const pair<int, int>& rhs){
  return ((lhs.first / B < rhs.first / B) ||
	  (lhs.first / B == rhs.first / B && lhs.second < rhs.second));
}

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  // Input
  ll N, Q;
  cin >> N >> Q;
  vector<int> a(N);
  for (auto &t : a) { cin >> t; t--; }

  vector<int> L(Q), R(Q);
  vector<pair<int, int>> qs;
  for (int i = 0; i < Q; i++){
    cin >> L[i] >> R[i];
    L[i]--; R[i]--;
    qs.emplace_back(L[i], R[i]);
  }

  // Solve: Mo のアルゴリズム
  B = max((int) sqrt(N*N/Q), 1);
  sort(qs.begin(), qs.end(), func);
  map<pair<int, int>, ll> mp;

  vector<ll> hist(200000);
  ll ans = 0; // 最後に6でわる
  
  auto[l, r] = *qs.begin();
  for (int i = l; i <= r; i++){
    hist[a[i]]++;
  }
  for (int i = 0; i < 200000; i++){
    if (hist[i] >= 3){
      ans += hist[i] * (hist[i] - 1) * (hist[i] - 2);
    }
  }

  for (auto p : qs){
    auto [nl, nr] = p;

    // 伸ばす方を先にやらないとおかしくなっちゃうかな
    // 左を伸ばす
    while (nl < l){
      l--;
      if (hist[a[l]] >= 3){
	ans -= hist[a[l]] * (hist[a[l]] - 1) * (hist[a[l]] - 2);
      }
      hist[a[l]]++;
      if (hist[a[l]] >= 3){
	ans += hist[a[l]] * (hist[a[l]] - 1) * (hist[a[l]] - 2);
      }
    }
    // 右を伸ばす
    while (nr > r){
      r++;
      if (hist[a[r]] >= 3){
	ans -= hist[a[r]] * (hist[a[r]] - 1) * (hist[a[r]] - 2);
      }
      hist[a[r]]++;
      if (hist[a[r]] >= 3){
	ans += hist[a[r]] * (hist[a[r]] - 1) * (hist[a[r]] - 2);
      }
    }
    
    // 左を縮める
    while (nl > l){
      if (hist[a[l]] >= 3){
	ans -= hist[a[l]] * (hist[a[l]] - 1) * (hist[a[l]] - 2);
      }
      hist[a[l]]--;
      if (hist[a[l]] >= 3){
	ans += hist[a[l]] * (hist[a[l]] - 1) * (hist[a[l]] - 2);
      }
      l++;
    }
    // 右を縮める
    while (nr < r){
      if (hist[a[r]] >= 3){
	ans -= hist[a[r]] * (hist[a[r]] - 1) * (hist[a[r]] - 2);
      }
      hist[a[r]]--;
      if (hist[a[r]] >= 3){
	ans += hist[a[r]] * (hist[a[r]] - 1) * (hist[a[r]] - 2);
      }
      r--;
    }

    l = nl;
    r = nr;
    mp[p] = ans / 6;
  }

  // Print
  for (int i = 0; i < Q; i++){
    ll ans = mp[make_pair(L[i], R[i])];
    cout << ans << "\n";
  }
  
  return 0;
}

Submission Info

Judge Result