莫队

普通莫队

P2709 【模板】莫队 / 小 B 的询问

我们开一个桶 $c_i$ 表示区间内某个颜色 $i$ 的出现次数，直接用莫队维护即可。

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e6 + 5;
6
long long n, m, l, r, k;
7
long long a[N], pos[N], cnt[N], now, ans[N], L[N], R[N];
8

9
struct Query {
10
  int l, r, id;
11
}Q[N];
12

13
bool cmp(Query a, Query b) {
14
  if(pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
15
  else if(pos[a.r] & 1) return pos[a.r] < pos[b.r];
16
  else return pos[a.r] > pos[b.r];
17
}
18

19
void add(int x) {
20
  int val = cnt[a[x]];
21
  cnt[a[x]] ++;
22
  now = now - val * val + cnt[a[x]] * cnt[a[x]];
23
}
24

25
void del(int x) {
26
  int val = cnt[a[x]];
27
  cnt[a[x]] --;
28
  now = now - val * val + cnt[a[x]] * cnt[a[x]];
29
}
30

31
int main() {
32
  cin >> n >> m >> k;
33

34
  int block = sqrt(n);
35
  int num = ceil((double) n / (double) block);
36

37
  for(int i = 1; i <= num; i ++) {
38
    L[i] = (i - 1) * block + 1;
39
    R[i] = i * block;
40

41
    for(int j = L[i]; j <= R[i]; j ++) {
42
      pos[j] = i;
43
    }
44
  }
45

46
  for(int i = 1; i <= n; i ++) {
47
    cin >> a[i];
48
  }
49

50
  for(int i = 1; i <= m; i ++) {
51
    cin >> Q[i].l >> Q[i].r;
52
    Q[i].id = i;
53
  }
54

55
  sort(Q + 1, Q + m + 1, cmp);
56

57
  int left = 1, right = 0;
58

59
  for(int i = 1; i <= m; i ++) {
60
    int l = Q[i].l, r = Q[i].r, id = Q[i].id;
61

62
    while(left < l) del(left ++);
63
    while(left > l) add(-- left);
64
    while(right < r) add(++ right);
65
    while(right > r) del(right --);
66

67
    ans[id] = now;
68
  }
69

70
  for(int i = 1; i <= m; i ++) cout << ans[i] << endl;
71

72
  return 0;
73
}

P1494 【国家集训队】小 Z 的袜子

我们考虑用莫队维护区间内抽到相同颜色的出现概率，用桶直接维护每种颜色的出现次数即可，注意输出格式要求输出最简分数。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 5e4 + 5;
6
long long cnt[N], answer = 0;
7
int pos[N], a[N], n, m;
8
pair<long long, long long> result[N];
9

10
long long gcd(long long a, long long b) {
11
  if (b == 0) return a;
12
  return gcd(b, a % b);
13
}
14

15
struct Query {
16
  int l, r, id;
17

18
  bool operator < (const Query & rhv) const {
19
    if (pos[l] == pos[rhv.l]) return r < rhv.r;
20
    return l < rhv.l;
21
  }
22
} query[N];
23

24
void update(int pos, int add) {
25
  answer -= cnt[a[pos]] * cnt[a[pos]];
26
  cnt[a[pos]] += add;
27
  answer += cnt[a[pos]] * cnt[a[pos]];
28
}
29

30
int main() {
31
  ios::sync_with_stdio(false);
32
  cin.tie(nullptr);
33
  cout.tie(nullptr);
34

35
  cin >> n >> m;
36

37
  int block = sqrt(n);
38

39
  for (int i = 1; i <= n; i++) {
40
    cin >> a[i];
41
    pos[i] = (i - 1) / block + 1;
42
  }
43

44
  for (int i = 1; i <= m; i++) {
45
    cin >> query[i].l >> query[i].r;
46
    query[i].id = i;
47
  }
48

49
  sort(query + 1, query + m + 1);
50

51
  int L = 1, R = 0;
52

53
  for (int i = 1; i <= m; i++) {
54
    while (L < query[i].l) update(L, -1), L++;
55
    while (L > query[i].l) L--, update(L, 1);
56
    while (R < query[i].r) R++, update(R, 1);
57
    while (R > query[i].r) update(R, -1), R--;
58

59
    if (query[i].l == query[i].r) {
60
      result[query[i].id] = make_pair(0, 1);
61
      continue;
62
    }
63

64
    long long a = answer - (query[i].r - query[i].l + 1);
65
    long long b = (long long) (query[i].r - query[i].l + 1) * (query[i].r - query[i].l);
66
    long long gcd_value = gcd(a, b);
67

68
    result[query[i].id] = make_pair(a / gcd_value, b / gcd_value);
69
  }
70

71
  for (int i = 1; i <= m; i ++) {
72
    cout << result[i].first << "/" << result[i].second << '\n';
73
  }
74

75
  return 0;
76
}

P4462 【CQOI2018】异或序列

我们定义 $pre_i = \oplus^{i}_{j=1} a_i$ ，询问我们有多少组 $(x, y)$ 满足 $a_x \oplus a_{x+1} \oplus a_{x+2} \oplus \dots \oplus a_{y-2} \oplus a_{y-1} \oplus a_y = k$ 即为 $pre_y \oplus pre_{x-1} = k$ ，开桶统计即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
using i32 = int;
6
using i64 = long long;
7
using i128 = __int128;
8
using ui64 = unsigned long long;
9
using f32 = float;
10
using f64 = double;
11

12
constexpr i32 N = 1e5 + 5;
13

14
i32 n, m, a[N], k;
15
i32 l[N], r[N], pos[N], block, num;
16
i64 ans[N], sum[N], cur;
17
vector<tuple<i32, i32, i32>> queries;
18

19
inline void Add(i32 i) {
20
  cur += sum[a[i] ^ k];
21
  sum[a[i]]++;
22
}
23

24
inline void Del(i32 i) {
25
  sum[a[i]]--;
26
  cur -= sum[a[i] ^ k];
27
}
28

29
i32 main() {
30
  ios::sync_with_stdio(false);
31
  cin.tie(nullptr);
32
  cout.tie(nullptr);
33

34
  cin >> n >> m >> k;
35

36
  for (i32 i = 1; i <= n; i++) {
37
    cin >> a[i];
38
    a[i] ^= a[i - 1];
39
  }
40

41
  queries.resize(m);
42
  for (i32 i = 0; i < m; i++) {
43
    cin >> get<0>(queries[i]) >> get<1>(queries[i]);
44
    get<2>(queries[i]) = i;
45
  }
46

47
  block = sqrt(n);
48
  num = (n + block - 1) / block;
49

50
  for (i32 i = 1; i <= num; i++) {
51
    l[i] = (i - 1) * block + 1;
52
    r[i] = i * block;
53
    for (i32 j = l[i]; j <= r[i]; j++) {
54
      pos[j] = i;
55
    }
56
  }
57

58
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
59
    if (pos[get<0>(a)] != pos[get<0>(b)])
60
      return pos[get<0>(a)] < pos[get<0>(b)];
61
    else if (pos[get<0>(a)] & 1)
62
      return get<1>(a) > get<1>(b);
63
    else
64
      return get<1>(a) < get<1>(b);
65
  });
