莫队

18 天前(已编辑)
14
1

莫队

普通莫队

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

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

#include<bits/stdc++.h>

using namespace std;

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

struct Query {
    int l, r, id;
}Q[N];

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

void add(int x) {
    int val = cnt[a[x]];
    cnt[a[x]] ++;
    now = now - val * val + cnt[a[x]] * cnt[a[x]];
}

void del(int x) {
    int val = cnt[a[x]];
    cnt[a[x]] --;
    now = now - val * val + cnt[a[x]] * cnt[a[x]];
}

int main() {
    cin >> n >> m >> k;
    
    int block = sqrt(n);
    int num = ceil((double) n / (double) block);
    
    for(int i = 1; i <= num; i ++) {
        L[i] = (i - 1) * block + 1;
        R[i] = i * block;
        
        for(int j = L[i]; j <= R[i]; j ++) {
            pos[j] = i;
        }
    }
    
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    
    for(int i = 1; i <= m; i ++) {
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }
    
    sort(Q + 1, Q + m + 1, cmp);
    
    int left = 1, right = 0;
    
    for(int i = 1; i <= m; i ++) {
        int l = Q[i].l, r = Q[i].r, id = Q[i].id;
        
        while(left < l) del(left ++);
        while(left > l) add(-- left);
        while(right < r) add(++ right);
        while(right > r) del(right --);
        
        ans[id] = now;
    }
    
    for(int i = 1; i <= m; i ++) cout << ans[i] << endl;
    
    return 0;
}

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

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

#include <bits/stdc++.h>

using namespace std;

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

long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

struct Query {
  int l, r, id;
  
  bool operator < (const Query & rhv) const {
    if (pos[l] == pos[rhv.l]) return r < rhv.r;
    return l < rhv.l;
  }
} query[N];

void update(int pos, int add) {
  answer -= cnt[a[pos]] * cnt[a[pos]];
  cnt[a[pos]] += add;
  answer += cnt[a[pos]] * cnt[a[pos]];
}

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

  cin >> n >> m;

  int block = sqrt(n);

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

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

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

  int L = 1, R = 0;

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

    if (query[i].l == query[i].r) {
      result[query[i].id] = make_pair(0, 1);
      continue;
    }
    
    long long a = answer - (query[i].r - query[i].l + 1);
    long long b = (long long) (query[i].r - query[i].l + 1) * (query[i].r - query[i].l);
    long long gcd_value = gcd(a, b);
    
    result[query[i].id] = make_pair(a / gcd_value, b / gcd_value);
  }
  
  for (int i = 1; i <= m; i ++) {
    cout << result[i].first << "/" << result[i].second << '\n';
  }

  return 0;
}

P4462 【CQOI2018】 异或序列

我们定义 prei=⊕j=1iaipre_i = \oplus^{i}_{j=1} a_i，询问我们有多少组 (x,y)(x, y) 满足 ax⊕ax+1⊕ax+2⊕⋯⊕ay−2⊕ay−1⊕ay=ka_x \oplus a_{x+1} \oplus a_{x+2} \oplus \dots \oplus a_{y-2} \oplus a_{y-1} \oplus a_y = k 即为 prey⊕prex−1=kpre_y \oplus pre_{x-1} = k，开桶统计即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;
using f32 = float;
using f64 = double;

constexpr i32 N = 1e5 + 5;

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

inline void Add(i32 i) {
  cur += sum[a[i] ^ k];
  sum[a[i]]++;
}

inline void Del(i32 i) {
  sum[a[i]]--;
  cur -= sum[a[i] ^ k];
}

i32 main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n >> m >> k;
  
  for (i32 i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  
  queries.resize(m);
  for (i32 i = 0; i < m; i++) {
    cin >> get<0>(queries[i]) >> get<1>(queries[i]);
    get<2>(queries[i]) = i;
  }
  
  block = sqrt(n);
  num = (n + block - 1) / block;
  
  for (i32 i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = i * block;
    for (i32 j = l[i]; j <= r[i]; j++) {
      pos[j] = i;
    }
  }
  
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
    if (pos[get<0>(a)] != pos[get<0>(b)])
      return pos[get<0>(a)] < pos[get<0>(b)];
    else if (pos[get<0>(a)] & 1)
      return get<1>(a) > get<1>(b);
    else
      return get<1>(a) < get<1>(b);
  });
  
  i32 L = 0, R = 0;
  sum[0] = 1;
  for (i32 i = 0; i < (i32) queries.size(); i++) {
    while (L < get<0>(queries[i]) - 1)
      Del(L++);
    while (L > get<0>(queries[i]) - 1)
      Add(--L);
    while (R < get<1>(queries[i]))
      Add(++R);
    while (R > get<1>(queries[i]))
      Del(R--);
    
    ans[get<2>(queries[i])] = cur;
  }
  
  for (i32 i = 0; i < m; i++) {
    cout << ans[i] << "\n";
  }
  
  return 0;
}

