题解 CF1093E 【Intersection of Permutations】

我永远喜欢树套树。 树状数组套权值线段树 注意到$a_i$和$b_i$都是排列，可以设`p[a[i]]=i`，这样的映射一定是一一映射。 那么对于一个询问，集合$\{a[l_a],a[l_a+1],\cdots,a[r_a]\}$与集合$\{b[l_b],b[l_b+1],\cdots,b[r_b]\}$的交集大小一定等于集合$\{p[a[l_a]],p[a[l_a+1]],\cdots,p[a[r_a]]\}$（也就是集合$\{l_a,l_a+1,\cdots,r_a\}$）与集合$\{p[b[l_b]],p[b[l_b+1]],\cdots,p[b[r_b]]\}$的交集大小。 所以我们用数据结构来维护序列$p[b[i]]$，每个询问就是在查询这个序列的第$l_b$个元素到第$r_b$个元素中，值域在$[l_a,r_a]$的元素有多少个，也就是区间上的值域数点。用树状数组维护区间，权值线段树维护值域即可。 修改也就没有任何难度了。 如果不带修改是可以直接用主席树的，时间和空间都更加优秀。 小心卡空间，我用了垃圾回收 ```cpp #include <cctype> #include <cstdio> #include <climits> #include <algorithm> #include <vector> template <typename T> inline void read(T& x) { int f = 0, c = getchar(); x = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = x * 10 + c - 48, c = getchar(); if (f) x = -x; } template <typename T, typename... Args> inline void read(T& x, Args&... args) { read(x); read(args...); } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + 48); } template <typename T> void writeln(T x) { write(x); puts(""); } template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; } template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; } const int maxn = 2e5 + 7; int lc[maxn << 7], rc[maxn << 7], sum[maxn << 7], tot; int root[maxn]; int b[maxn], p[maxn]; int n, m; std::vector<int> can; inline int newNode() { if (can.empty()) return ++tot; else { int x = can.back(); can.pop_back(); return x; } } inline void deleteNode(int x) { lc[x] = rc[x] = sum[x] = 0; can.push_back(x); } void modify(int &o, int l, int r, int pos, int d) { if (!o) o = newNode(); sum[o] += d; if (l < r) { int mid = (l + r) >> 1; if (pos <= mid) modify(lc[o], l, mid, pos, d); else modify(rc[o], mid + 1, r, pos, d); } if (!sum[o]) deleteNode(o), o = 0; } int query(int o, int lb, int rb, int l, int r) { if (!o || l > rb || r < lb) return 0; if (l <= lb && r >= rb) return sum[o]; int mid = (lb + rb) >> 1; return query(lc[o], lb, mid, l, r) + query(rc[o], mid + 1, rb, l, r); } inline void modify(int x, int v, int d) { for (; x <= n; x += x & -x) modify(root[x], 1, n, v, d); } inline int query(int l, int r, int x, int y) { int ans = 0; for (; r; r -= r & -r) ans += query(root[r], 1, n, x, y); for (--l; l; l -= l & -l) ans -= query(root[l], 1, n, x, y); return ans; } int main() { read(n, m); for (int i = 1, x; i <= n; ++i) read(x), p[x] = i; for (int i = 1; i <= n; ++i) read(b[i]), modify(i, p[b[i]], 1); while (m--) { int q; read(q); if (q == 1) { int l1, r1, l2, r2; read(l1, r1, l2, r2); writeln(query(l2, r2, l1, r1)); } else { int x, y; read(x, y); modify(x, p[b[x]], -1); modify(y, p[b[y]], -1); std::swap(b[x], b[y]); modify(x, p[b[x]], 1); modify(y, p[b[y]], 1); } } return 0; } ```