66

67
  i32 L = 0, R = 0;
68
  sum[0] = 1;
69
  for (i32 i = 0; i < (i32) queries.size(); i++) {
70
    while (L < get<0>(queries[i]) - 1)
71
      Del(L++);
72
    while (L > get<0>(queries[i]) - 1)
73
      Add(--L);
74
    while (R < get<1>(queries[i]))
75
      Add(++R);
76
    while (R > get<1>(queries[i]))
77
      Del(R--);
78

79
    ans[get<2>(queries[i])] = cur;
80
  }
81

82
  for (i32 i = 0; i < m; i++) {
83
    cout << ans[i] << "\n";
84
  }
85

86
  return 0;
87
}

P3709 大爷的字符串题

设 $c_i$ 表示当前区间内 $i$ 这个数字的出现次数，不难发现，rp 的最终结果只和区间内最大的 $c_i$ 有关，莫队维护即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
using i32 = int;
6
using i64 = long long;
7
using f32 = float;
8
using f64 = double;
9

10
constexpr i32 N = 2e5 + 5;
11

12
i32 n, m, a[N], ans[N];
13
i32 l[N], r[N], pos[N], block, num;
14
i32 tot[N], refer[N], cur = 0;
15
vector<tuple<i32, i32, i32>> queries;
16
vector<int> vars;
17

18
inline void Add(i32 i) {
19
  refer[tot[a[i]]]--;
20
  tot[a[i]]++;
21
  refer[tot[a[i]]]++;
22
  cur = max(cur, tot[a[i]]);
23
}
24

25
inline void Del(i32 i) {
26
  refer[tot[a[i]]]--;
27
  if (cur == tot[a[i]] && refer[tot[a[i]]] == 0)
28
    cur--;
29
  tot[a[i]]--;
30
  refer[tot[a[i]]]++;
31
}
32

33
int main() {
34
  ios::sync_with_stdio(false);
35
  cin.tie(nullptr);
36
  cout.tie(nullptr);
37

38
  cin >> n >> m;
39

40
  for (i32 i = 1; i <= n; i++) {
41
    cin >> a[i];
42
    vars.push_back(a[i]);
43
  }
44

45
  sort(vars.begin(), vars.end());
46
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
47

48
  for (i32 i = 1; i <= n; i++) {
49
    a[i] = (i32) (lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1);
50
  }
51

52
  queries.resize(m);
53
  for (i32 i = 0; i < m; i++) {
54
    cin >> get<0>(queries[i]) >> get<1>(queries[i]);
55
    get<2>(queries[i]) = i;
56
  }
57

58
  block = sqrt(n);
59
  num = (n + block - 1) / block;
60

61
  for (i32 i = 1; i <= num; i++) {
62
    l[i] = (i - 1) * block + 1;
63
    r[i] = min(n, i * block);
64

65
    for (int j = l[i]; j <= r[i]; j++)
66
      pos[j] = i;
67
  }
68

69
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
70
    if (pos[get<0>(a)] != pos[get<0>(b)])
71
      return pos[get<0>(a)] < pos[get<0>(b)];
72
    if (pos[get<0>(a)] & 1)
73
      return get<1>(a) < get<1>(b);
74
    return get<1>(a) > get<1>(b);
75
  });
76

77
  i32 L = 0, R = 0;
78
  refer[0] = n;
79
  for (i32 i = 0; i < (i32) queries.size(); i++) {
80
    while (L < get<0>(queries[i]))
81
      Del(L++);
82
    while (L > get<0>(queries[i]))
83
      Add(--L);
84
    while (R < get<1>(queries[i]))
85
      Add(++R);
86
    while (R > get<1>(queries[i]))
87
      Del(R--);
88

89
    ans[get<2>(queries[i])] = -cur;
90
  }
91

92
  for (i32 i = 0; i < m; i++) {
93
    cout << ans[i] << "\n";
94
  }
95

96
  return 0;
97
}

带修莫队

带修莫队就是在普通莫队的基础上加上了一个时间维度，我们只要记录查询的时间，并将之前的操作全部应用即可，注意这时候块长取 $n^{\frac{3}{2}}$ 可以取到最优复杂度。

P1903 【模板】带修莫队 / 【国家集训队】数颜色 / 维护队列

我们维护一个时间维度上的修改操作即可。

1
#include <bits/stdc++.h>
2

3
#ifdef LOCAL
4
#include <algo/debug.h>
5
#else
6
#define debug(...) 42
7
#endif
8

9
using namespace std;
10

11
constexpr int N = 6e5 + 5;
12

13
int n, m, c[N], cpy[N], lst[N], answer[N];
14
int cnt_queries = 0;
15
set<int> positions[N];
16
vector<int> vars;
17

18
int cnt_op = 0;
19
struct Op {
20
  int type, x, r, y, val, index;
21
} ops[N];
22

23
struct Fenwick {
24
  int tr[N], Limit = 0;
25
  Fenwick() = default;
26
  Fenwick(int n) : Limit(n) {
27
    fill(tr, tr + Limit + 1, 0);
28
  }
29
  static int Lowbit(int x) {
30
    return x & (-x);
31
  }
32
  void Modify(int pos, int var) {
33
    for (int i = pos; i <= Limit; i += Lowbit(i))
34
      tr[i] += var;
35
  }
36
  int Query(int pos) {
37
    int retval = 0;
38
    for (int i = pos; i; i -= Lowbit(i))
39
      retval += tr[i];
40
    return retval;
41
  }
42
} tr;
43

