Submission #74718807

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#if 1
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //用 pair<int, int> 来支持重复值, {x, i}
template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag,  tree_order_statistics_node_update>;
#endif

//beg========================================================================
#ifndef ONLINE_JUDGE
//#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << endl; }
#define dbg(...) do { string _s = #__VA_ARGS__; _s.erase(remove(_s.begin(), _s.end(), ' '), _s.end()); string _tmp; for (auto _x: splitArgs(_s)) _tmp += " " + _x; stringstream _ss(_tmp); istream_iterator<string> _it(_ss); err(_it, __VA_ARGS__); cout << endl; } while (0)
vector<string> splitArgs(const string& args) { vector<string> result; string current; int depth = 0; for (char c : args) { if (c == '(' || c == '<' || c == '[' || c == '{') { depth++; current += c; } else if (c == ')' || c == '>' || c == ']' || c == '}') { depth--; current += c; } else if (c == ',' && depth == 0) { if (!current.empty()) { size_t start = current.find_first_not_of(" \t"); size_t end = current.find_last_not_of(" \t"); if (start != string::npos) { result.push_back(current.substr(start, end - start + 1)); } } current.clear(); } else { current += c; } } if (!current.empty()) { size_t start = current.find_first_not_of(" \t"); size_t end = current.find_last_not_of(" \t"); if (start != string::npos) { result.push_back(current.substr(start, end - start + 1)); } } return result; }

template <typename A, typename B> string to_string(pair<A, B> p);
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(char b) { return string(1, b);}
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; }
template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; }
template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; }
template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ":" + to_string(p.second) + ")"; }
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + "," + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; }
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) { cout << *it << "=" << to_string(a) << ","; err(++it, args...); }

#else
#define dbg(...)
#endif
//end========================================================================

//beg========================================================================
#define endl "\n"
using i64 = int64_t;
using i32 = int;
using ll=long long;

const int MAXN = 2e5+10;
const i64 MOD = 1e9+7;
//const int MOD = 998244353;
const i64 INF = 0x3f3f3f3f;
const int64_t INF64 = 0x3f3f3f3f3f3f3f3fll;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

#define all(v) v.begin(), v.end()
template<class Ta, class Tb> bool chmax(Ta &a, Tb b) { if (a >= b) return false; a = b; return true; }
template<class Ta, class Tb> bool chmin(Ta &a, Tb b) { if (a <= b) return false; a = b; return true; }
template <typename T> typename T::value_type Max(T &a){ return *max_element(a.begin(), a.end()); }
template <typename T> auto Min(T &a){ return *min_element(a.begin(), a.end()); }
template <typename T> i64 Sum(T &a){ return accumulate(a.begin(), a.end(), i64(0));}
template <typename T> auto MaxV(T &m){ auto res = m.begin()->second; for (auto &[k, v]: m) chmax(res, v);return res;}
template <typename T> auto MaxK(T &m){ auto res = m.begin()->first; for (auto &[k, v]: m) chmax(res, k); return res;}
template <typename T> T SUM1(T k) { return  k * (k + 1) /2;};
template <typename T> T SUM2(T k) { return  k * (k + 1) * (k * 2 + 1) /6;}
template <typename T> T SUM3(T k) {  return (k * (k + 1) / 2) * ((k * (k + 1) / 2)); }


using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
//using f128 = __float128;


#pragma once
#include <cassert>
#include <cmath>
#include <utility>
#include <vector>

// Mo's algorithm
// - add_range(l, r) : Add [l, r) as query.
// - run(Add, Remove, Query) : run Mo's algorithm.
//   - Add(i) : Add i-th element ([i + 1, r) -> [i, r)).
//   - Remove(i) : Remove i-th element (Inverse of Add(i)).
//   - Query(q) : Solve q-th problem.
// Verified: https://codeforces.com/contest/375/submission/114665433
class MosAlgorithm {
    static const int INF = 1 << 30;
    int nmin, nmax;

public:
    std::vector<std::pair<int, int>> ranges;
    MosAlgorithm() : nmin(INF), nmax(-INF) {}

    void add_range(int l, int r) {
        // assert(l <= r);
        if (l>r) while (1);
        nmin = std::min(nmin, l);
        nmax = std::max(nmax, r);
        ranges.emplace_back(l, r);
    }
    template <typename F1, typename F2, typename F3, typename F4, typename F5>
    void run(F1 AddRight, F2 AddLeft, F3 RemoveRight, F4 RemoveLeft, F5 Query) {
        const int Q = ranges.size();
        if (!Q) return;
        const int nbbucket = std::max(1, std::min<int>(nmax - nmin, sqrt(Q)));
        const int szbucket = (nmax - nmin + nbbucket - 1) / nbbucket;
        std::vector<int> qs(Q);
        std::iota(qs.begin(), qs.end(), 0);
        std::sort(qs.begin(), qs.end(), [&](int q1, int q2) {
            int b1 = (ranges[q1].first - nmin) / szbucket, b2 = (ranges[q2].first - nmin) / szbucket;
            if (b1 != b2)
                return b1 < b2;
            else {
                return (b1 & 1) ? (ranges[q1].second > ranges[q2].second)
                                : (ranges[q1].second < ranges[q2].second);
            }
        });

        int l = ranges[qs[0]].first, r = l;
        for (auto q : qs) {
            while (r < ranges[q].second) AddRight(r++);
            while (l > ranges[q].first) AddLeft(--l);
            while (r > ranges[q].second) RemoveRight(--r);
            while (l < ranges[q].first) RemoveLeft(l++);
            assert(l == ranges[q].first and r == ranges[q].second);
            Query(q);
        }
    }
    template <typename F1, typename F3, typename F5> void run(F1 Add, F3 Remove, F5 Query) {
        run(Add, Add, Remove, Remove, Query);
    }
};



int TestNum;
signed main(){
  ios_base::sync_with_stdio(0),cin.tie(0), cout.tie(0);
  int N, Q; cin >> N >> Q;
  map<int, int> M;
  vector<pair<int, int>> A(N); for (auto &[x, v]: A) cin >> x >> v, M[v]=0;

  int id = 0; for (auto &[k, v]: M) v = id++;
  for (auto &[k, v]: A) v = M[v];

  sort(A.begin(), A.end());

  MosAlgorithm mo;
  vector<i64> ANS(Q);
  for (int i = 0; i < Q; i++) {
    int l, r; cin >> l >> r;
    l = lower_bound(A.begin(), A.end(), pair<int,int>{l, -INF})-A.begin();
    r = upper_bound(A.begin(), A.end(), pair<int,int>{r, INF})-A.begin();
    if (l>r) while (1);
    mo.add_range(l, r);
  }


  i64 cur = 0;
  i64 sz = 0;
  vector<int> CNT(id);
  mo.run(
    [&](int i) {
      if (i>=N) while (1);
      int x = A[i].second;
      cur += sz - CNT[x];
      CNT[x]++, sz++;
    }, 
    [&](int i) {
      if (i>=N) while (1);
      int x = A[i].second;
      cur -= sz - CNT[x];
      CNT[x]--, sz--;
    },
    [&](int i) {
      if (i>=Q) while (1);
      ANS[i] = cur+sz;
    }
  );
  for (auto x: ANS) cout << x << endl;



}

Submission Info

Compile Error

./Main.cpp:76:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
   76 | #pragma once
      |         ^~~~

Judge Result