P3709 大爷的字符串题

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

#include <bits/stdc++.h>

using namespace std;

using i32 = int;
using i64 = long long;
using f32 = float;
using f64 = double;

constexpr i32 N = 2e5 + 5;

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

inline void Add(i32 i) {
  refer[tot[a[i]]]--;
  tot[a[i]]++;
  refer[tot[a[i]]]++;
  cur = max(cur, tot[a[i]]);
}

inline void Del(i32 i) {
  refer[tot[a[i]]]--;
  if (cur == tot[a[i]] && refer[tot[a[i]]] == 0)
    cur--;
  tot[a[i]]--;
  refer[tot[a[i]]]++;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n >> m;
  
  for (i32 i = 1; i <= n; i++) {
    cin >> a[i];
    vars.push_back(a[i]);
  }
  
  sort(vars.begin(), vars.end());
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
  
  for (i32 i = 1; i <= n; i++) {
    a[i] = (i32) (lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1);
  }
  
  queries.resize(m);
  for (i32 i = 0; i < m; i++) {
    cin >> get<0>(queries[i]) >> get<1>(queries[i]);
    get<2>(queries[i]) = i;
  }
  
  block = sqrt(n);
  num = (n + block - 1) / block;
  
  for (i32 i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = min(n, i * block);
    
    for (int j = l[i]; j <= r[i]; j++)
      pos[j] = i;
  }
  
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
    if (pos[get<0>(a)] != pos[get<0>(b)])
      return pos[get<0>(a)] < pos[get<0>(b)];
    if (pos[get<0>(a)] & 1)
      return get<1>(a) < get<1>(b);
    return get<1>(a) > get<1>(b);
  });
  
  i32 L = 0, R = 0;
  refer[0] = n;
  for (i32 i = 0; i < (i32) queries.size(); i++) {
    while (L < get<0>(queries[i]))
      Del(L++);
    while (L > get<0>(queries[i]))
      Add(--L);
    while (R < get<1>(queries[i]))
      Add(++R);
    while (R > get<1>(queries[i]))
      Del(R--);
    
    ans[get<2>(queries[i])] = -cur;
  }
  
  for (i32 i = 0; i < m; i++) {
    cout << ans[i] << "\n";
  }
  
  return 0;
}

带修莫队

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

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

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

#include <bits/stdc++.h>

#ifdef LOCAL
#include <algo/debug.h>
#else
#define debug(...) 42
#endif

using namespace std;

constexpr int N = 6e5 + 5;

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

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

struct Fenwick {
  int tr[N], Limit = 0;
  Fenwick() = default;
  Fenwick(int n) : Limit(n) {
    fill(tr, tr + Limit + 1, 0);
  }
  static int Lowbit(int x) {
    return x & (-x);
  }
  void Modify(int pos, int var) {
    for (int i = pos; i <= Limit; i += Lowbit(i))
      tr[i] += var;
  }
  int Query(int pos) {
    int retval = 0;
    for (int i = pos; i; i -= Lowbit(i))
      retval += tr[i];
    return retval;
  }
} tr;

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