44
int GetColor(int col) {
45
  return (int) (lower_bound(vars.begin(), vars.end(), col) - vars.begin() + 1);
46
}
47

48
void CDQ(int l, int r) {
49
  if (l == r) return;
50

51
  int mid = (l + r) >> 1;
52
  CDQ(l, mid);
53
  CDQ(mid + 1, r);
54

55
  sort(ops + l, ops + mid + 1, [&] (auto a, auto b) {
56
    if (a.y != b.y) return a.y < b.y;
57
    return a.x < b.x;
58
  });
59
  sort(ops + mid + 1, ops + r + 1, [&] (auto a, auto b) {
60
    if (a.y != b.y) return a.y < b.y;
61
    return a.x < b.x;
62
  });
63

64
  int pl = l, pr = mid + 1;
65
  while (pr <= r) {
66
    while (pl <= mid && ops[pl].y < ops[pr].y) {
67
      if (ops[pl].type == 1) {
68
        tr.Modify(ops[pl].x, ops[pl].val);
69
      }
70
      pl++;
71
    }
72

73
    if (ops[pr].type == 2) {
74
      answer[ops[pr].index] += tr.Query(ops[pr].r) - tr.Query(ops[pr].x - 1);
75
    }
76
    pr++;
77
  }
78

79
  for (int i = l; i < pl; i++) {
80
    if (ops[i].type == 1) {
81
      tr.Modify(ops[i].x, -ops[i].val);
82
    }
83
  }
84
}
85

86
int main() {
87
  ios::sync_with_stdio(false);
88
  cin.tie(nullptr);
89
  cout.tie(nullptr);
90

91
  cin >> n >> m;
92

93
  for (int i = 1; i <= n; i++) {
94
    cin >> c[i];
95
    cpy[i] = c[i];
96
    vars.push_back(c[i]);
97
  }
98

99
  vector<tuple<char, int, int>> raw(m + 1);
100
  for (int i = 1; i <= m; i++) {
101
    auto&& [x, y, z] = raw[i];
102
    cin >> x >> y >> z;
103

104
    if (x == 'R') {
105
      vars.push_back(z);
106
    }
107
  }
108

109
  sort(vars.begin(), vars.end());
110
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
111

112
  for (int i = 1; i <= n; i++) {
113
    positions[GetColor(c[i])].insert(i);
114
  }
115

116
  for (int i = 1; i <= n; i++) {
117
    int cur_col = GetColor(c[i]);
118
    ops[++cnt_op] = Op{1, i, 0, lst[cur_col], 1, 0};
119
    lst[cur_col] = i;
120
  }
121

122
  for (int i = 1; i <= m; i++) {
123
    if (get<0>(raw[i]) == 'Q') {
124
      auto&& [op, l, r] = raw[i];
125

126
      ops[++cnt_op] = Op{2, l, r, l, 0, ++cnt_queries};
127
    } else if (get<0>(raw[i]) == 'R') {
128
      auto&& [op, pos, nxt_col] = raw[i];
129
      int cur_col = cpy[pos];
130

131
      auto Current = positions[GetColor(cur_col)].find(pos);
132
      int pre = 0, suc = 0;
133
      if (Current != positions[GetColor(cur_col)].begin()) {
134
        pre = *prev(Current);
135
      }
136
      if (next(Current) != positions[GetColor(cur_col)].end()) {
137
        suc = *next(Current);
138
      }
139

140
      ops[++cnt_op] = Op{1, pos, 0, pre, -1, 0};
141

142
      if (suc != 0) {
143
        ops[++cnt_op] = Op{1, suc, 0, pos,  -1, 0};
144
        ops[++cnt_op] = Op{1, suc, 0, pre, 1, 0};
145
      }
146
      positions[GetColor(cur_col)].erase(Current);
147

148
      Current = positions[GetColor(nxt_col)].lower_bound(pos);
149
      pre = 0, suc = 0;
150
      if (Current != positions[GetColor(nxt_col)].begin()) {
151
        pre = *prev(Current);
152
      }
153
      if (Current != positions[GetColor(nxt_col)].end()) {
154
        suc = *Current;
155
      }
156

157
      ops[++cnt_op] = Op{1, pos, 0, pre, 1, 0};
158

159
      if (suc != 0) {
160
        ops[++cnt_op] = Op{1, suc, 0, pre, -1, 0};
161
        ops[++cnt_op] = Op{1, suc, 0, pos, 1, 0};
162
      }
163
      positions[GetColor(nxt_col)].insert(pos);
164

165
      cpy[pos] = nxt_col;
166
    }
167
  }
168

169
  tr = Fenwick(n);
170
  CDQ(1, cnt_op);
171

172
  for (int i = 1; i <= cnt_queries; i++) {
173
    cout << answer[i] << "\n";
174
  }
175

176
  return 0;
177
}

Problem - 940F - Codeforces

直接开桶暴力维护mex即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
using i32 = int;
6
using i64 = long long;
7
using f32 = float;
8
using f64 = double;
9

10
constexpr i32 N = 5e5 + 5;
11

12
i32 n, q, a[N], ans[N];
13
i32 l[N], r[N], pos[N], block, num;
14
vector<tuple<i32, i32, i32>> query, modify;
15
vector<i32> vars;
16
i32 cnt[N], tot[N];
17

18
inline void Add(i32 val) {
19
  if (cnt[val] > 0) tot[cnt[val]]--;
20
  cnt[val]++;
21
  if (cnt[val] > 0) tot[cnt[val]]++;
22
}
23

24
inline void Del(i32 val) {
25
  if (cnt[val] > 0) tot[cnt[val]]--;
26
  cnt[val]--;
27
  if (cnt[val] > 0) tot[cnt[val]]++;
28
}
29

30
inline void Upd(i32 idx_q, i32 idx_m) {
31
  if (get<0>(modify[idx_m]) >= get<0>(query[idx_q]) && get<0>(modify[idx_m]) <= get<1>(query[idx_q])) {
32
    Del(a[get<0>(modify[idx_m])]);
33
    Add(get<1>(modify[idx_m]));
34
  }
35
  swap(get<1>(modify[idx_m]), a[get<0>(modify[idx_m])]);
36
}
37

