2025 Summer Day3 - Unleafy‘s Blog

Content： Data structs

Date：2025.7.19

内容

三维偏序问题
CDQ分治
整体二分
分块
莫队算法

具体内容

三维偏序问题

问题描述

给定一些三元组 $(a_i, b_i, c_i)$ ，询问对于三元组 $(a_j, b_j, c_j)$ ，有多少个三元组满足 $a_i \le a_j$ 且 $b_i \le b_j$ 且 $c_i \le c_j$ 。

首先对于这个问题，我们考虑先去重，然后排序。排序规则如下：

如果 $a_i \ne a_j$ ，则返回 $a_i < a_j$
如果 $b_i \ne b_j$ ，则返回 $b_i < b_j$
否则返回 $c_i < c_j$

这样我们就把 $a_i < a_j$ 的条件去掉了。

接下来我们考虑分治，定义函数 $solve(l, r)$ 表示当前解决到了区间 $[l, r]$ ，取其中点 $mid$ ，将原序列的问题转化为三个部分：

$j < i \le mid$ ，由 $solve(l, mid)$ 解决。
$mid < j < i$ ，由 $solve(mid + 1, r)$ 解决。
$j \le mid < i$ ，即被 $mid$ 分成了两个部分。

对于第三种情况，我们需要解决的是如下问题：

问题描述

在区间 $[l,r]$ 中，有多少对二元组 $(i, j)$ （其中 $i \ne j$ ）满足 $b_i < b_j$ 且 $c_i < c_j$ 。

可见问题转化为了二维偏序问题，用线段树解决就可以。

整体二分

普通的二分操作是直接对于每个询问二分答案，判断答案是否合法。整体二分的思路是将所有询问一起二分，根据二分的答案对询问进行分类，再逐步求解。

洛谷 P3332 题目描述

你需要维护 n 个可重整数集，集合的编号从 1 到 n。
这些集合初始都是空集，有 m 个操作：

1 l r c：表示将 c 加入到编号在 $[l,r]$ 内的集合中
2 l r c：表示查询编号在 $[l,r]$ 内的集合的并集中，第 c 大的数是多少。
注意可重集的并是不去除重复元素的，如 $\set{1,1,4} \cup \set{5,1,4}=\set{1,1,4,5,1,4}$ 。

我们还是定义 $solve(l, r, ql, qr)$ 表示当前答案区间为 $[l, r]$ ，处理的操作区间为 $[ql, qr]$ ，取答案中点 $mid$ 。将操作分为如下四类

如果当前操作是修改（ $op = 1$ ）
- 如果 $c \le mid$ ：归为 $A$ 类，由左递归处理。
如果 $c > mid$ ：归为 $B$ 类，由右递归处理，且用树状数组维护当前比 $mid$ 大的数的个数（差分）。
如果当前操作是查询（ $op = 2$ ）
- 如果 $c \le mid$ ：归为 $A$ 类，由左递归处理。
- 如果 $c > mid$ ：归为 $B$ 类，由右递归处理，并调整 $c$ 的值，以保证结果正确性。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
struct Node {
  int l, r, k;
} q[N];
int pos[N], cnt[N], a[N], ans = 0, rec[N];
int n, m;

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

void add(int x) {
  cnt[a[x]]++;
  if (cnt[a[x]] == 1) ans++;
}

void del(int x) {
  cnt[a[x]]--;
  if (cnt[a[x]] == 0) ans--;
}

int main() {
  cin >> n;

  int block = sqrt(n);

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

  cin >> m;

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

  sort(q + 1, q + m + 1, cmp);

  int L = 1, R = 0;

  for (int i = 1; i <= m; i++) {
    while (L < q[i].l) {
      del(L);
      L++;
    }
    while (R > q[i].r) {
      del(R);
      R--;
    }
    while (L > q[i].l) {
      L--;
      add(L);
    }
    while (R < q[i].r) {
      R++;
      add(R);
    }

    rec[q[i].k] = ans;
  }

  for (int i = 1; i <= m; i++) cout << rec[i] << endl;

  return 0;
}

莫队算法

莫队