void CDQ(int l, int r) {
  if (l == r) return;
  
  int mid = (l + r) >> 1;
  CDQ(l, mid);
  CDQ(mid + 1, r);
  
  sort(ops + l, ops + mid + 1, [&] (auto a, auto b) {
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
  });
  sort(ops + mid + 1, ops + r + 1, [&] (auto a, auto b) {
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
  });
  
  int pl = l, pr = mid + 1;
  while (pr <= r) {
    while (pl <= mid && ops[pl].y < ops[pr].y) {
      if (ops[pl].type == 1) {
        tr.Modify(ops[pl].x, ops[pl].val);
      }
      pl++;
    }
    
    if (ops[pr].type == 2) {
      answer[ops[pr].index] += tr.Query(ops[pr].r) - tr.Query(ops[pr].x - 1);
    }
    pr++;
  }
  
  for (int i = l; i < pl; i++) {
    if (ops[i].type == 1) {
      tr.Modify(ops[i].x, -ops[i].val);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n >> m;
  
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
    cpy[i] = c[i];
    vars.push_back(c[i]);
  }
  
  vector<tuple<char, int, int>> raw(m + 1);
  for (int i = 1; i <= m; i++) {
    auto&& [x, y, z] = raw[i];
    cin >> x >> y >> z;
    
    if (x == 'R') {
      vars.push_back(z);
    }
  }
  
  sort(vars.begin(), vars.end());
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
  
  for (int i = 1; i <= n; i++) {
    positions[GetColor(c[i])].insert(i);
  }
  
  for (int i = 1; i <= n; i++) {
    int cur_col = GetColor(c[i]);
    ops[++cnt_op] = Op{1, i, 0, lst[cur_col], 1, 0};
    lst[cur_col] = i;
  }
  
  for (int i = 1; i <= m; i++) {
    if (get<0>(raw[i]) == 'Q') {
      auto&& [op, l, r] = raw[i];
      
      ops[++cnt_op] = Op{2, l, r, l, 0, ++cnt_queries};
    } else if (get<0>(raw[i]) == 'R') {
      auto&& [op, pos, nxt_col] = raw[i];
      int cur_col = cpy[pos];
      
      auto Current = positions[GetColor(cur_col)].find(pos);
      int pre = 0, suc = 0;
      if (Current != positions[GetColor(cur_col)].begin()) {
        pre = *prev(Current);
      }
      if (next(Current) != positions[GetColor(cur_col)].end()) {
        suc = *next(Current);
      }
      
      ops[++cnt_op] = Op{1, pos, 0, pre, -1, 0};
      
      if (suc != 0) {
        ops[++cnt_op] = Op{1, suc, 0, pos,  -1, 0};
        ops[++cnt_op] = Op{1, suc, 0, pre, 1, 0};
      }
      positions[GetColor(cur_col)].erase(Current);
      
      Current = positions[GetColor(nxt_col)].lower_bound(pos);
      pre = 0, suc = 0;
      if (Current != positions[GetColor(nxt_col)].begin()) {
        pre = *prev(Current);
      }
      if (Current != positions[GetColor(nxt_col)].end()) {
        suc = *Current;
      }
      
      ops[++cnt_op] = Op{1, pos, 0, pre, 1, 0};
      
      if (suc != 0) {
        ops[++cnt_op] = Op{1, suc, 0, pre, -1, 0};
        ops[++cnt_op] = Op{1, suc, 0, pos, 1, 0};
      }
      positions[GetColor(nxt_col)].insert(pos);
      
      cpy[pos] = nxt_col;
    }
  }
  
  tr = Fenwick(n);
  CDQ(1, cnt_op);
  
  for (int i = 1; i <= cnt_queries; i++) {
    cout << answer[i] << "\n";
  }
  
  return 0;
}

Problem - 940F - Codeforces

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

#include <bits/stdc++.h>

using namespace std;

using i32 = int;
using i64 = long long;
using f32 = float;
using f64 = double;

constexpr i32 N = 5e5 + 5;

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

inline void Add(i32 val) {
  if (cnt[val] > 0) tot[cnt[val]]--;
  cnt[val]++;
  if (cnt[val] > 0) tot[cnt[val]]++;
}

inline void Del(i32 val) {
  if (cnt[val] > 0) tot[cnt[val]]--;
  cnt[val]--;
  if (cnt[val] > 0) tot[cnt[val]]++;
}

inline void Upd(i32 idx_q, i32 idx_m) {
  if (get<0>(modify[idx_m]) >= get<0>(query[idx_q]) && get<0>(modify[idx_m]) <= get<1>(query[idx_q])) {
    Del(a[get<0>(modify[idx_m])]);
    Add(get<1>(modify[idx_m]));
  }
  swap(get<1>(modify[idx_m]), a[get<0>(modify[idx_m])]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n >> q;
  
  for (i32 i = 1; i <= n; i++) {
    cin >> a[i];
    vars.push_back(a[i]);
  }
  
  for (i32 i = 1; i <= q; i++) {
    i32 op, l, r;
    cin >> op >> l >> r;
    
    if (op == 1) {
      query.push_back(make_tuple(l, r, i));
    } else {
      modify.push_back(make_tuple(l, r, i));
      vars.push_back(r);
    }
  }
  
  sort(vars.begin(), vars.end());
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
  
  for (i32 i = 1; i <= n; i++) {
    a[i] = lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1;
  }
  for (i32 i = 0; i < (i32) modify.size(); i++) {
    get<1>(modify[i]) = lower_bound(vars.begin(), vars.end(), get<1>(modify[i])) - vars.begin() + 1;
  }
  
  block = pow(n, 2.0 / 3);
  num = (n + block - 1) / block;
  
  for (i32 i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = min(i * block, n);
    
    for (i32 j = l[i]; j <= r[i]; j++)
      pos[j] = i;
  }
  
  sort(query.begin(), query.end(), [&] (auto a, auto b) {
    if (pos[get<0>(a)] != pos[get<0>(b)])
      return pos[get<0>(a)] < pos[get<0>(b)];
    if (pos[get<1>(a)] != pos[get<1>(b)])
      return pos[get<1>(a)] < pos[get<1>(b)];
    return get<2>(a) < get<2>(b);
  });
  sort(modify.begin(), modify.end(), [&] (auto a, auto b) {
    return get<2>(a) < get<2>(b);
  });
  
  i32 L = 0, R = 0, idx = -1;
  for (i32 i = 0; i < (i32) query.size(); i++) {
    while (L < get<0>(query[i]))
      Del(a[L++]);
    while (L > get<0>(query[i]))
      Add(a[--L]);
    while (R < get<1>(query[i]))
      Add(a[++R]);
    while (R > get<1>(query[i]))
      Del(a[R--]);
    while (idx + 1 < (i32) modify.size() && get<2>(modify[idx + 1]) < get<2>(query[i]))
      Upd(i, ++idx);
    while (idx >= 0 && get<2>(modify[idx]) > get<2>(query[i]))
      Upd(i, idx--);
    
    ans[get<2>(query[i])] = 1;
    while (tot[ans[get<2>(query[i])]] > 0) ans[get<2>(query[i])]++;
  }
  
  for (int i = 1; i <= q; i++) {
    if (ans[i]) cout << ans[i] << "\n";
  }
  
  return 0;
}

回滚莫队

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

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

板子题。

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 4e5 + 5;

int n, m, a[N];
int l[N], r[N], pos[N], block, num;
int max_pos[N], min_pos[N], _max_pos[N];
int max_dist, ans[N];
vector<tuple<int, int, int>> queries;
vector<int> vars;

inline int BruteQuery(int l, int r) {
  static int mx[N], mn[N];
  int res = 0;
  for (int i = l; i <= r; i++) {
    if (!mn[a[i]]) mn[a[i]] = i;
    mx[a[i]] = i;
    res = max(res, mx[a[i]] - mn[a[i]]);
  }
  
  for (int i = l; i <= r; i++)
    mx[a[i]] = mn[a[i]] = 0;
  
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n;
  
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    vars.push_back(a[i]);
  }
  
  sort(vars.begin(), vars.end());
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
  
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1;
  }
  
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int left, right;
    cin >> left >> right;
    queries.push_back(make_tuple(left, right, i));
  }
  
  block = sqrt(n);
  num = (n + block - 1) / block;
  
  for (int i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = min(i * block, n);
    
    for (int j = l[i]; j <= r[i]; j++)
      pos[j] = i;
  }
  
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
    if (pos[get<0>(a)] != pos[get<0>(b)])
      return pos[get<0>(a)] < pos[get<0>(b)];
    return get<1>(a) < get<1>(b);
  });
  
  int query_idx = 0;
  for (int block_idx = 1; block_idx <= num; block_idx++) {
    max_dist = 0;
    int L = r[block_idx] + 1, R = r[block_idx];
    memset(max_pos, 0, sizeof(max_pos));
    memset(min_pos, 0, sizeof(min_pos));
    
    while (query_idx < (int) queries.size() && pos[get<0>(queries[query_idx])] == block_idx) {
      auto&& [ql, qr, idx] = queries[query_idx];
      
      if (qr <= r[block_idx]) {
        ans[idx] = BruteQuery(ql, qr);
      } else {
        while (R < qr) {
          R++;
          if (!min_pos[a[R]]) min_pos[a[R]] = R;
          max_pos[a[R]] = R;
          max_dist = max(max_dist, max_pos[a[R]] - min_pos[a[R]]);
        }
        
        int _max_dist = 0, _L = L;
        while (L > ql) {
          L--;
          if (!_max_pos[a[L]]) _max_pos[a[L]] = L;
          _max_dist = max(_max_dist, max(_max_pos[a[L]], max_pos[a[L]]) - L);
        }
        
        ans[idx] = max(_max_dist, max_dist);
        
        while (L < _L)
          _max_pos[a[L++]] = 0;
      }
      
      query_idx++;
    }
  }
  
  for (int i = 1; i <= m; i++) {
    cout << ans[i] << "\n";
  }
  
  return 0;
}

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

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