38
int main() {
39
  ios::sync_with_stdio(false);
40
  cin.tie(nullptr);
41
  cout.tie(nullptr);
42

43
  cin >> n >> q;
44

45
  for (i32 i = 1; i <= n; i++) {
46
    cin >> a[i];
47
    vars.push_back(a[i]);
48
  }
49

50
  for (i32 i = 1; i <= q; i++) {
51
    i32 op, l, r;
52
    cin >> op >> l >> r;
53

54
    if (op == 1) {
55
      query.push_back(make_tuple(l, r, i));
56
    } else {
57
      modify.push_back(make_tuple(l, r, i));
58
      vars.push_back(r);
59
    }
60
  }
61

62
  sort(vars.begin(), vars.end());
63
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
64

65
  for (i32 i = 1; i <= n; i++) {
66
    a[i] = lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1;
67
  }
68
  for (i32 i = 0; i < (i32) modify.size(); i++) {
69
    get<1>(modify[i]) = lower_bound(vars.begin(), vars.end(), get<1>(modify[i])) - vars.begin() + 1;
70
  }
71

72
  block = pow(n, 2.0 / 3);
73
  num = (n + block - 1) / block;
74

75
  for (i32 i = 1; i <= num; i++) {
76
    l[i] = (i - 1) * block + 1;
77
    r[i] = min(i * block, n);
78

79
    for (i32 j = l[i]; j <= r[i]; j++)
80
      pos[j] = i;
81
  }
82

83
  sort(query.begin(), query.end(), [&] (auto a, auto b) {
84
    if (pos[get<0>(a)] != pos[get<0>(b)])
85
      return pos[get<0>(a)] < pos[get<0>(b)];
86
    if (pos[get<1>(a)] != pos[get<1>(b)])
87
      return pos[get<1>(a)] < pos[get<1>(b)];
88
    return get<2>(a) < get<2>(b);
89
  });
90
  sort(modify.begin(), modify.end(), [&] (auto a, auto b) {
91
    return get<2>(a) < get<2>(b);
92
  });
93

94
  i32 L = 0, R = 0, idx = -1;
95
  for (i32 i = 0; i < (i32) query.size(); i++) {
96
    while (L < get<0>(query[i]))
97
      Del(a[L++]);
98
    while (L > get<0>(query[i]))
99
      Add(a[--L]);
100
    while (R < get<1>(query[i]))
101
      Add(a[++R]);
102
    while (R > get<1>(query[i]))
103
      Del(a[R--]);
104
    while (idx + 1 < (i32) modify.size() && get<2>(modify[idx + 1]) < get<2>(query[i]))
105
      Upd(i, ++idx);
106
    while (idx >= 0 && get<2>(modify[idx]) > get<2>(query[i]))
107
      Upd(i, idx--);
108

109
    ans[get<2>(query[i])] = 1;
110
    while (tot[ans[get<2>(query[i])]] > 0) ans[get<2>(query[i])]++;
111
  }
112

113
  for (int i = 1; i <= q; i++) {
114
    if (ans[i]) cout << ans[i] << "\n";
115
  }
116

117
  return 0;
118
}

回滚莫队

对于一些加入元素很难，但是删除元素很简单的题目，我们可以考虑只维护插入的元素，然后处理完当前询问后直接继承之前的状态即可，这样可以保证复杂度为 $\Theta(\sqrt{n})$ 。反之亦然。

P5906 【模板】回滚莫队&不删除莫队

板子题。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 4e5 + 5;
6

7
int n, m, a[N];
8
int l[N], r[N], pos[N], block, num;
9
int max_pos[N], min_pos[N], _max_pos[N];
10
int max_dist, ans[N];
11
vector<tuple<int, int, int>> queries;
12
vector<int> vars;
13

14
inline int BruteQuery(int l, int r) {
15
  static int mx[N], mn[N];
16
  int res = 0;
17
  for (int i = l; i <= r; i++) {
18
    if (!mn[a[i]]) mn[a[i]] = i;
19
    mx[a[i]] = i;
20
    res = max(res, mx[a[i]] - mn[a[i]]);
21
  }
22

23
  for (int i = l; i <= r; i++)
24
    mx[a[i]] = mn[a[i]] = 0;
25

26
  return res;
27
}
28

29
int main() {
30
  ios::sync_with_stdio(false);
31
  cin.tie(nullptr);
32
  cout.tie(nullptr);
33

34
  cin >> n;
35

36
  for (int i = 1; i <= n; i++) {
37
    cin >> a[i];
38
    vars.push_back(a[i]);
39
  }
40

41
  sort(vars.begin(), vars.end());
42
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
43

44
  for (int i = 1; i <= n; i++) {
45
    a[i] = lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1;
46
  }
47

48
  cin >> m;
49
  for (int i = 1; i <= m; i++) {
50
    int left, right;
51
    cin >> left >> right;
52
    queries.push_back(make_tuple(left, right, i));
53
  }
54

55
  block = sqrt(n);
56
  num = (n + block - 1) / block;
57

58
  for (int i = 1; i <= num; i++) {
59
    l[i] = (i - 1) * block + 1;
60
    r[i] = min(i * block, n);
61

62
    for (int j = l[i]; j <= r[i]; j++)
63
      pos[j] = i;
64
  }
65

66
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
67
    if (pos[get<0>(a)] != pos[get<0>(b)])
68
      return pos[get<0>(a)] < pos[get<0>(b)];
69
    return get<1>(a) < get<1>(b);
70
  });
71

72
  int query_idx = 0;