莫队算法即为优美的暴力，根据分块对询问排序，然后维护双指针统计答案。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
struct Node { 
    int l, r, k;
}q[N];
int pos[N], cnt[N], a[N], ans = 0, rec[N];
int n, m;

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

void add(int x) {
    cnt[a[x]] ++;
    if(cnt[a[x]] == 1) ans ++;
}

void del(int x) {
    cnt[a[x]] --;
    if(cnt[a[x]] == 0) ans --;
}

int main() {
    cin >> n;
    
    int block = sqrt(n);
    
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        pos[i] = (i - 1) / block + 1;
    }
    
    cin >> m;
    
    for(int i = 1; i <= m; i ++) {
        cin >> q[i].l >> q[i].r;
        q[i].k = i;
    }
    
    sort(q + 1, q + m + 1, cmp);
    
    int L = 1, R = 0;
    
    for(int i = 1; i <= m; i ++) {
        while(L < q[i].l) {
            del(L);
            L ++;
        }
        while(R > q[i].r) {
            del(R);
            R --;
        }
        while(L > q[i].l) {
            L --;
            add(L);
        }
        while(R < q[i].r) {
            R ++;
            add(R);
        }
        
        rec[q[i].k] = ans;
    }
    
    for(int i = 1; i <= m; i ++) cout << rec[i] << endl;
    
    return 0;
}

带修莫队

在普通莫队的基础上维护修改操作的时间戳 $t$ ，每次移动左右端点时同时维护修改操作，根据询问的时间戳同步修改/撤销操作。

洛谷 P1903

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int a[N], ans[N], pos[N];
int L[N], R[N];
int cnt[N];

struct query {
  int L, R, time, id;
} ask[N];

struct modify {
  int pos, color, last;
} c[N];

int cntq, cntc, n, m, block, num;
int times, now;

bool cmp(query a, query b) {
  bool ret = false;

  if (pos[a.L] ^ pos[b.L]) {
    ret = pos[a.L] < pos[b.L];
  } else if (pos[a.R] ^ pos[b.R]) {
    ret = pos[a.R] < pos[b.R];
  } else {
    ret = a.time < b.time;
  }

  return ret;
}

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

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

void change() {
  int P = c[times].pos;
  cnt[a[P]]--;
  if (!cnt[a[P]]) now--;

  int COL = c[times].color;
  if (!cnt[COL]) now++;
  cnt[COL]++;
}

int main() {
  cin >> n >> m;

  block = pow(n, 2.0 / 3.0);

  num = ceil((double)n / block);

  for (int i = 1; i <= num; i++) {
    L[i] = (i - 1) * block + 1;
    R[i] = i * block;
  }

  for (int i = 1; i <= num; i++) {
    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++) {
    string opt;
    cin >> opt;

    if (opt[0] == 'Q') {
      cntq++;

      cin >> ask[cntq].L >> ask[cntq].R;

      ask[cntq].time = cntc;
      ask[cntq].id = cntq;
    } else if (opt[0] == 'R') {
      cntc++;

      cin >> c[cntc].pos >> c[cntc].color;
    }
  }

  sort(ask + 1, ask + cntq + 1, cmp);

  int left = 1, right = 0;
  times = 0;
  now = 0;

  for (int i = 1; i <= cntq; i++) {
    int ql = ask[i].L, qr = ask[i].R, qt = ask[i].time;

    while (left < ql) del(left++);
    while (left > ql) add(--left);
    while (right < qr) add(++right);
    while (right > qr) del(right--);

    while (times < qt) {
      times++;
      if (ql <= c[times].pos && c[times].pos <= qr) {
        change();
      }

      swap(a[c[times].pos], c[times].color);
    }

    while (times > qt) {
      if (ql <= c[times].pos && c[times].pos <= qr) {
        change();
      }
      swap(a[c[times].pos], c[times].color);
      times--;
    }

    ans[ask[i].id] = now;
  }

  for (int i = 1; i <= cntq; i++) {
    cout << ans[i] << endl;
  }

  return 0;
}

回滚莫队

即每次操作后都将左指针回退到分块的左端点，然后再进行下一次操作。