#include <bits/stdc++.h>

#ifdef LOCAL
#include <algo/debug.h>
#else
#define debug(...) 42
#endif

using namespace std;

using i32 = int;
using i64 = long long;
using f32 = float;
using f64 = double;

constexpr i32 N = 3e5 + 5;

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

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

inline void Del(i32 val) {
  cnt[val]--;
}

inline i64 BruteQuery(i32 L, i32 R) {
  i64 max_var = 0;
  map<i32, i32> cnt;
  for (i32 i = L; i <= R; i++) {
    cnt[x[i]]++;
    max_var = max(max_var, (i64) vars[x[i] - 1] * cnt[x[i]]);
  }
  return max_var;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n >> q;
  
  for (i32 i = 1; i <= n; i++) {
    cin >> x[i];
    vars.push_back(x[i]);
  }
  
  for (i32 i = 1; i <= q; i++) {
    i32 left, right;
    cin >> left >> right;
    queries.push_back(make_tuple(left, right, i));
  }
  
  sort(vars.begin(), vars.end());
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
  
  for (i32 i = 1; i <= n; i++) {
    x[i] = lower_bound(vars.begin(), vars.end(), x[i]) - vars.begin() + 1;
  }
  
  block = sqrt(n);
  num = (n + block - 1) / block;
  
  for (i32 i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = min(n, i * block);
    
    for (i32 j = l[i]; j <= r[i]; j++)
      pos[j] = i;
  }
  
  for (i32 i = 1; i <= n; i++)
    debug(pos[i]);
  
  sort(queries.begin(), queries.end(), [&] (auto a, auto b) {
    if (pos[get<0>(a)] != pos[get<0>(b)])
      return pos[get<0>(a)] < pos[get<0>(b)];
    return get<1>(a) < get<1>(b);
  });
  
  i32 query_idx = 0;
  for (i32 block_idx = 1; block_idx <= num; block_idx++) {
    cur_max = 0;
    i32 L = r[block_idx] + 1, R = r[block_idx];
    
    fill(cnt, cnt + (i32) vars.size() + 5, 0);
    
    while (query_idx < (i32) queries.size() && pos[get<0>(queries[query_idx])] == block_idx) {
      debug(L, R, cur_max, query_idx);
      
      auto&& [ql, qr, idx] = queries[query_idx];
      
      if (qr <= r[block_idx]) {
        ans[idx] = BruteQuery(ql, qr);
      } else {
        while (R < qr) Add(x[++R]);
        i64 _cur_max = cur_max;
        while (L > ql) Add(x[--L]);
        
        ans[idx] = cur_max;
        
        while (L <= r[block_idx]) Del(x[L++]);
        cur_max = _cur_max;
      }
      
      query_idx++;
    }
  }
  
  for (i32 i = 1; i <= q; i++) {
    cout << ans[i] << "\n";
  }
  
  return 0;
}