73
  for (int block_idx = 1; block_idx <= num; block_idx++) {
74
    max_dist = 0;
75
    int L = r[block_idx] + 1, R = r[block_idx];
76
    memset(max_pos, 0, sizeof(max_pos));
77
    memset(min_pos, 0, sizeof(min_pos));
78

79
    while (query_idx < (int) queries.size() && pos[get<0>(queries[query_idx])] == block_idx) {
80
      auto&& [ql, qr, idx] = queries[query_idx];
81

82
      if (qr <= r[block_idx]) {
83
        ans[idx] = BruteQuery(ql, qr);
84
      } else {
85
        while (R < qr) {
86
          R++;
87
          if (!min_pos[a[R]]) min_pos[a[R]] = R;
88
          max_pos[a[R]] = R;
89
          max_dist = max(max_dist, max_pos[a[R]] - min_pos[a[R]]);
90
        }
91

92
        int _max_dist = 0, _L = L;
93
        while (L > ql) {
94
          L--;
95
          if (!_max_pos[a[L]]) _max_pos[a[L]] = L;
96
          _max_dist = max(_max_dist, max(_max_pos[a[L]], max_pos[a[L]]) - L);
97
        }
98

99
        ans[idx] = max(_max_dist, max_dist);
100

101
        while (L < _L)
102
          _max_pos[a[L++]] = 0;
103
      }
104

105
      query_idx++;
106
    }
107
  }
108

109
  for (int i = 1; i <= m; i++) {
110
    cout << ans[i] << "\n";
111
  }
112

113
  return 0;
114
}

P14420 【JOISC 2014】历史的研究 / Historical Research

容易发现删除的时候最大值不连续，所以删除不太好维护，我们考虑使用不删除莫队维护，每次回滚状态即可。

1
#include <bits/stdc++.h>
2

3
#ifdef LOCAL
4
#include <algo/debug.h>
5
#else
6
#define debug(...) 42
7
#endif
8

9
using namespace std;
10

11
using i32 = int;
12
using i64 = long long;
13
using f32 = float;
14
using f64 = double;
15

16
constexpr i32 N = 3e5 + 5;
17

18
i32 n, q, x[N];
19
i32 l[N], r[N], pos[N], block, num;
20
i64 cnt[N], ans[N], cur_max = 0;
21
vector<tuple<i32, i32, i32>> queries;
22
vector<i32> vars;
23

24
inline void Add(i32 val) {
25
  cnt[val]++;
26
  cur_max = max(cur_max, (i64) vars[val - 1] * cnt[val]);
27
}
28

29
inline void Del(i32 val) {
30
  cnt[val]--;
31
}
32

33
inline i64 BruteQuery(i32 L, i32 R) {
34
  i64 max_var = 0;
35
  map<i32, i32> cnt;
36
  for (i32 i = L; i <= R; i++) {
37
    cnt[x[i]]++;
38
    max_var = max(max_var, (i64) vars[x[i] - 1] * cnt[x[i]]);
39
  }
40
  return max_var;
41
}
42

43
int main() {
44
  ios::sync_with_stdio(false);
45
  cin.tie(nullptr);
46
  cout.tie(nullptr);
47

48
  cin >> n >> q;
49

50
  for (i32 i = 1; i <= n; i++) {
51
    cin >> x[i];
52
    vars.push_back(x[i]);
53
  }
54

55
  for (i32 i = 1; i <= q; i++) {
56
    i32 left, right;
57
    cin >> left >> right;
58
    queries.push_back(make_tuple(left, right, i));
59
  }
60

61
  sort(vars.begin(), vars.end());
62
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
63

64
  for (i32 i = 1; i <= n; i++) {
65
    x[i] = lower_bound(vars.begin(), vars.end(), x[i]) - vars.begin() + 1;
66
  }
67

68
  block = sqrt(n);
69
  num = (n + block - 1) / block;
70

71
  for (i32 i = 1; i <= num; i++) {
72
    l[i] = (i - 1) * block + 1;
73
    r[i] = min(n, i * block);
74

75
    for (i32 j = l[i]; j <= r[i]; j++)
76
      pos[j] = i;
77
  }
78

79
  for (i32 i = 1; i <= n; i++)
80
    debug(pos[i]);
81

82
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
83
    if (pos[get<0>(a)] != pos[get<0>(b)])
84
      return pos[get<0>(a)] < pos[get<0>(b)];
85
    return get<1>(a) < get<1>(b);
86
  });
87

88
  i32 query_idx = 0;
89
  for (i32 block_idx = 1; block_idx <= num; block_idx++) {
90
    cur_max = 0;
91
    i32 L = r[block_idx] + 1, R = r[block_idx];
92

93
    fill(cnt, cnt + (i32) vars.size() + 5, 0);
94

95
    while (query_idx < (i32) queries.size() && pos[get<0>(queries[query_idx])] == block_idx) {
96
      debug(L, R, cur_max, query_idx);
97

98
      auto&& [ql, qr, idx] = queries[query_idx];
99

100
      if (qr <= r[block_idx]) {
101
        ans[idx] = BruteQuery(ql, qr);
102
      } else {
103
        while (R < qr) Add(x[++R]);
104
        i64 _cur_max = cur_max;
105
        while (L > ql) Add(x[--L]);
106

107
        ans[idx] = cur_max;
108

109
        while (L <= r[block_idx]) Del(x[L++]);
110
        cur_max = _cur_max;
111
      }
112

113
      query_idx++;
114
    }
115
  }
116

117
  for (i32 i = 1; i <= q; i++) {
118
    cout << ans[i] << "\n";
119
  }
120

121
  return 0;
122
}

P8078 【WC2022】秃子酋长

发现删除好做加入难，使用回滚莫队维护。用链表维护当前的序列即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
namespace IO {
6
  template<class _tp> inline void read(_tp& x) {
7
    x = 0; _tp f = 1; char ch = getchar_unlocked();
8
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar_unlocked(); }
9
    while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar_unlocked(); }
10
    x *= f;
11
  }
12
  template<class _tp, class... args> inline void read(_tp& x, args& ...t) {
13
    read(x);
14
    read(t...);
15
  }
16
  template<class _tp> inline void _write(_tp x) {
17
    if (x < 0) putchar_unlocked('-'), x = -x;
18
    if (x > 9) _write(x / 10);
19
    putchar_unlocked(x % 10 + '0');
20
  }
21
  template<class _tp> inline void write(_tp x, char split = '\n') {
22
    _write(x);
23
    putchar(split);
24
  }
25
} using namespace IO;
26

27
constexpr int N = 5e5 + 5;
28

29
int n, m, a[N], refer[N];
30
int pos[N], l[N], r[N], block, num;
31
long long ans[N];
32

