1 build
1.1 Description
从前有一个王国，里面有n 座城市，一开始两两不连通。现在国王将进行m 次命令，命令可
能有两种，一种是在u 和v 之间修建道路，另一种是询问在第u 次命令执行之后，城市v 经过任
意多条道路所能够到达的城市的数目（包括城市v）。
1.2 Input
第一行两个整数n;m，表示城市数和命令数。
接下来m 行，每行三个整数t; x; y，若t 为1 则表示为第一种命令，t 为2 则表示为第二种命
令。为了强制要求在线算法，u = x + lastans; v = y + lastans，其中lastans 为上次查询命令的
结果(若之前没有查询则为0)。
1.3 Output
对于每个查询命令，输出一行一个整数，表示查询的结果。
1.4 Sample Input
5 5
1 1 2
2 0 1
1 1 2
1 0 4
2 2 1
1.5 Sample Output
1
3
1.6 Hint
第一次命令：连接1、2 城市。
第二次命令：查询1 号城市在第0 次命令做完之后，能够到达的点数，为1。并将lastans 设
为1 。
第三次命令：连接2、3 城市。
第四次命令：连接1、5 城市。
第五次命令：查询2 号城市在第3 次命令做完之后，能够到达的点数，为3。并将lastans 设
为3 。
1.7 Note
对于30% 的数据，1 <= n;m <= 5000。
对于另外20% 的数据，对于第i 条命令，如果是查询命令，则有u = i ?? 1。
对于100% 的数据，1 <= n;m <= 100000。保证无自环，可能有重边。
可持久化并查集可以实现（然而现在并不会，所以就写主席树咯。
怎么想到主席树呢 题目说要回到以前的版本 不就是主席树的每个版本的$root$吗！
我们想要的是利用主席树实现维护$fa$数组的操作，所以叶子节点记录$fa$，每次$find$就和并查集一样了，只不过要找$fa$在树上的位置还要在树上$Query$一次，所以每次查询是$O(log_n^2)$
【注意】合并两个并查集以及查询操作和并查集一样aaa！！都是要先找到并查集的$fa$！！一直RE的元凶QAQ
然后因为主席树上其实只有叶子节点有用 所以路上的节点就可以不赋值叻
#include<bits/stdc++.h> using namespace std; int n, m; struct Node { Node *ls, *rs; int siz, fa, pos; } pool[100005*32], *tail = pool, *root[100005], *zero; Node *newnode() { Node *nd = ++ tail; nd -> ls = zero; nd -> rs = zero; nd -> fa = 0; nd -> siz = 0; nd -> pos = 0; return nd; } Node *build(int l, int r) { Node *nd = newnode(); if(l == r) { nd -> fa = l; nd -> siz = 1; nd -> pos = l; return nd; } int mid = (l + r) >> 1; nd -> ls = build(l, mid); nd -> rs = build(mid + 1, r); return nd; } Node *Query(Node *nd, int l, int r, int x) { if(l == r) return nd; int mid = (l + r) >> 1; if(x <= mid) return Query(nd -> ls, l, mid, x); else return Query(nd -> rs, mid + 1, r, x); } int findd(int opt, int a) { Node *x = Query(root[opt], 1, n, a); if(x -> fa != a) return findd(opt, x -> fa); return x -> fa; } Node *Change(Node *nd, int l, int r, int pos1, int pos2) { Node *nnd = newnode(); // nnd -> ls = nd -> ls; nnd -> rs = nd -> rs; nnd -> fa = nd -> fa; nnd -> siz = nd -> siz; nnd -> pos = nd -> pos; if(l == r) { nnd -> ls = nd -> ls; nnd -> rs = nd -> rs; nnd -> siz = nd -> siz; nnd -> pos = nd -> pos; nnd -> fa = pos2; return nnd; } int mid = (l + r) >> 1; if(pos1 <= mid) { nnd -> rs = nd -> rs; nnd -> ls = Change(nd -> ls, l, mid, pos1, pos2); } else { nnd -> ls = nd -> ls; nnd -> rs = Change(nd -> rs, mid + 1, r, pos1, pos2); } return nnd; } Node *Change2(Node *nd, int l, int r, int pos1, int d) { Node *nnd = newnode(); // nnd -> ls = nd -> ls; nnd -> rs = nd -> rs; nnd -> fa = nd -> fa; nnd -> siz = nd -> siz; nnd -> pos = nd -> pos; if(l == r) { nnd -> ls = nd -> ls; nnd -> rs = nd -> rs; nnd -> fa = nd -> fa; nnd -> siz = nd -> siz; nnd -> pos = nd -> pos; nnd -> siz += d; return nnd; } int mid = (l + r) >> 1; if(pos1 <= mid) { nnd -> rs = nd -> rs; nnd -> ls = Change2(nd -> ls, l, mid, pos1, d); } else { nnd -> ls = nd -> ls; nnd -> rs = Change2(nd -> rs, mid + 1, r, pos1, d); } return nnd; } int main() { freopen("build.in", "r", stdin); freopen("build.out", "w", stdout); scanf("%d%d", &n, &m); int ans = 0; zero = ++ tail; zero -> ls = zero, zero -> rs = zero, zero -> fa = 0, zero -> siz = 0, zero -> pos = 0; root[0] = build(1, n); for(int i = 1; i <= m; i ++) { int t, x, y; scanf("%d%d%d", &t, &x, &y); if(t == 1) { int u = ans + x, v = ans + y; int ux = findd(i-1, u), vx = findd(i-1, v);//////////////是要先找fa在fa的基础上改 Node *uu = Query(root[i-1], 1, n, ux); Node *vv = Query(root[i-1], 1, n, vx); if(uu -> pos == vv -> pos) {///////////如果已经在一起就不用改了 root[i] = root[i-1]; continue; } if(uu -> siz > vv -> siz) swap(uu, vv); root[i] = Change(root[i-1], 1, n, uu -> pos, vv -> pos); root[i] = Change2(root[i], 1, n, vv -> pos, uu -> siz); } else { int u = ans + x, v = ans + y; int f = findd(u, v); ans = Query(root[u], 1, n, f) -> siz; root[i] = root[i-1]; printf("%d\n", ans); } } return 0; }
2 distribute
2.1 Description
在城市的道路修建完毕之后，国王希望给pure 和dirty 分配这n 座城市。
他给出了这样一个方案：pure 为初始的决定者，从1 号城市开始到n 号城市顺序决定，如果
决定者决定把当前城市分配给pure，则下一座城市分配时决定者将变为dirty，反之亦然。
现在每一座城市i 有一个评定价值vi，pure 和dirty 都希望自己获得最大的收益，收益即获
得的城市价值之和。
假定两者足够聪明，最后pure 将获得多少收益？
2.2 Input
第一行一个整数n，表示城市数。
第二行n 个整数，第i 个整数表示vi。
2.3 Output
一行一个整数，表示pure 最后获得的收益。
2.4 Sample Input
5
1 5 3 2 4
2.5 Sample Output
9
2.6 Hint
城市1 ：pure 将其分配给dirty，不获得收益。
城市2 ：pure 将其分配给自己，pure 获得5 的收益。
城市3 ：dirty 将其分配给自己。
城市4 ：pure 将其分配给dirty，不获得收益。
城市5 ：pure 将其分配给自己，获得4 的收益。
2.7 Note
对于30% 的数据，n <= 20；
对于50% 的数据，n <= 1000；
对于70% 的数据，n <= 10000；
对于100% 的数据，1 <= n; vi <= 100000。
一道很巧妙的DP叻，夸夸$Ru笨$！！
懒了。感觉开三维好理解啊。
#include<bits/stdc++.h> #define LL long long using namespace std; int n, v[100005]; LL pre[100005], dp[100005][2][2]; int main() { freopen("distribute.in", "r", stdin); freopen("distribute.out", "w", stdout); scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d", &v[i]), pre[i] = pre[i-1] + v[i]; for(int i = n; i >= 1; i --) { for(int now = 0; now <= 1; now ++) { dp[i][now][1] = pre[n] - pre[i-1] - max(dp[i+1][now ^ 1][1], dp[i+1][now ^ 1][0]); dp[i][now][0] = max(dp[i+1][now][0], dp[i+1][now][1]); } } printf("%lld", max(dp[1][0][1], dp[1][0][0])); return 0; }
3 find
3.1 Description
然而友善的pure 和dirty 还是决定共同管理城市。现在他们拥有n 座城市，城市与城市之
间建好了m 条无向边。
他们所面临的第一个任务，就是找出所有的“圆边”。一条边被称为圆边，当且仅当存在且仅
存在一个简单环包含这条边。简单环指每个点最多只能经过一次的环。
3.2 Input
第一行两个整数n;m，表示城市数和边数。
第2 行至第m + 1 行，每行两个整数a; b，第i + 1 行表示第i 条边连接a; b 两座城市。
3.3 Output
第一行一个整数，表示圆边数目ans。
接下来一行ans 个整数，表示这些圆边的标号，按从小到大的顺序输出。
3.4 Sample Input1
5 6
1 2
2 3
3 4
4 5
1 4
3 5
3.5 Sample Output1
0
3.6 Sample Input2
5 6
1 2
2 3
3 4
4 5
1 3
3 5
3.7 Sample Output1
6
1 2 3 4 5 6
3.8 Note
对于10% 的数据，n <= 6；
对于30% 的数据，n;m <= 5000；
对于另外20% 的数据，m = n + 1，且保证图连通。
对于100% 的数据，1 <= n;m <= 100000，保证无重边无自环。
分析一下题目，发现题目要求的其实是在求点双联通分量中边数等于点数的所有边。因为我们的目的是把所有环分离出来判断它们的性质，而点双才是环的叠加，边双中可能会又环的重复，如下图：
如果是找边双，这个图就会整个被放入联通块中，就不符合我们边等于点的判断条件，而我们找点双，从中间这个点开始分成两个点双，两边各自满足边数等于点数就可以判断叻。
【注意】这个不是以前单纯的有向图联通块aaa！！！存的边的数组都要开两倍！！！！！改了一下午QAQAQAQ
可以当割点和点双的模板叻
//点双联通分量模板（割点模板） #include<bits/stdc++.h> using namespace std; int n, m; void read(int &x) { x = 0; char ch = getchar(); while(ch > ‘9‘ || ch < ‘0‘) ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); } } struct Node { int u, tov, nex; Node(int u = 0, int tov = 0, int nex = 0) : u(u), tov(tov), nex(nex) { } } Edge[200005]; int stot, h[100005]; void add(int u, int v) { Edge[++stot] = Node(u, v, h[u]); h[u] = stot; } vector < int > QAQ[100005]; int num[100005], color[200005], dfn[100005], low[100005], ti, tp, stk[200005], cnt, cut[100005]; void tarjan(int u, int f) { dfn[u] = low[u] = ++ti; int child = 0; for(int i = h[u]; i; i = Edge[i].nex) { int v = Edge[i].tov; if(v == f) continue; if(!dfn[v]) { stk[++tp] = i;/////必须放里面避免重复入栈 child ++;/////判断根节点的不在同一点双的儿子个数 tarjan(v, u); low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]) {/////割点的判断条件 如果当前点已经是割点 那么就要取出这个已找出来的点双 cut[u] = 1; //////////cut是标记割点 此题不需要用 cnt ++; int x; do { x = stk[tp--]; if(!color[x]) { color[x] = cnt;/////某条边在哪个点双中 QAQ[cnt].push_back(x);/////点双记录边的集合 } num[cnt] ++;///////当前点双中边的数量 } while(Edge[x].u != u || Edge[x].tov != v); } } else if(dfn[v] < dfn[u]) { low[u] = min(low[u], dfn[v]); ////必须有判断条件 因为不加就可能把无向图的反向边当成返祖边 stk[++tp] = i; } } if(f == 0 && child == 1) cut[u] = 0;//////////如果是根节点割点需要特判 } int vis[100005], tmp[100005], ans[100005]; int main() { freopen("find.in", "r", stdin); freopen("find.out", "w", stdout); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++) { int a, b; read(a); read(b); add(b, a); add(a, b); } for(int i = 1; i <= n; i ++) if(!dfn[i]) tarjan(i, 0); int tot = 0; for(int i = 1; i <= cnt; i ++) { int tmp = 0;///记录点数 for(int j = 0; j < QAQ[i].size(); j ++) { int id = QAQ[i][j]; int u = Edge[id].u, v = Edge[id].tov; if(!vis[u]) vis[u] = 1, tmp ++; if(!vis[v]) vis[v] = 1, tmp ++; } if(tmp == num[i]) {/////////////只有边数等于点数时符合条件 for(int j = 0; j < QAQ[i].size(); j ++) { int id = QAQ[i][j]; ans[++tot] = ceil(1.0 * id / 2);////////////真正的边的标号 } } for(int j = 0; j < QAQ[i].size(); j ++) { int id = QAQ[i][j]; int u = Edge[id].u, v = Edge[id].tov; vis[u] = vis[v] = 0; } } printf("%d\n", tot); if(!tot) return 0; if(tot) { sort(ans + 1, ans + 1 + tot); for(int i = 1; i <= tot; i ++) printf("%d ", ans[i]); } return 0; }