P8078 【WC2022】 秃子酋长

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

#include <bits/stdc++.h>

using namespace std;

namespace IO {
  template<class _tp> inline void read(_tp& x) {
    x = 0; _tp f = 1; char ch = getchar_unlocked();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar_unlocked(); }
    while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar_unlocked(); }
    x *= f;
  }
  template<class _tp, class... args> inline void read(_tp& x, args& ...t) {
    read(x);
    read(t...);
  }
  template<class _tp> inline void _write(_tp x) {
    if (x < 0) putchar_unlocked('-'), x = -x;
    if (x > 9) _write(x / 10);
    putchar_unlocked(x % 10 + '0');
  }
  template<class _tp> inline void write(_tp x, char split = '\n') {
    _write(x);
    putchar(split);
  }
} using namespace IO;

constexpr int N = 5e5 + 5;

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

struct Query {
  int l, r, idx;
  Query() = default;
  Query(int l, int r, int i) : l(l), r(r), idx(i) {}
  bool operator<(const Query& rhs) const {
    if (pos[l] != pos[rhs.l])
      return pos[l] < pos[rhs.l];
    return r > rhs.r;
  }
} query[N];

stack<int> stk;

struct Link_t {
  int _prev, _next;
  Link_t() = default;
  Link_t(int l, int r) : _prev(l), _next(r) {}
  inline int& prev() { return _prev; }
  inline int& next() { return _next; }
} Link[N];