33
struct Query {
34
  int l, r, idx;
35
  Query() = default;
36
  Query(int l, int r, int i) : l(l), r(r), idx(i) {}
37
  bool operator<(const Query& rhs) const {
38
    if (pos[l] != pos[rhs.l])
39
      return pos[l] < pos[rhs.l];
40
    return r > rhs.r;
41
  }
42
} query[N];
43

44
stack<int> stk;
45

46
struct Link_t {
47
  int _prev, _next;
48
  Link_t() = default;
49
  Link_t(int l, int r) : _prev(l), _next(r) {}
50
  inline int& prev() { return _prev; }
51
  inline int& next() { return _next; }
52
} Link[N];
53

54
inline long long Del(int p) {
55
  long long cur = 0;
56
  if (Link[p].prev() != 0 && Link[p].next() != 0)
57
    cur += abs(refer[Link[p].prev()] - refer[Link[p].next()]);
58
  if (Link[p].prev() != 0)
59
    cur -= abs(refer[p] - refer[Link[p].prev()]);
60
  if (Link[p].next() != 0)
61
    cur -= abs(refer[p] - refer[Link[p].next()]);
62

63
  stk.push(p);
64
  Link[Link[p].prev()].next() = Link[p].next();
65
  Link[Link[p].next()].prev() = Link[p].prev();
66

67
  return cur;
68
}
69

70
inline void Undo() {
71
  int p = stk.top();
72
  stk.pop();
73
  Link[Link[p].prev()].next() = p;
74
  Link[Link[p].next()].prev() = p;
75
}
76

77
int main() {
78
  // cin >> n >> m;
79
  read(n, m);
80

81
  for (int i = 1; i <= n; i++) {
82
    // cin >> a[i];
83
    read(a[i]);
84
    refer[a[i]] = i;
85
  }
86

87
  for (int i = 1; i <= n; i++) {
88
    Link[i].prev() = i - 1;
89
    Link[i].next() = i + 1;
90
  }
91
  Link[n].next() = 0;
92

93
  for (int i = 1; i <= m; i++) {
94
    // cin >> query[i].l >> query[i].r;
95
    read(query[i].l, query[i].r);
96
    query[i].idx = i;
97
  }
98

99
  block = sqrt(n);
100
  num = (n + block - 1) / block;
101

102
  for (int i = 1; i <= num; i++) {
103
    l[i] = (i - 1) * block + 1;
104
    r[i] = min(n, i * block);
105

106
    for (int j = l[i]; j <= r[i]; j++)
107
      pos[j] = i;
108
  }
109

110
  sort(query + 1, query + m + 1);
111

112
  int L = 1, R = n, lst_block = 1;
113
  long long tmp = 0, cur = 0;
114

115
  for (int i = 2; i <= n; i++) {
116
    cur += abs(refer[i] - refer[i - 1]);
117
  }
118

119
  tmp = cur;
120

121
  for (int i = 1; i <= m; i++) {
122
    auto&& [ql, qr, idx] = query[i];
123

124
    if (pos[ql] != lst_block) {
125
      while (!stk.empty()) Undo();
126
      while (L < l[pos[ql]]) cur += Del(a[L++]);
127
      tmp = cur;
128
      R = n;
129
      lst_block = pos[ql];
130
      while (!stk.empty()) stk.pop();
131
    }
132

133
    while (R > qr) tmp += Del(a[R--]);
134

135
    long long _tmp = tmp, _L = L;
136
    while (_L < ql) _tmp += Del(a[_L++]);
137
    while (_L > L) Undo(), _L--;
138

139
    ans[idx] = _tmp;
140
  }
141

142
  for (int i = 1; i <= m; i++) {
143
    // cout << ans[i] << "\n";
144
    write(ans[i]);
145
  }
146

147
  return 0;
148
}

树上莫队

我们维护一个括号序列，在 dfs 的时候每次访问和回溯都加入到括号序列当中，定义 $in_u$ 和 $out_u$ 表示 $u$ 节点进入和退出 dfs 时在括号序列的位置，每次查询 $(u,v)$ 分为两种情况：

直链：对应的括号序列的区间为 $in_u \sim in_v$ ，中间若同一个节点出现两次，则正负抵消，因为这样的节点一定不在 $u \to v$ 的路径上。
折链：用树剖的思想，将 $u \to v$ 转化为 $u \to \mathrm{LCA}(u, v)$ 和 $v \to \mathrm{LCA}(u, v)$ ，这样就得到了两条直链，直接维护即可。

P4074 【WC2013】糖果公园

模板题。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 5e5 + 5;
6
constexpr int K = 25;
7

8
int n, m, q, v[N], w[N], c[N], lst[N];
9
int l[N], r[N], pos[N], block, num;
10
int seq[N], refer[N], in[N], out[N], cnt = 0;
11
int jmp[N][K], dep[N];
12
int f[N], tot[N];
13
long long cur, ans[N];
14
vector<int> adj[N];
15
vector<tuple<int, int, int, int>> query, modify;
16

17
inline void Dfs(int u, int fa) {
18
  dep[u] = dep[fa] + 1;
19
  seq[++cnt] = u;
20
  in[u] = cnt;
21
  jmp[u][0] = fa;
22

23
  for (int k = 1; k < K; k++)
24
    jmp[u][k] = jmp[jmp[u][k - 1]][k - 1];
25

26
  for (auto v : adj[u]) {
27
    if (v == fa) continue;
28
    Dfs(v, u);
29
  }
30

31
  seq[++cnt] = u;
32
  out[u] = cnt;
33
}
34

35
inline int GetLCA(int u, int v) {
36
  if (dep[u] > dep[v]) swap(u, v);
37

38
  for (int k = K - 1; k >= 0; k--) {
39
    if (dep[jmp[v][k]] >= dep[u])
40
      v = jmp[v][k];
41
  }
42

43
  if (u == v)
44
    return u;
45

46
  for (int k = K - 1; k >= 0; k--) {
47
    if (jmp[u][k] != jmp[v][k])
48
      tie(u, v) = tie(jmp[u][k], jmp[v][k]);
49
  }
50

51
  return jmp[u][0];
52
}
53

