网站导航
> 文章列表 > SCUACM2023集训前训练-数据结构

SCUACM2023集训前训练-数据结构

网友: 文章列表 2024-03-22 04:42:57

SCUACM2023集训前训练-数据结构

文章目录

    • 引言
    • M-等价关系，并查集
    • Z-线段树模板：区间加、区间查询，两种维护方式
    • AA-lg3396-分块
    • AE-每次选两个，抛弃一个的过程，可以建模为树
    • AF-约瑟夫环结论+线段树
      • 普通线段树
      • zkw线段树
      • zkw线段树-最简版

引言

传送门

本文juejin：https://juejin.cn/post/7224886702883160120/

本文CSDN：https://blog.csdn.net/hans774882968/article/details/130312953

作者：hans774882968以及hans774882968以及hans774882968

M-等价关系，并查集

交换操作是“等价关系”的经典模型，就连LC都考过，回去看了一下才发现是同一道题……《离散数学》中等价关系的定义：

  1. 自反性：x = x
  2. 对称性：x = y => y = x
  3. 传递性：x = y, y = z => x = z

交换操作满足传递性的证明，就是找到1 2 3 -> 3 2 1的一种方式，如下：1 2 3 -> 1 3 2 -> 3 1 2 -> 3 2 1。故“可交换”是等价关系。把等价关系看成无向边，则可以得到一系列连通分量，每个连通分量的元素两两可交换，即每个连通分量内部的元素可以任意排序。最后只需要求每个连通分量下标值和p[]值的交集。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e5 + 5;int n, m, a[N], fa[N];
set<int> gi[N], ga[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int find (int x) {return x == fa[x] ? x : (fa[x] = find (fa[x]) );
}int main() {read (n, m);rep (i, 1, n) read (a[i]);rep (i, 1, n) fa[i] = i;while (m--) {int x, y;read (x, y);int fx = find (x), fy = find (y);fa[fx] = fy;}rep (i, 1, n) gi[find (i)].insert (i);rep (i, 1, n) ga[find (i)].insert (a[i]);int ans = 0;rep (i, 1, n) {int fi = find (i);if (i != fi) continue;vector<int> res;set_intersection (gi[fi].begin(), gi[fi].end(), ga[fi].begin(), ga[fi].end(),insert_iterator<vector<int>> (res, res.begin() ));ans += res.size();}printf ("%d\\n", ans);return 0;
}

Z-线段树模板：区间加、区间查询，两种维护方式

无论考虑维护前缀和还是差分数组，发现树状数组都无法优化到nlogn。但线段树有这个能力。线段树节点维护一个区间的1的个数和懒标记：

struct Node {int c, tg, len;
} nd[N << 2];

懒标记nd[x].tg表示对区间进行若干次操作后相当于区间异或nd[x].tg。那么区间查询操作就是查询nd[x].c，区间修改操作就是修改c属性nd[x].c = nd[x].len - nd[x].c。

懒标记还有一个小问题：nd[x].tg需要选取一个0和1以外的值来表示区间没有被修改过吗？不需要，因为异或的性质，区间修改两次和区间没修改过没有任何区别。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)const int N = 1e5 + 5;int n, m;struct Node {int c, tg, len;
} nd[N << 2];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}void build (int x, int l, int r) {if (l == r) {nd[x].len = 1;return;}int mid = (l + r) >> 1;build (ls (x), l, mid);build (rs (x), mid + 1, r);nd[x].len = nd[ls (x)].len + nd[rs (x)].len;
}void pushdown (int x) {nd[ls (x)].tg ^= nd[x].tg;nd[rs (x)].tg ^= nd[x].tg;if (nd[x].tg) {nd[ls (x)].c = nd[ls (x)].len - nd[ls (x)].c;nd[rs (x)].c = nd[rs (x)].len - nd[rs (x)].c;}nd[x].tg = 0;
}void pushup (int x) {nd[x].c = nd[ls (x)].c + nd[rs (x)].c;
}void mdy (int ql, int qr, int x = 1, int l = 1, int r = n) {if (ql <= l && r <= qr) {nd[x].c = nd[x].len - nd[x].c;nd[x].tg ^= 1;return;}pushdown (x);int mid = (l + r) >> 1;if (ql <= mid) mdy (ql, qr, ls (x), l, mid);if (qr > mid) mdy (ql, qr, rs (x), mid + 1, r);pushup (x);
}int qry (int ql, int qr, int x = 1, int l = 1, int r = n) {if (ql <= l && r <= qr) {return nd[x].c;}pushdown (x);int mid = (l + r) >> 1;int ans = 0;if (ql <= mid) ans += qry (ql, qr, ls (x), l, mid);if (qr > mid) ans += qry (ql, qr, rs (x), mid + 1, r);return ans;
}int main() {read (n, m);build (1, 1, n);while (m--) {int op;read (op);if (op == 0) {int l, r;read (l, r);mdy (l, r);}if (op == 1) {int l, r;read (l, r);int ans = qry (l, r);printf ("%d\\n", ans);}}return 0;
}