inline long long Del(int p) {
  long long cur = 0;
  if (Link[p].prev() != 0 && Link[p].next() != 0)
    cur += abs(refer[Link[p].prev()] - refer[Link[p].next()]);
  if (Link[p].prev() != 0)
    cur -= abs(refer[p] - refer[Link[p].prev()]);
  if (Link[p].next() != 0)
    cur -= abs(refer[p] - refer[Link[p].next()]);
  
  stk.push(p);
  Link[Link[p].prev()].next() = Link[p].next();
  Link[Link[p].next()].prev() = Link[p].prev();
  
  return cur;
}

inline void Undo() {
  int p = stk.top();
  stk.pop();
  Link[Link[p].prev()].next() = p;
  Link[Link[p].next()].prev() = p;
}

int main() {
  // cin >> n >> m;
  read(n, m);
  
  for (int i = 1; i <= n; i++) {
    // cin >> a[i];
    read(a[i]);
    refer[a[i]] = i;
  }
  
  for (int i = 1; i <= n; i++) {
    Link[i].prev() = i - 1;
    Link[i].next() = i + 1;
  }
  Link[n].next() = 0;
  
  for (int i = 1; i <= m; i++) {
    // cin >> query[i].l >> query[i].r;
    read(query[i].l, query[i].r);
    query[i].idx = i;
  }
  
  block = sqrt(n);
  num = (n + block - 1) / block;
  
  for (int i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = min(n, i * block);
    
    for (int j = l[i]; j <= r[i]; j++)
      pos[j] = i;
  }
  
  sort(query + 1, query + m + 1);
  
  int L = 1, R = n, lst_block = 1;
  long long tmp = 0, cur = 0;
  
  for (int i = 2; i <= n; i++) {
    cur += abs(refer[i] - refer[i - 1]);
  }
  
  tmp = cur;
  
  for (int i = 1; i <= m; i++) {
    auto&& [ql, qr, idx] = query[i];
    
    if (pos[ql] != lst_block) {
      while (!stk.empty()) Undo();
      while (L < l[pos[ql]]) cur += Del(a[L++]);
      tmp = cur;
      R = n;
      lst_block = pos[ql];
      while (!stk.empty()) stk.pop();
    }
    
    while (R > qr) tmp += Del(a[R--]);
    
    long long _tmp = tmp, _L = L;
    while (_L < ql) _tmp += Del(a[_L++]);
    while (_L > L) Undo(), _L--;
    
    ans[idx] = _tmp;
  }
  
  for (int i = 1; i <= m; i++) {
    // cout << ans[i] << "\n";
    write(ans[i]);
  }
  
  return 0;
}

树上莫队

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

  • 直链：对应的括号序列的区间为 inu∼invin_u \sim in_v，中间若同一个节点出现两次，则正负抵消，因为这样的节点一定不在 u→vu \to v 的路径上。

  • 折链：用树剖的思想，将 u→vu \to v 转化为 u→LCA(u,v)u \to \mathrm{LCA}(u, v) 和 v→LCA(u,v)v \to \mathrm{LCA}(u, v)，这样就得到了两条直链，直接维护即可。

P4074 【WC2013】 糖果公园

模板题。

#include <bits/stdc++.h>

using namespace std;

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

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

inline void Dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    seq[++cnt] = u;
    in[u] = cnt;
    jmp[u][0] = fa;
    
    for (int k = 1; k < K; k++)
        jmp[u][k] = jmp[jmp[u][k - 1]][k - 1];
    
    for (auto v : adj[u]) {
        if (v == fa) continue;
        Dfs(v, u);
    }
    
    seq[++cnt] = u;
    out[u] = cnt;
}

inline int GetLCA(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    
    for (int k = K - 1; k >= 0; k--) {
        if (dep[jmp[v][k]] >= dep[u])
            v = jmp[v][k];
    }
    
    if (u == v)
        return u;
    
    for (int k = K - 1; k >= 0; k--) {
        if (jmp[u][k] != jmp[v][k])
            tie(u, v) = tie(jmp[u][k], jmp[v][k]);
    }
    
    return jmp[u][0];
}

