引言
传送门
本文juejin:https://juejin.cn/post/7224886702883160120/
本文CSDN:https://blog.csdn.net/hans774882968/article/details/130312953
作者:hans774882968以及hans774882968以及hans774882968
M-等价关系,并查集
交换操作是“等价关系”的经典模型,就连LC都考过,回去看了一下才发现是同一道题……《离散数学》中等价关系的定义:
- 自反性:
x = x
- 对称性:
x = y => y = x
- 传递性:
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-分块
有两种暴力做法:
- 不维护数据结构,直接修改原数组。
x
较大时,复杂度较低。 - 维护
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的个数。因此我们需要一个数据结构,能够:
- 单点修改。
- 求出第
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的幂。文章来源:https://www.toymoban.com/news/detail-423066.html
#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线段树-最简版
和上面的代码等价,只不过做了些简化。文章来源地址https://www.toymoban.com/news/detail-423066.html
#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;
}
到了这里,关于SCUACM2023集训前训练-数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!