还有一个不需要用到nd[x].len的线段树做法：维护区间0和1的个数c0, c1，则区间异或1的操作，相当于c0, c1交换。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)const int N = 1e5 + 5;int n, m;struct Node {int c0, c1, tg;
} nd[N << 2];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}void pushdown (int x) {nd[ls (x)].tg ^= nd[x].tg;nd[rs (x)].tg ^= nd[x].tg;if (nd[x].tg) {swap (nd[ls (x)].c0, nd[ls (x)].c1);swap (nd[rs (x)].c0, nd[rs (x)].c1);}nd[x].tg = 0;
}void pushup (int x) {nd[x].c0 = nd[ls (x)].c0 + nd[rs (x)].c0;nd[x].c1 = nd[ls (x)].c1 + nd[rs (x)].c1;
}void build (int x, int l, int r) {if (l == r) {nd[x].c0 = 1;return;}int mid = (l + r) >> 1;build (ls (x), l, mid);build (rs (x), mid + 1, r);pushup (x);
}void mdy (int ql, int qr, int x = 1, int l = 1, int r = n) {if (ql <= l && r <= qr) {swap (nd[x].c0, nd[x].c1);nd[x].tg ^= 1;return;}pushdown (x);int mid = (l + r) >> 1;if (ql <= mid) mdy (ql, qr, ls (x), l, mid);if (qr > mid) mdy (ql, qr, rs (x), mid + 1, r);pushup (x);
}int qry (int ql, int qr, int x = 1, int l = 1, int r = n) {if (ql <= l && r <= qr) {return nd[x].c1;}pushdown (x);int mid = (l + r) >> 1;int ans = 0;if (ql <= mid) ans += qry (ql, qr, ls (x), l, mid);if (qr > mid) ans += qry (ql, qr, rs (x), mid + 1, r);return ans;
}int main() {read (n, m);build (1, 1, n);while (m--) {int op;read (op);if (op == 0) {int l, r;read (l, r);mdy (l, r);}if (op == 1) {int l, r;read (l, r);int ans = qry (l, r);printf ("%d\\n", ans);}}return 0;
}

AA-lg3396-分块

有两种暴力做法：

  1. 不维护数据结构，直接修改原数组。x较大时，复杂度较低。
  2. 维护sum[x][y]表示模x时y池的总和。查询O(1)但修改复杂度高。x较小时好。

我们考虑将两种做法结合起来，x较小使用做法2，否则使用做法1。这就是分块的思想。注意：需要同时维护原数组和sum[x][y]。代码很简单，就不写了。

AE-每次选两个，抛弃一个的过程，可以建模为树

这题描述了每次选两个并抛弃一个的过程。这个过程可以建模为树：每次选择就是连一次有向边，被抛弃的为儿子。知道这个模型，这题就可以秒掉了：因为没有选择上的性质，所以相当于在一个完全图中求最大生成树。代码很简单，就不写了。

AF-约瑟夫环结论+线段树

考虑一个01数组，存活的人为1，每轮要把某个1修改为0。设需要维护的全局变量now为：这一轮从第now个1所在的下标开始报数（0-indexed），根据定义，初值now = 0。并约定每一轮的操作为：先根据now求出下一轮的now1，再根据now1找到这一轮要修改为0的下标，这个下标记为idx（0-indexed）。所求即idx + 1。设这一轮要修改为0的下标是第now0个1（0-indexed）。因为下一轮比这一轮少了一个1，所以now1等于now0，所以上述约定是合理的。