inline void Chg(int pos) {
    if (f[pos]) {
        cur -= (long long) v[c[pos]] * w[tot[c[pos]]];
        tot[c[pos]]--;
    } else {
        tot[c[pos]]++;
        cur += (long long) v[c[pos]] * w[tot[c[pos]]];
    }
    f[pos] ^= 1;
}

inline void Upd(int x, int t) {
    if (f[x]) {
        Chg(x);
        c[x] = t;
        Chg(x);
    } else {
        c[x] = t;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // freopen("P4074_4.in", "r", stdin);
    
    cin >> n >> m >> q;
    
    for (int i = 1; i <= m; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        lst[i] = c[i];
    }
    
    Dfs(1, 0);
    
    memset(ans, -1, sizeof(ans));
    for (int i = 1; i <= q; i++) {
        int typ, x, y;
        cin >> typ >> x >> y;
        
        if (typ == 0) {
            modify.push_back(tuple(x, lst[x], y, i));
            lst[x] = y;
        } else if (typ == 1) {
            if (in[x] > in[y])
                swap(x, y);
            query.push_back(tuple(GetLCA(x, y) == x ? in[x] : out[x], in[y], i, i));
        }
    }
    
    block = pow(2 * n, 2.0 / 3);
    num = (2 * n + block - 1) / block;
    
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * block + 1;
        r[i] = min(2 * n, i * block);
        
        for (int j = l[i]; j <= r[i]; j++)
            pos[j] = i;
    }
    
    sort(query.begin(), query.end(), [&] (auto a, auto b) {
        if (pos[get<0>(a)] != pos[get<0>(b)])
            return pos[get<0>(a)] < pos[get<0>(b)];
        if (pos[get<1>(a)] != pos[get<1>(b)])
            return pos[get<1>(a)] < pos[get<1>(b)];
        return get<2>(a) < get<2>(b);
    });
    // sort(modify.begin(), modify.end(), [&] (auto a, auto b) {
    //     return get<3>(a) < get<3>(b);
    // });
    
    int L = 1, R = 0, T = -1;
    
    for (int i = 0; i < (int) query.size(); i++) {
        auto&& [ql, qr, idx, _] = query[i];
        
        while (!modify.empty() && T + 1 < (int) modify.size() && get<3>(modify[T + 1]) < idx) {
            T++;
            Upd(get<0>(modify[T]), get<2>(modify[T]));
        }
        while (!modify.empty() && T >= 0 && get<3>(modify[T]) > idx) {
            Upd(get<0>(modify[T]), get<1>(modify[T]));
            T--;
        }
        
        while (L > ql) Chg(seq[--L]);
        while (L < ql) Chg(seq[L++]);
        while (R > qr) Chg(seq[R--]);
        while (R < qr) Chg(seq[++R]);
        
        int x = seq[ql], y = seq[qr];
        int LCA = GetLCA(x, y);
        
        if (x != LCA && y != LCA) {
            Chg(LCA);
            ans[idx] = cur;
            Chg(LCA);
        } else {
            ans[idx] = cur;
        }
    }
    
    for (int i = 1; i <= q; i++) {
        if (ans[i] == -1) continue;
        cout << ans[i] << "\n";
    }
    
    return 0;
}

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

struct Query {
  int ql, qr, f, idx;
  bool operator<(const Query& rhs) const {
    if (pos[ql] != pos[rhs.ql])
      return pos[ql] < pos[rhs.ql];
    return qr < rhs.qr;
  }
};
vector<Query> query;

inline void Dfs(int u, int father) {
  dep[u] = dep[father] + 1;
  jmp[u][0] = father;
  siz[u] = 1;
  dfn[u] = ++t;
  for (int k = 1; k < K; k++)
    jmp[u][k] = jmp[jmp[u][k - 1]][k - 1];
  
  for (auto&& v : adj[u]) {
    if (v == father) continue;
    Dfs(v, u);
    siz[u] += siz[v];
  }
}

inline int GetKth(int u, int kth) {
  for (int k = K - 1; k >= 0; k--) {
    if (kth >> k & 1)
      u = jmp[u][k];
  }
  return u;
}