54
inline void Chg(int pos) {
55
  if (f[pos]) {
56
    cur -= (long long) v[c[pos]] * w[tot[c[pos]]];
57
    tot[c[pos]]--;
58
  } else {
59
    tot[c[pos]]++;
60
    cur += (long long) v[c[pos]] * w[tot[c[pos]]];
61
  }
62
  f[pos] ^= 1;
63
}
64

65
inline void Upd(int x, int t) {
66
  if (f[x]) {
67
    Chg(x);
68
    c[x] = t;
69
    Chg(x);
70
  } else {
71
    c[x] = t;
72
  }
73
}
74

75
signed main() {
76
  ios::sync_with_stdio(false);
77
  cin.tie(nullptr);
78
  cout.tie(nullptr);
79

80
  // freopen("P4074_4.in", "r", stdin);
81

82
  cin >> n >> m >> q;
83

84
  for (int i = 1; i <= m; i++) {
85
    cin >> v[i];
86
  }
87
  for (int i = 1; i <= n; i++) {
88
    cin >> w[i];
89
  }
90

91
  for (int i = 1; i < n; i++) {
92
    int u, v;
93
    cin >> u >> v;
94
    adj[u].push_back(v);
95
    adj[v].push_back(u);
96
  }
97

98
  for (int i = 1; i <= n; i++) {
99
    cin >> c[i];
100
    lst[i] = c[i];
101
  }
102

103
  Dfs(1, 0);
104

105
  memset(ans, -1, sizeof(ans));
106
  for (int i = 1; i <= q; i++) {
107
    int typ, x, y;
108
    cin >> typ >> x >> y;
109

110
    if (typ == 0) {
111
      modify.push_back(tuple(x, lst[x], y, i));
112
      lst[x] = y;
113
    } else if (typ == 1) {
114
      if (in[x] > in[y])
115
        swap(x, y);
116
      query.push_back(tuple(GetLCA(x, y) == x ? in[x] : out[x], in[y], i, i));
117
    }
118
  }
119

120
  block = pow(2 * n, 2.0 / 3);
121
  num = (2 * n + block - 1) / block;
122

123
  for (int i = 1; i <= num; i++) {
124
    l[i] = (i - 1) * block + 1;
125
    r[i] = min(2 * n, i * block);
126

127
    for (int j = l[i]; j <= r[i]; j++)
128
      pos[j] = i;
129
  }
130

131
  sort(query.begin(), query.end(), [&] (auto a, auto b) {
132
    if (pos[get<0>(a)] != pos[get<0>(b)])
133
      return pos[get<0>(a)] < pos[get<0>(b)];
134
    if (pos[get<1>(a)] != pos[get<1>(b)])
135
      return pos[get<1>(a)] < pos[get<1>(b)];
136
    return get<2>(a) < get<2>(b);
137
  });
138
  // sort(modify.begin(), modify.end(), [&] (auto a, auto b) {
139
  //   return get<3>(a) < get<3>(b);
140
  // });
141

142
  int L = 1, R = 0, T = -1;
143

144
  for (int i = 0; i < (int) query.size(); i++) {
145
    auto&& [ql, qr, idx, _] = query[i];
146

147
    while (!modify.empty() && T + 1 < (int) modify.size() && get<3>(modify[T + 1]) < idx) {
148
      T++;
149
      Upd(get<0>(modify[T]), get<2>(modify[T]));
150
    }
151
    while (!modify.empty() && T >= 0 && get<3>(modify[T]) > idx) {
152
      Upd(get<0>(modify[T]), get<1>(modify[T]));
153
      T--;
154
    }
155

156
    while (L > ql) Chg(seq[--L]);
157
    while (L < ql) Chg(seq[L++]);
158
    while (R > qr) Chg(seq[R--]);
159
    while (R < qr) Chg(seq[++R]);
160

161
    int x = seq[ql], y = seq[qr];
162
    int LCA = GetLCA(x, y);
163

164
    if (x != LCA && y != LCA) {
165
      Chg(LCA);
166
      ans[idx] = cur;
167
      Chg(LCA);
168
    } else {
169
      ans[idx] = cur;
170
    }
171
  }
172

173
  for (int i = 1; i <= q; i++) {
174
    if (ans[i] == -1) continue;
175
    cout << ans[i] << "\n";
176
  }
177

178
  return 0;
179
}

P4689 【Ynoi Easy Round 2016】这是我自己的发明 - 洛谷

用类似 P5268 的方式将映射在括号序上的询问拆分一下即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 1e5 + 5;
6
constexpr int K = 25;
7
constexpr int M = 5e5 + 5;
8

9
int n, m, a[N];
10
int l[N], r[N], pos[N], block, num;
11
int dfn[N], t = 0, rf[N], dep[N], siz[N];
12
int jmp[N][K];
13
int cl[N], cr[N];
14
long long ans[M], cur;
15
vector<int> vars, adj[N];
16

17
struct Query {
18
  int ql, qr, f, idx;
19
  bool operator<(const Query& rhs) const {
20
    if (pos[ql] != pos[rhs.ql])
21
      return pos[ql] < pos[rhs.ql];
22
    return qr < rhs.qr;
23
  }
24
};
25
vector<Query> query;
26

27
inline void Dfs(int u, int father) {
28
  dep[u] = dep[father] + 1;
29
  jmp[u][0] = father;
30
  siz[u] = 1;
31
  dfn[u] = ++t;
32
  for (int k = 1; k < K; k++)
33
    jmp[u][k] = jmp[jmp[u][k - 1]][k - 1];
34

35
  for (auto&& v : adj[u]) {
36
    if (v == father) continue;
37
    Dfs(v, u);
38
    siz[u] += siz[v];
39
  }
40
}
41

42
inline int GetKth(int u, int kth) {
43
  for (int k = K - 1; k >= 0; k--) {
44
    if (kth >> k & 1)
45
      u = jmp[u][k];
46
  }
47
  return u;
48
}
49

50
inline vector<pair<int, int>> GetRanges(int u, int root) {
51
  vector<pair<int, int>> ranges;
52
  if (u == root) {
53
    ranges.push_back(pair(1, t));
54
  } else if (dfn[root] >= dfn[u] && dfn[root] <= dfn[u] + siz[u] - 1) {
55
    int kth = GetKth(root, dep[root] - dep[u] - 1);
56
    if (dfn[kth] - 1 >= 1)
57
      ranges.push_back(pair(1, dfn[kth] - 1));
58
    if (dfn[kth] + siz[kth] <= t)
59
      ranges.push_back(pair(dfn[kth] + siz[kth], t));
60
  } else {
61
    ranges.push_back(pair(dfn[u], dfn[u] + siz[u] - 1));
62
  }
63

64
  return ranges;
65
}
66