举个例子：

7 4
5
9
8
5
// 5 1 4 6

a[] = 1 1 1 1 1 1 1。样例第1轮表示把a[4]修改为0，1 1 1 1 0 1 1，则now = 4, idx = 4。第2轮把a[0]修改为0，0 1 1 1 0 1 1，now = 0, idx = 0。第3轮把a[3]修改为0，0 1 1 0 0 1 1，now = 3, idx = 3。第4轮把a[5]修改为0，0 1 1 0 0 0 1，now = 3, idx = 5。

不难归纳出要进行的操作：now1 = (now + k - 1) % n, n -= 1，n表示当前所剩1的个数。因此我们需要一个数据结构，能够：

  1. 单点修改。
  2. 求出第now个1所在的下标。

在线段树上二分即可。但因为只需要单点修改，所以可以用一种码量更少的非递归线段树来实现，名为zkw线段树。zkw线段树的思想如下：把二叉树补全为满二叉树，利用这条性质：当二叉树是1-indexed，则x左右孩子可表示为x << 1, x << 1 | 1。于是走向左右孩子和走向父亲的操作都很简单。

普通线段树

注意：上述描述是0-indexed，我实现的线段树输入约定为1-indexed。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)const int N = 5e5 + 5;int n, m;int nd[N << 2];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}void pushup (int x) {nd[x] = nd[ls (x)] + nd[rs (x)];
}void build (int x, int l, int r) {if (l == r) {nd[x] = 1;return;}int mid = (l + r) >> 1;build (ls (x), l, mid);build (rs (x), mid + 1, r);pushup (x);
}int mdy (int ql, int cur = 0, int x = 1, int l = 1, int r = n) {if (l == r) {nd[x] = 0;return l;}int mid = (l + r) >> 1;int vl = nd[ls (x)];int ans;if (cur + vl >= ql) ans = mdy (ql, cur, ls (x), l, mid);else ans = mdy (ql, cur + vl, rs (x), mid + 1, r);pushup (x);return ans;
}int main() {read (n, m);build (1, 1, n);int now = 0;re_ (cas, 0, m) {int x;read (x);now = (now + x - 1) % (n - cas);int ans = mdy (now + 1);printf ("%d\\n", ans);}return 0;
}

zkw线段树

注意zkw线段树有补全为满二叉树的操作，空间要求是2的幂。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)const int N = (1 << 20) + 5;int n, m;int nd[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int main() {read (n, m);int tot = 1;for (; tot < n; tot <<= 1);re_ (i, 0, n) nd[tot + i] = 1;dwn (i, tot - 1, 1) nd[i] = nd[ls (i)] + nd[rs (i)];int now = 0;while (m--) {int x;read (x);now = (now + x - 1) % (n--);int ans = 1, cur = 0;while (ans < tot) {if (cur + nd[ls (ans)] > now) ans = ls (ans); // now + 1, so use >else cur += nd[ls (ans)], ans = rs (ans);}nd[ans] = 0;printf ("%d\\n", ans - tot + 1);do {ans >>= 1;nd[ans] = nd[ls (ans)] + nd[rs (ans)];} while (ans);}return 0;
}

zkw线段树-最简版

和上面的代码等价，只不过做了些简化。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)const int N = (1 << 20) + 5;int n, m;int nd[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int main() {read (n, m);int tot = 1;for (; tot < n; tot <<= 1);re_ (i, 0, n) nd[tot + i] = 1;dwn (i, tot - 1, 1) nd[i] = nd[ls (i)] + nd[rs (i)];int now = 0;while (m--) {int x;read (x);now = (now + x - 1) % (n--);int ans = 1, cur = 0;while (ans < tot) if (cur + nd[ans <<= 1] <= now) cur += nd[ans], ans |= 1;printf ("%d\\n", ans - tot + 1);while (ans) --nd[ans], ans >>= 1;}return 0;
}
网络标签：

相关问题