algorithms-and-data-structures/Mo.cpp at main · os-moussao/algorithms-and-data-structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// CP Algorithms template
void remove(idx);  // TODO: remove value at idx from data structure
void add(idx);     // TODO: add value at idx from data structure
int get_answer();  // TODO: extract the current answer of the data structure

int block_size;

struct Query {
    int l, r, idx;
    bool operator<(Query other) const
    {
        return make_pair(l / block_size, r) <
               make_pair(other.l / block_size, other.r);
    }
};

vector<int> mo_s_algorithm(vector<Query> queries) {
    vector<int> answers(queries.size());
    sort(queries.begin(), queries.end());

    // TODO: initialize data structure

    int cur_l = 0;
    int cur_r = -1;
    // invariant: data structure will always reflect the range [cur_l, cur_r]
    for (Query q : queries) {
        while (cur_l > q.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < q.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < q.l) {
            remove(cur_l);
            cur_l++;
        }
        while (cur_r > q.r) {
            remove(cur_r);
            cur_r--;
        }
        answers[q.idx] = get_answer();
    }
    return answers;
}

////////////////////////////////////////////////////////
// CP Algorithms template tweaked as nested functions //
////////////////////////////////////////////////////////
int N = 1e5 + 10;
int block_size = sqrt(N);

struct Query {
    int l, r, idx;
    bool operator<(const Query &other) const
    {
        return make_tuple(l / block_size, r) <
              make_tuple(other.l / block_size, other.r);
    }
};

// my usual solve function
void solve() {
  int n, q; cin >> n >> q;
  block_size = sqrt(n);

  vector<Query> queries(q);
  vector<int> answers(q);

  // TODO: remove value at idx from data structure
  function<void(int)> remove = [&](int idx) {
  };

  // TODO: add value at idx from data structure
  function<void(int)> add = [&](int idx) {
  };

  // TODO: extract the current answer of the data structure
  function<int(void)> get_answer = [&]() {
    return 1;
  };


  function<void(void)> mos_algorithm = [&]() {
      sort(queries.begin(), queries.end());

      // TODO: initialize data structure

      int cur_l = 0;
      int cur_r = -1;
      // invariant: data structure will always reflect the range [cur_l, cur_r]
      for (Query q : queries) {
          while (cur_l > q.l) {
              cur_l--;
              add(cur_l);
          }
          while (cur_r < q.r) {
              cur_r++;
              add(cur_r);
          }
          while (cur_l < q.l) {
              remove(cur_l);
              cur_l++;
          }
          while (cur_r > q.r) {
              remove(cur_r);
              cur_r--;
          }
          answers[q.idx] = get_answer();
      }
  };

  mos_algorithm();
}