67
inline void UpdL(int var, int f) {
68
  cur += f * cr[var];
69
  cl[var] += f;
70
}
71

72
inline void UpdR(int var, int f) {
73
  cur += f * cl[var];
74
  cr[var] += f;
75
}
76

77
int main() {
78
  ios::sync_with_stdio(false);
79
  cin.tie(nullptr);
80
  cout.tie(nullptr);
81

82
  cin >> n >> m;
83

84
  for (int i = 1; i <= n; i++) {
85
    cin >> a[i];
86
    vars.push_back(a[i]);
87
  }
88

89
  sort(vars.begin(), vars.end());
90
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
91

92
  for (int i = 1, u, v; i < n; i++) {
93
    cin >> u >> v;
94
    adj[u].push_back(v);
95
    adj[v].push_back(u);
96
  }
97

98
  Dfs(1, 0);
99

100
  for (int i = 1; i <= n; i++) {
101
    rf[dfn[i]] = (int) (lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1);
102
  }
103

104
  memset(ans, -1, sizeof(ans));
105

106
  int root = 1;
107
  for (int i = 1; i <= m; i++) {
108
    int tp, x, y;
109
    cin >> tp;
110

111
    if (tp == 1) {
112
      cin >> x;
113
      root = x;
114
    } else {
115
      cin >> x >> y;
116
      auto a = GetRanges(x, root), b = GetRanges(y, root);
117

118
      ans[i] = 0;
119
      for (auto&& va : a) {
120
        for (auto&& vb : b) {
121
          query.push_back({va.second, vb.second, 1, i});
122
          query.push_back({va.first - 1, vb.second, -1, i});
123
          query.push_back({va.second, vb.first - 1, -1, i});
124
          query.push_back({va.first - 1, vb.first - 1, 1, i});
125
        }
126
      }
127
    }
128
  }
129

130
  for (auto&& [ql, qr, f, idx] : query) {
131
    if (ql > qr) swap(ql, qr);
132
  }
133

134
  block = sqrt(n);
135
  num = (n + block - 1) / block;
136

137
  for (int i = 1; i <= num; i++) {
138
    l[i] = (i - 1) * block + 1;
139
    r[i] = min(t, i * block);
140

141
    for (int j = l[i]; j <= r[i]; j++)
142
      pos[j] = i;
143
  }
144

145
  sort(query.begin(), query.end());
146

147
  int L = 0, R = 0;
148
  for (auto&& [ql, qr, f, idx] : query) {
149
    while (L < ql) UpdL(rf[++L], 1);
150
    while (L > ql) UpdL(rf[L--], -1);
151
    while (R < qr) UpdR(rf[++R], 1);
152
    while (R > qr) UpdR(rf[R--], -1);
153

154
    ans[idx] += cur * f;
155
  }
156

157
  for (int i = 1; i <= m; i++) {
158
    if (ans[i] == -1) continue;
159
    cout << ans[i] << "\n";
160
  }
161

162
  return 0;
163
}

P5268 【SNOI2017】一个简单的询问

容易发现 $\operatorname{get}(l, r, x) = \operatorname{get}(r, 1, x) - \operatorname{get}(l - 1, 1, x)$ ，直接拆式子分两段维护即可。注意莫队双指针的移动方式。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 5e4 + 5;
6

7
int n, q, a[N];
8
int l[N], r[N], pos[N], block, num;
9
int cl[N], cr[N];
10
long long ans[N], cur;
11
vector<tuple<int, int, int, int>> query;
12

13
inline void UpdL(int val, int f) {
14
  cur += f * cr[val];
15
  cl[val] += f;
16
}
17

18
inline void UpdR(int val, int f) {
19
  cur += f * cl[val];
20
  cr[val] += f;
21
}
22

23
int main() {
24
  ios::sync_with_stdio(false);
25
  cin.tie(nullptr);
26
  cout.tie(nullptr);
27

28
  cin >> n;
29

30
  for (int i = 1; i <= n; i++) {
31
    cin >> a[i];
32
  }
33

34
  cin >> q;
35
  for (int i = 1; i <= q; i++) {
36
    int l1, r1, l2, r2;
37
    cin >> l1 >> r1 >> l2 >> r2;
38

39
    query.push_back(tuple(r1, r2, 1, i));
40
    query.push_back(tuple(l1 - 1, r2, -1, i));
41
    query.push_back(tuple(r1, l2 - 1, -1, i));
42
    query.push_back(tuple(l1 - 1, l2 - 1, 1, i));
43
  }
44

45
  for (auto&& [ql, qr, f, idx] : query) {
46
    if (ql > qr) swap(ql, qr);
47
  }
48

49
  block = sqrt(n);
50
  num = (n + block - 1) / block;
51

52
  for (int i = 1; i <= num; i++) {
53
    l[i] = (i - 1) * block + 1;
54
    r[i] = i * block;
55

56
    for (int j = l[i]; j <= r[i]; j++)
57
      pos[j] = i;
58
  }
59

60
  sort(query.begin(), query.end(), [&] (auto a, auto b) -> bool {
61
    if (pos[get<0>(a)] != pos[get<0>(b)])
62
      return pos[get<0>(a)] < pos[get<0>(b)];
63
    if (pos[get<0>(a)] & 1)
64
      return get<1>(a) < get<1>(b);
65
    return get<1>(a) > get<1>(b);
66
  });
67

68
  int L = 0, R = 0;
69
  for (auto&& [ql, qr, f, idx] : query) {
70
    while (L < ql) UpdL(a[++L], 1);
71
    while (L > ql) UpdL(a[L--], -1);
72
    while (R < qr) UpdR(a[++R], 1);
73
    while (R > qr) UpdR(a[R--], -1);
74

75
    ans[idx] += f * cur;
76
  }
77

78
  for (int i = 1; i <= q; i++) {
79
    cout << ans[i] << "\n";
80
  }
81

82
  return 0;
83
}