inline vector<pair<int, int>> GetRanges(int u, int root) {
  vector<pair<int, int>> ranges;
  if (u == root) {
    ranges.push_back(pair(1, t));
  } else if (dfn[root] >= dfn[u] && dfn[root] <= dfn[u] + siz[u] - 1) {
    int kth = GetKth(root, dep[root] - dep[u] - 1);
    if (dfn[kth] - 1 >= 1)
      ranges.push_back(pair(1, dfn[kth] - 1));
    if (dfn[kth] + siz[kth] <= t)
      ranges.push_back(pair(dfn[kth] + siz[kth], t));
  } else {
    ranges.push_back(pair(dfn[u], dfn[u] + siz[u] - 1));
  }
  
  return ranges;
}

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

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n >> m;
  
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    vars.push_back(a[i]);
  }
  
  sort(vars.begin(), vars.end());
  vars.erase(unique(vars.begin(), vars.end()), vars.end());
  
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  Dfs(1, 0);
  
  for (int i = 1; i <= n; i++) {
    rf[dfn[i]] = (int) (lower_bound(vars.begin(), vars.end(), a[i]) - vars.begin() + 1);
  }
  
  memset(ans, -1, sizeof(ans));
  
  int root = 1;
  for (int i = 1; i <= m; i++) {
    int tp, x, y;
    cin >> tp;
    
    if (tp == 1) {
      cin >> x;
      root = x;
    } else {
      cin >> x >> y;
      auto a = GetRanges(x, root), b = GetRanges(y, root);
      
      ans[i] = 0;
      for (auto&& va : a) {
        for (auto&& vb : b) {
          query.push_back({va.second, vb.second, 1, i});
          query.push_back({va.first - 1, vb.second, -1, i});
          query.push_back({va.second, vb.first - 1, -1, i});
          query.push_back({va.first - 1, vb.first - 1, 1, i});
        }
      }
    }
  }
  
  for (auto&& [ql, qr, f, idx] : query) {
    if (ql > qr) swap(ql, qr);
  }
  
  block = sqrt(n);
  num = (n + block - 1) / block;
  
  for (int i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = min(t, i * block);
    
    for (int j = l[i]; j <= r[i]; j++)
      pos[j] = i;
  }
  
  sort(query.begin(), query.end());
  
  int L = 0, R = 0;
  for (auto&& [ql, qr, f, idx] : query) {
    while (L < ql) UpdL(rf[++L], 1);
    while (L > ql) UpdL(rf[L--], -1);
    while (R < qr) UpdR(rf[++R], 1);
    while (R > qr) UpdR(rf[R--], -1);
    
    ans[idx] += cur * f;
  }
  
  for (int i = 1; i <= m; i++) {
    if (ans[i] == -1) continue;
    cout << ans[i] << "\n";
  }
  
  return 0;
}

P5268 【SNOI2017】 一个简单的询问

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

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 5e4 + 5;

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

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

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  cin >> n;
  
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    
    query.push_back(tuple(r1, r2, 1, i));
    query.push_back(tuple(l1 - 1, r2, -1, i));
    query.push_back(tuple(r1, l2 - 1, -1, i));
    query.push_back(tuple(l1 - 1, l2 - 1, 1, i));
  }
  
  for (auto&& [ql, qr, f, idx] : query) {
    if (ql > qr) swap(ql, qr);
  }
  
  block = sqrt(n);
  num = (n + block - 1) / block;
  
  for (int i = 1; i <= num; i++) {
    l[i] = (i - 1) * block + 1;
    r[i] = i * block;
    
    for (int j = l[i]; j <= r[i]; j++)
      pos[j] = i;
  }
  
  sort(query.begin(), query.end(), [&] (auto a, auto b) -> bool {
    if (pos[get<0>(a)] != pos[get<0>(b)])
      return pos[get<0>(a)] < pos[get<0>(b)];
    if (pos[get<0>(a)] & 1)
      return get<1>(a) < get<1>(b);
    return get<1>(a) > get<1>(b);
  });
  
  int L = 0, R = 0;
  for (auto&& [ql, qr, f, idx] : query) {
    while (L < ql) UpdL(a[++L], 1);
    while (L > ql) UpdL(a[L--], -1);
    while (R < qr) UpdR(a[++R], 1);
    while (R > qr) UpdR(a[R--], -1);
    
    ans[idx] += f * cur;
  }
  
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << "\n";
  }
  
  return 0;
}

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...