原题目链接 Jumping Through the Array ，看题解才做出来，用到 Split-Rebuild 的方法，感觉挺巧妙的。虽然 Codeforces 有题解，但是仍有很多细节没写清楚，要慢慢消化，这里对其添加一些注解。
一、题意有一个长度为 的数组 ，和一个长度为 的排列 。其中 中都是整数， 是由 1 到 这 个自然数组成的排列。现对 和 进行如下 3 种类型的操作：
- 给出 和 ，输出数组 上 区段上数值的和：
- 给出 和 ，对于 可连通的 都要给 加 。与 连通是这样定义的：给定入口 ，可跳转到 ，再从 ，可跳转到 ，... ，从而产生一个连通集合， ，如果 在这个集合里面，就称 与 可连通。
- 给出 和 ，交换 和 。在这之后，操作 2 都是根据更新后的排列 来判断 和 是否连通。
最终结果是对比操作 1 所输出的和是否正确。
二、题解官方题解的核心是给定一个值 ，然后把数组 与排列 分成若干块，限制每块长度 ，同时设法以块为单位进行操作。因为每块长度限制在 内，所以块的数目 ，每次操作也只需要处理 个块，从而使每次操作的复杂度降至 。
关键就是如何实现每次操作都以块为单位。
对于数组 ，只需要按顺序地每 个数为划分一块，剩余的单独划为一块。用一个数组 记录划分出来的各个块，其中，
然后用一个数组 来记录前 个 的和，即，
如此，对于操作 1 ，可通过 求出，其中 。借助 可预先知道前 个 的和，不用重复计算。而剩余的再单独求和，需要求和的数 个，因此操作维持在以块大小为单位进行。具体地，
然而还要考虑操作 2 和操作 3 带来的变化，才能完整地求出 。
对于操作 2 和操作 3 ，涉及到排列 的，则有点复杂。
根据排列的特性，操作 2 中所描述的连通方式，实际上会得到从 出发，沿着一条简单路径回到 的圈。同时整个排列 将会被刚好地划分为若干个圈，例如，
对于 ： 1 3 4 2 10 9 6 7 5 8 17 14 18 16 13 19 12 11 20 15
| [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] | [13] | [14] | [15] | [16] | [17] | [18] | [19] | [20] |
| 1 | 3 | 4 | 2 | 10 | 9 | 6 | 7 | 5 | 8 | 17 | 14 | 18 | 16 | 13 | 19 | 12 | 11 | 20 | 15 |
所包含的圈有
- 1
- 2 3 4
- 5 10 8 7 6 9
- 11 17 12 14 16 19 20 15 13 18
这就是官方题解里没有详细描述的 cycle ，因为没有详细描述，所以之后提到对 cycle 划分成 cycle block 就比较让人难以明白具体是怎么操作。
首先，根据 cycle 的长度，把 cycle 分为两类，
- 如果圈的长度 ，则称为短类型 cycle ，如上面例子的 1 和 2 3 4
- 如果圈的长度 ，则称为长类型 cycle ，如上面例子的 5 10 8 7 6 9
对于短类型 cycle ，因为其长度 ，所以不需要特殊的处理，任何操作都只需要直接历遍 cycle 上的各个点。例如对于操作 2 ，可以直接历遍圈上的每个 对数组 进行更新 。
对于长类型 cycle ，根据以块大小为单位操作的原则，需要对圈进行分块。分块的长度不需要固定为 ，只需要满足在 的范围内就行。初始时可按顺序每 个点分成一个 cycle block ，有剩余的可以合并到上一个 cycle block 上。如果用数组 来记录所有的 cycle block，上面例子初始时将记录下如下的 cycle block ，
：5 10 8 7 6 9
：11 17 12 14
：16 19 20 15 13 18
为了以 cycle block 为单位历遍长类型 cycle ，还需要添加从排列 的点到圈块的映射 。映射里需要包含的信息有，点在哪个一 cycle block 上，以及在 cycle block 上的哪个位置。
以 cycle block 为单位历遍长类型 cycle 时，首先取出当前 cycle block 末尾的点 ，然后通过排列 跳转到下一个点 ，然后再根据 获知其所在的 cycle block， ，该cycle block 就是要历遍的下一个 cycle block， 。如此重复，可历遍整个长类型 cycle 。
当长类型 cycle 分块以后，对于操作 2 ，对 所连通的 增加 时，可把 暂时记在 所在组成长类型 cycle 的各个 cycle block上，从而达到以块大小为单位进行操作的目的。设记录 cycle block 上增加值的数组为 。
然而 并不能直接用于操作 1 的计算上，因为 cycle block 里面的点不是按点的序号排序的，无法得知 有多少个点在 的范围内，进而无法得知需要多少倍的 。
为此，对于操作 2 ，还需要维护一个数据结构， ，用于记录 cycle block 里点的分布情况，这是官方题解里又一个难以参透的地方。
在这里， 是一个二维数组， 表示第 个 cycle block 上有多少个点是处于前 个 array block 。在这里需要强调，第一， 是在统计点的数目，而不是计算数值求和；第二， 并不是表示第 个 array block ，而是表示前 个 array block ，即 0 至 这 个 array block 所包含的点都要考虑进去。举个例子，
对于排列 ： 5 11 6 9 7 1 2 10 3 4 8
array block 分别有，
0：1 2 3
1：4 5 6
2：7 8 9
3：10 11
cycle block 分别有，
0：1 5 7
1：2 11 8
2：10 4 9 3 6
于是 如下所示，
| 0 | 1 | 2 | 3 | ||
| 0 | 1 | 2 | 3 | 3 | |
| 1 | 1 | 1 | 2 | 3 | |
| 2 | 1 | 3 | 4 | 5 | |
其中 表示在 cycle block [1] 上有 2 个点是落在 array block [0] array block [1] array block [2]上的，分别是 2 和 8。
有了 ，则可以弥补 的不足，操作 1 中 的计算，将补充记录在各个 cycle block ，同时落在 以前 array block 上的增加值。
， ， 是 cycle block 的总数目
维护某个 cycle block 的 的时候，可历遍 cycle block 上面的每个点，统计每个 array block 上各有多少个 cycle block 上出现的点，然后再累计起来就能得到前 个 array block 有多少个点在该 cycle block 上，复杂度为，仍然满足以块大小为单位操作的范围内。
同时由于 array block 的数目约为 ， cycle block 的数目也约为 ，所以 在空间上的消耗刚好为 ，这也是巧妙的地方之一。
对于操作 3 ，根据排列的特性，如果 和 在同一个 cycle 内，则经过操作 3 以后，这个 cycle 将分为两个 cycle；如果 和 不在同一个 cycle 内，则经过操作 3 以后，原本 和 分别所在的 cycle 会连接为一个 cycle 。一般地，
对于 cycle ，
，
经过操作 3 交换 和 以后，将切分为两个 cycle ，其中一个是 后接 后面的部分，另一个是 后接 后面的部分，
而对于不同的两个 cycle ，
经过操作 3 交换 和 以后，将连接成为一个 cycle ，类似地，这将会是 后接 后面的部分，同时 后接 后面的部分，
这里存在几种可能，
- 短类型 cycle 被分成短类型 cycle
- 长类型 cycle 被分成两个短类型 cycle
- 长类型 cycle 被分成两个长类型 cycle
- 长类型 cycle 被分成一个长类型 cycle 和一个短类型 cycle
- 两个短类型 cycle 连接成一个短类型 cycle
- 两个短类型 cycle 连接成一个长类型 cycle
- 一个长类型 cycle 和一个短类型 cycle 连接成一个长类型 cycle
- 两个长类型 cycle 连接成一个长类型 cycle
这里比较难处理的是长类型 cycle 的 cycle block 。处理的时候一般来说只需要对 和 所在的 cycle block 进行处理就可以，因为只是 和 附近的连接要交换，其他的排列顺序维持不变。
例如如下排列，
| [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] | [13] | [14] | [15] | [16] | [17] | [18] | [19] | [20] |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 1 |
若原 cycle block 如下分布，
：1 2 3 4 5
：6 7 8 9 10
：11 12 13 14 15
：16 17 18 19 20
然后交换 和 以后， cycle block 的分布如下，
：1 2 3 4 5
：11 12 13 14 15
：6 7 8 18 19 20
：16 17 18 9 10
问题就是 或 处于 cycle block 的位置不确定，有可能交换拼接以后的 cycle block 的长度会不满足 ，可能会长度不足，也可能会过长。
假设有两个 block 要合并在一起，长度都在 的范围内，那么合并得到的 block 长度在 的范围内。
对于合并后长度在 范围的 block ，如果已经变成短类型 cycle ，则不再需要记录这个 cycle block 。如果仍然处于长类型 cycle 中，则需要与相邻的 cycle block 合并，使其长度保持满足 。
对于长度变为 的 block ，则是一个正常的 cycle block ，不需要处理。
对于长度变为 的 block ，如果把他按长度平分为两个 block ，可使得每个 block 长度都在 范围内。
综上，总是能让 cycle block 维持在 的长度内，这应该就是 Split-Rebuild 方法的关键所在。
至此，已确保所有操作都维持在以长度为 的块为基础上进行，每一个操作复杂度可控制在 内。剩下的就是在代码实现的时候，每一步操作都要维护好 ， ， ， 和 等等，所以有很多复杂的数组操作，在这里就不赘述，可参考代码。
三、参考代码#include四、参考测试数据#include using namespace std; const int MAXN = 200000 + 10; const int MAXQ = 200000 + 10; const int MAXBSZ = 500; int n; int bsz; int q; long long as[MAXN]; int ps[MAXN]; // array block 的数目 int nArrayBlks = 0; // 前 i 个 array block 的累积和 long long arrayBlockSums[MAXN]; // 历遍 cycle 标记已历遍 bool vis[MAXN]; // 长类型 cycle block 的数目 int nLongCycleBlks = 0; // 长类型 cycle block // 长类型 cycle block 长度至少为 MAXBSZ // 则长类型 cycle block 的数目不超过 MAXBSZ int longCycleBlocks[MAXBSZ][MAXBSZ + MAXBSZ]; // 长类型 cycle block 的长度 int longCycleBlockSzs[MAXBSZ]; // 长类型 cycle block 上的增加值 long long longCycleInc[MAXN]; // 元素映射长类型 cycle block struct RefToCycleBlock { int ptCycleBlk; //指向长类型 cycle block int cycleBlkEntr; //指向所处长类型 cycle block 里的位置 } refToCycleBlocks[MAXN]; // 映射前 i 个 array block 上的元素处于第 j 个 cycle block 的数目 // array block 的数目不会超过 MAXBSZ // 长类型 cycle block 的数目不会超过 MAXBSZ int prefsInCycleBlks[MAXBSZ][MAXBSZ]; void debugPrintInformation() { printf("array:rn"); for(int i = 0; i < n; i++) { printf("%d ", as[i]); } printf("rn"); printf("permutation:rn"); for(int i = 0; i < n; i++) { printf("%d ", ps[i]); } printf("rn"); printf("number of long cycle blocks: %drn", nLongCycleBlks); for(int i = 0; i < nLongCycleBlks; i++) { int* blk = longCycleBlocks[i]; int sz = longCycleBlockSzs[i]; if (sz > 0) { printf("block %d: ", i); for (int j = 0; j < sz; j++) { printf("%d ", blk[j]); } printf(" - inc: %lld", longCycleInc[i]); printf("rn"); } } printf("prefs:rn"); for (int i = 0; i < nLongCycleBlks; i++) { for(int j = 0; j < nArrayBlks; j++) { printf("%d ", prefsInCycleBlks[j][i]); } printf("rn"); } printf("refs:rn"); for(int i = 0; i < n; i++) { RefToCycleBlock* ref = &(refToCycleBlocks[i]); if(ref->ptCycleBlk >= 0) { printf("{%d,%d}", ref->ptCycleBlk, ref->cycleBlkEntr); } else { printf("{} "); } } printf("rn"); printf("arrayBlockSums:rn"); for(int i = 0; i < nArrayBlks; i++) { printf("%lld ", arrayBlockSums[i]); } printf("rn"); } int blockSize(int nn) { // 定义 block 的大小 // nn 取二次方根，取下界取整 int b = 1; int t = 1; while(true) { while((b + t + t) * (b + t + t) < nn) { t = t + t; } if(t == 1 && (b + t) * (b + t) > nn) { break; } else { b = b + t; t = 1; } } if(b < 2) { b = 2; } return b; } void initArrayBlkSums() { // 初始化 array block 累积值 // array block 的数目 nArrayBlks = 0; // 单个 array block 计数目，求和值 long long subBlkSum = 0; int subSz = 0; for(int i = 0; i < n; i++) { subBlkSum = subBlkSum + as[i]; subSz++; if(subSz >= bsz) { // 数满 bsz 足够一个 array block if (nArrayBlks > 0) { // 累积和值 subBlkSum += arrayBlockSums[nArrayBlks - 1]; } arrayBlockSums[nArrayBlks] = subBlkSum; nArrayBlks++; subBlkSum = 0; subSz = 0; } } if(subSz > 0) { // 最后一截 if (nArrayBlks > 0) { // 累积和值 subBlkSum += arrayBlockSums[nArrayBlks - 1]; } arrayBlockSums[nArrayBlks] = subBlkSum; nArrayBlks++; } } void initLongCycleBlock() { // 初始化长类型 cycle block // 初始化元素映射长类型 cycle block for(int i = 0; i < n; i++) { refToCycleBlocks[i].ptCycleBlk = -1; } int ptCycleBlock = 0; for(int i = 0; i < n; i++) { if(!vis[i]) { // 一个未历遍过的 cycle int k = i; vis[k] = true; int lenCycle = 1; // 历遍 cycle while(ps[k] != i) { k = ps[k]; vis[k] = true; lenCycle++; } if(lenCycle >= bsz) { // 长类型 cycle block // 添加 array block 位处当前 cycle block 的对应关系 for(int j = 0; j < nArrayBlks; j++) { prefsInCycleBlks[j][ptCycleBlock] = 0; } // 再次历遍 cycle k = i; // 新建长类型 cycle block int* blk = longCycleBlocks[ptCycleBlock]; int sz = 0; blk[sz] = k; sz++; // 元素 k 映射长类型 cycle block RefToCycleBlock* ref = &(refToCycleBlocks[k]); ref->ptCycleBlk = ptCycleBlock; ref->cycleBlkEntr = 0; // 更新 array block 位处 cycle block 统计值 int ptArrayBlock = k / bsz; prefsInCycleBlks[ptArrayBlock][ptCycleBlock]++; int cCycle = 1; // 继续再次历遍 cycle while(ps[k] != i) { k = ps[k]; // 元素 k 映射长类型 cycle block RefToCycleBlock* ref = &(refToCycleBlocks[k]); ref->ptCycleBlk = ptCycleBlock; ref->cycleBlkEntr = sz; blk[sz] = k; sz++; // 更新 array block 位处 cycle block 统计值 ptArrayBlock = k / bsz; prefsInCycleBlks[ptArrayBlock][ptCycleBlock]++; cCycle++; if(sz >= bsz && ((lenCycle - cCycle) >= bsz)) { // cycle block 大小达到 bsz 的，新开一个 cycle block // 如果最后的 cycle block 把剩下的元素在也加进来，数目不超过 2 * bsz // 则把剩下的元素在也加进最后的 cycle block longCycleBlockSzs[ptCycleBlock] = sz; ptCycleBlock++; // 开辟新的长类型 cycle block // 添加 array block 位处当前 cycle block 的对应关系 for(int j = 0; j < nArrayBlks; j++) { prefsInCycleBlks[j][ptCycleBlock] = 0; } blk = longCycleBlocks[ptCycleBlock]; sz = 0; } } // 封闭最后一个长类型 block longCycleBlockSzs[ptCycleBlock] = sz; ptCycleBlock++; } } } // 长类型 cycle block 的数目 nLongCycleBlks = ptCycleBlock; // 计算 array block 位处 cycle block 的累计值 for (int i = 0; i < nLongCycleBlks; i++) { for (int j = 1; j < nArrayBlks; j++) { prefsInCycleBlks[j][i] += prefsInCycleBlks[j-1][i]; } } // 初始化长类型 cycle block 上的增加值 for(int i = 0; i < nLongCycleBlks; i++) { longCycleInc[i] = 0; } } long long arraySumOfPreviousL(int l) { // 求前 l 个元素(包括 l )的和 if (l < 0 || l >= n) { return 0; } long long sum = 0; // l 之前完整的 array block 的数目 int nblks = l / bsz; if(nblks > 0) { // 在 l 之前有 nblks - 1 个完整的 array block // 前 nblks - 1 个完整 array block 上的累积和 sum += arrayBlockSums[nblks - 1]; // 前 nblks - 1 个完整 array block 对应在长类型 cycle block 上增加值的和 for(int i = 0; i < nLongCycleBlks; i++) { // 读取有多少个元素，在前 nblks - 1 个 array block 里面 // 而且在第 i 个长类型 cycle block 中 int pres = prefsInCycleBlks[nblks - 1][i]; // 读取第 i 个长类型 cycle block 上的增加值 long long inc = longCycleInc[i]; // 计算增加值的和 sum += (inc * ((long long)pres)); } } // 计算 l 之前，不足一个完整 array block 的部分 for(int i = nblks * bsz; i <= l; i++) { // 加上 array 的值 sum += as[i]; RefToCycleBlock* ref = &(refToCycleBlocks[i]); // 如果在长类型 cycle block 上，加上长类型 cycle block 的增加值 if(ref->ptCycleBlk != -1) { int pt = ref->ptCycleBlk; sum += longCycleInc[pt]; } } return sum; } long long answerQueryOne() { // 处理访问类型一 int l, r; scanf("%d%d", &l, &r); // 减 2 是因为要减去的是 l - 1 之前的和 long long sumL = arraySumOfPreviousL(l - 2); long long sumR = arraySumOfPreviousL(r - 1); return sumR - sumL; } void answerQueryTwo() { // 处理访问类型二 int v; long long x; scanf("%d%lld", &v, &x); v--; RefToCycleBlock* ref = &(refToCycleBlocks[v]); if(ref->ptCycleBlk == -1) { // 如果 v 不在长类型 cycle block 内 // 则直接历遍 cycle ，把 x 加到 array 上 // 同时加到 arrayBlockSum 上 long long arrayBlockSumIncs[MAXBSZ]; for(int i = 0; i < nArrayBlks; i++) { arrayBlockSumIncs[i] = 0; } int k = v; as[k] += x; // 指向 k 所在的 array block int ptArrayBlock = k / bsz; // 计算统计值 arrayBlockSumIncs[ptArrayBlock] += x; while(ps[k] != v) { k = ps[k]; as[k] += x; // 指向 k 所在的 array block ptArrayBlock = k / bsz; // 计算统计值 arrayBlockSumIncs[ptArrayBlock] += x; } // 更新 arrayBlockSum arrayBlockSums[0] += arrayBlockSumIncs[0]; for (int i = 1; i < nArrayBlks; i++) { // 计算累积值 arrayBlockSumIncs[i] += arrayBlockSumIncs[i - 1]; arrayBlockSums[i] += arrayBlockSumIncs[i]; } } else { // 如果 v 在长类型 cycle block 内 // 把 x 加到长类型 cycle block 上 int k = ref->ptCycleBlk; do { longCycleInc[k] += x; int* blk = longCycleBlocks[k]; int sz = longCycleBlockSzs[k]; // 读 cycle block 最面的元素 int bck = blk[sz - 1]; // 通过 ps 指 bck 在 cycle 上的下一个元素 int nxt = ps[bck]; // 通过 nxt 找下一个长类型 cycle block RefToCycleBlock* ref2 = &(refToCycleBlocks[nxt]); k = ref2->ptCycleBlk; } while(k != ref->ptCycleBlk); } } void addLongCycleBlock(int* blk, int sz) { // 添加零散元素到长类型 cycle block int ptCycleBlock = 0; // 寻找在哪里加入新的长类型 block while(ptCycleBlock < nLongCycleBlks) { if(longCycleBlockSzs[ptCycleBlock] == 0) { break; } ptCycleBlock++; } // 在新的位置加入新的长类型 block if(ptCycleBlock >= nLongCycleBlks) { nLongCycleBlks++; // 添加 array block 位处 cycle block 数目的映射关系 for(int j = 0; j < nArrayBlks; j++) { prefsInCycleBlks[j][ptCycleBlock] = 0; } } int* blk2 = longCycleBlocks[ptCycleBlock]; for (int i = 0; i < sz; i++) { blk2[i] = blk[i]; } longCycleBlockSzs[ptCycleBlock] = sz; // 更新 longCycleInc longCycleInc[ptCycleBlock] = 0; // 更新 array block 位处 cycle block 数目的映射关系 for(int i = 0; i < sz; i++) { int k = blk[i]; int ptArrayBlock = k / bsz; // 计算统计值 prefsInCycleBlks[ptArrayBlock][ptCycleBlock]++; } for (int i = 1; i < nArrayBlks; i++) { long long acc = prefsInCycleBlks[i - 1][ptCycleBlock]; // 计算累积值 prefsInCycleBlks[i][ptCycleBlock] += acc; } // 更新 refToCycleBlocks // 更新 blk 上的元素指向新的长类型 cycle block for (int i = 0; i < sz; i++) { int a = blk[i]; RefToCycleBlock* ref = &(refToCycleBlocks[a]); ref->ptCycleBlk = ptCycleBlock; ref->cycleBlkEntr = i; } // 只有原 longCycleInc 需要转移到 arrayBlockSums ， // 才会引起 arrayBlockSums 变化，在这里一律不处理 } void transLongCycleIncToArrayBlockSum(int* blk, int sz, long long inc) { // 已知 blk 上的元素都是长类型 cycle block 上的元素， // 而且都标记增加值为 inc // 现在 blk 上的增加值都转移到 arrayBlockSums 上 long long arrayBlockSumIncs[MAXBSZ]; for (int i = 0; i < nArrayBlks; i++) { arrayBlockSumIncs[i] = 0; } for (int i = 0; i < sz; i++) { int a = blk[i]; as[a] += inc; int ptArrayBlock = a / bsz; // 统计 blk 在各 array block 上产生的增加值 arrayBlockSumIncs[ptArrayBlock] += inc; } arrayBlockSums[0] += arrayBlockSumIncs[0]; for(int i = 1; i < nArrayBlks; i++) { // 累计增加值 arrayBlockSumIncs[i] += arrayBlockSumIncs[i - 1]; // 更新 arrayBlockSums 累计增加值 arrayBlockSums[i] += arrayBlockSumIncs[i]; } } // 插入且合并到长类型 cycle block 中 void insertIntoLongCycleBlock(int* blk, int sz, long long inc, int ptCycleBlock, int offset) { // blk 是从长类型 cycle block 上抽出来的元素，或者是短类型的 cycle ， // blk 原本的长类型 cycle block 的增加值为 inc ， // 现要把 blk 上面的元素插入到 ptCycleBlock 所指向的长类型 cycle block 中 // 插入位置为 offset 前方 // blk 最终被拷贝了一份，可以调用完此方法后回收空间 // ptCycleBlock 所指向的长类型 cycle block 会被回收空间，调用完此方法后不能再用原来的 cycle block int* blk2 = longCycleBlocks[ptCycleBlock]; int sz2 = longCycleBlockSzs[ptCycleBlock]; long long inc2 = longCycleInc[ptCycleBlock]; // 保留在 ptCycleBlock 所指向的长类型 cycle block 的部分 int blk3[MAXBSZ + MAXBSZ]; int sz3 = 0; // 如果插入 blk 后，ptCycleBlock 所指向的长类型 cycle block 长度大于或等于 2 * bsz if (sz + sz2 >= bsz + bsz) { // 则分裂 cycle block // 需保证 blk 是从长类型 cycle block 中抽出来的，或者是短类型 cycle ，其长度小于 2 * bsz， // 这样分裂的 cycle block 长度必定大于或等于 bsz ，但是长度又小于 2 * bsz int mid = (sz + sz2) / 2; int pt = 0; int pt1 = 0; int pt2 = 0; for (; pt2 < offset && pt < mid; pt++, pt2++) { blk3[sz3] = blk2[pt2]; sz3++; } if (pt < mid) { // 如果运行到这里未到达中间位置，则表示已到达 offset 的位置 // 已到达 offset 的位置，转为插入 blk 的部分 for (; pt1 < sz && pt < mid; pt++, pt1++) { blk3[sz3] = blk[pt1]; sz3++; } } if (pt < mid) { // 如果运行到这里未到达中间位置，则表示 blk 的元素插入完毕 // blk 的元素插入完毕，转为插入 blk2 offset 后面的部分 for (; pt2 < sz2 && pt < mid; pt++, pt2++) { blk3[sz3] = blk2[pt2]; sz3++; } } // 运行到这里，一定到达中间位置，分裂一个新的长类型 cycle block int blk4[MAXBSZ + MAXBSZ]; int sz4 = 0; // 抽出 blk2 在 offset 前面的部分 // 如果 pt2 >= offset 则跳过 for (; pt2 < offset; pt2++) { blk4[sz4] = blk2[pt2]; sz4++; } // 插入 blk ，从 pt1 指向的位置开始 for (; pt1 < sz; pt1++) { blk4[sz4] = blk[pt1]; sz4++; } // 抽出 blk2 剩下的部分 for (; pt2 < sz2; pt2++) { blk4[sz4] = blk2[pt2]; sz4++; } // 把 blk4 加入到新的长类型 cycle block 中 // 更新 prefsInCycleBlks // 更新 refToCycleBlocks // 把标记在 longCycleInc 的增加值标为 0 ，原增加值转移到 arrayBlockSums 去 addLongCycleBlock(blk4, sz4); } else { // 否则直接插入到 ptCycleBlock 所指向的长类型 cycle block for (int i = 0; i < offset; i++) { blk3[sz3] = blk2[i]; sz3++; } for (int i = 0; i < sz; i++) { blk3[sz3] = blk[i]; sz3++; } for (int i = offset; i < sz2; i++) { blk3[sz3] = blk2[i]; sz3++; } } // 更新 longCycleBlocks 前复制 blk2; int blk5[MAXBSZ + MAXBSZ]; int sz5 = sz2; for (int i = 0; i < sz2; i++) { blk5[i] = blk2[i]; } // 更新 longCycleBlocks for (int i = 0; i < sz3; i++) { blk2[i] = blk3[i]; } longCycleBlockSzs[ptCycleBlock] = sz3; // 更新 longCycleInc // 把标记在 longCycleInc 的增加值标为 0 ，原增加值转移到 arrayBlockSums 去 longCycleInc[ptCycleBlock] = 0; // 更新 prefsInCycleBlks for(int i = 0; i < nArrayBlks; i++) { prefsInCycleBlks[i][ptCycleBlock] = 0; } for (int i = 0; i < sz3; i++) { int a = blk3[i]; int ptArrayBlock = a / bsz; // 统计数目 prefsInCycleBlks[ptArrayBlock][ptCycleBlock]++; } for(int i = 1; i < nArrayBlks; i++) { int acc = prefsInCycleBlks[i - 1][ptCycleBlock]; // 累计数目 prefsInCycleBlks[i][ptCycleBlock] += acc; } // 更新 refToCycleBlocks // 可能是从 blk 插进来的，所以要更新 for (int i = 0; i < sz3; i++) { int a = blk3[i]; RefToCycleBlock* ref = &(refToCycleBlocks[a]); ref->ptCycleBlk = ptCycleBlock; ref->cycleBlkEntr = i; } // 更新 arrayBlockSums // 无论是 blk 上的，还是 ptCycleBlock 指向的， // 都把增加值转移到 arrayBlockSums 上， // 可以统一处理 transLongCycleIncToArrayBlockSum(blk, sz, inc); transLongCycleIncToArrayBlockSum(blk5, sz5, inc2); } // 删除长类型 block void eraseLongCycleBlock(int ptCycleBlock) { // delete longCycleBlocks[ptCycleBlock]; longCycleBlockSzs[ptCycleBlock] = 0; longCycleInc[ptCycleBlock] = 0; // 更新 prefsInCycleBlks for(int i = 0; i < nArrayBlks; i++) { prefsInCycleBlks[i][ptCycleBlock] = 0; } // 需确保 ptCycleBlock 所指向的 cycle block 上的元素 // 在调用此方法之前已更新 refToCycleBlocks // 需确保 ptCycleBlock 所指向的 cycle block 上的元素 // 在调用此方法之前已更新 arrayBlockSums } void linkShortCycles(int si, int sj) { // 短类型 cycle 拼接在一起 int blk[MAXBSZ + MAXBSZ]; int sz = 0; blk[sz] = si; sz++; // 交换 si 和 sj 的下一个 int k = ps[sj]; while(k != si) { blk[sz] = k; sz++; if(k == sj) { // 交换 si 和 sj 的下一个 k = ps[si]; } else { // 正常下一个 k = ps[k]; } } if(sz >= bsz) { // 拼接在一起变成长类型 cycle // 短类型 cycle 长度都不足 bsz , 拼接在一起长度不会超过 2 * bsz, 不用拆开 addLongCycleBlock(blk, sz); } } void linkLongCycleWithShortCycle(int si, int sj) { // 设定 si 处于长类型 cycle , sj 处于短类型 cycle // 长类型 cycle 连接短类型 cycle RefToCycleBlock refSi = refToCycleBlocks[si]; int* blkSi = longCycleBlocks[refSi.ptCycleBlk]; int blkSj[MAXBSZ + MAXBSZ]; int szSj = 0; // 第一个放入 cycle 的需要是 sj 的下一个 // 将连在 si 后面 int k = ps[sj]; while(k != sj) { blkSj[szSj] = k; szSj++; if(k == sj) { // 交换 si 和 sj 的下一个 k = ps[si]; } else { // 正常下一个 k = ps[k]; } } // sj 在最后面 blkSj[szSj] = sj; szSj++; // blkSj 插入 refSi->ptCycleBlk 所指向的长类型 cycle block // 插入位置是 si 的后面 insertIntoLongCycleBlock(blkSj, szSj, 0, refSi.ptCycleBlk, refSi.cycleBlkEntr + 1); } void linkLongCycles(int si, int sj) { // 长类型 cycle 接长类型 cycle // 结果一定仍是长类型 cycle RefToCycleBlock refSi = refToCycleBlocks[si]; RefToCycleBlock refSj = refToCycleBlocks[sj]; int* blkSi = longCycleBlocks[refSi.ptCycleBlk]; int szSi = longCycleBlockSzs[refSi.ptCycleBlk]; int* blkSj = longCycleBlocks[refSj.ptCycleBlk]; int szSj = longCycleBlockSzs[refSj.ptCycleBlk]; long long incSi = longCycleInc[refSi.ptCycleBlk]; long long incSj = longCycleInc[refSj.ptCycleBlk]; // 找 blkSj 的下一个 cycle block int bck = blkSj[szSj - 1]; int nxt = ps[bck]; RefToCycleBlock* refNxt = &(refToCycleBlocks[nxt]); if(refNxt->ptCycleBlk == refSj.ptCycleBlk) { // 如果下一个 cycle block 就是 sj 所在的 block // 这表示 sj 所在的 cycle 只有单独一个长类型 cycle block // 这时只需要把 si 前面的部分连接上 sj 后面的部分 // 再拼接上 sj 前面的部分，再拼接上 si 后面的部分 // 这相当于 blkSi 和 blkSj 所有的元素都加进来了， // 那么长度必定足够 2 * bsz // 取中间位置重新分配两个 cycle block 的元素即可 int mid = (szSi + szSj) / 2; int pt = 0; int pt1 = 0; int pt2 = refSj.cycleBlkEntr + 1; int pt3 = 0; int pt4 = refSi.cycleBlkEntr + 1; int blk1[MAXBSZ + MAXBSZ]; int sz1 = 0; // 添加 si 前面的部分 for(; pt1 <= refSi.cycleBlkEntr && pt < mid; pt1++, pt++) { blk1[sz1] = blkSi[pt1]; sz1++; } if (pt < mid) { // 如果运行到这里还没到中间位置 // 则转为添加 sj 后面的部分，仍然添加到 blk1 for(; pt2 < szSj && pt < mid; pt2++, pt++) { blk1[sz1] = blkSj[pt2]; sz1++; } } if (pt < mid) { // 如果运行到这里还没到中间位置 // 则转为添加 sj 前面的部分，仍然添加到 blk1 for(; pt3 <= refSj.cycleBlkEntr && pt < mid; pt3++, pt++) { blk1[sz1] = blkSj[pt3]; sz1++; } } if (pt < mid) { // 如果运行到这里还没到中间位置 // 则转为添加 si 后面的部分，仍然添加到 blk1 for(; pt4 < szSi && pt < mid; pt4++, pt++) { blk1[sz1] = blkSi[pt4]; sz1++; } } // 运行到这里必定已到达中间位置 // 转为把元素添加到 blk2 int blk2[MAXBSZ + MAXBSZ]; int sz2 = 0; // 添加 si 前面的部分 for(; pt1 <= refSi.cycleBlkEntr; pt1++, pt++) { blk2[sz2] = blkSi[pt1]; sz2++; } // 则转为添加 sj 后面的部分 for(; pt2 < szSj; pt2++, pt++) { blk2[sz2] = blkSj[pt2]; sz2++; } // 则转为添加 sj 前面的部分 for(; pt3 <= refSj.cycleBlkEntr; pt3++, pt++) { blk2[sz2] = blkSj[pt3]; sz2++; } // 则转为添加 si 后面的部分 for(; pt4 < szSi; pt4++, pt++) { blk2[sz2] = blkSi[pt4]; sz2++; } // 分别把 blk1 和 blk2 添加到新的长类型 cycle block 上 // 后面会删除 blkSi 和 blkSj addLongCycleBlock(blk1, sz1); addLongCycleBlock(blk2, sz2); // 更新 arrayBlockSums // blkSi 和 blkSj 都要把增加值转移到 arrayBlockSums 上 transLongCycleIncToArrayBlockSum(blkSi, szSi, incSi); transLongCycleIncToArrayBlockSum(blkSj, szSj, incSj); } else { // 否则 blkSj 的下一个 cycle block 不是 sj 所在的 block // blkSj 的下一个 cycle block 一定是另一个长类型 cycle block // 新的 cycle 连接的顺序是 // si 前面的部分 // --- sj 后面的部分 // --- sj 所在的 cycle 的其他 cycle block ,之些 cycle block 之间的连接维持不变 // --- sj 前面的部分 // --- si 后面的部分 // si 所在的 cycle 的其他的 cycle block 之间的连接维持不变 // 先转移指向下一个 cycle block 的末尾 RefToCycleBlock* refCur = refNxt; int* blkCur = longCycleBlocks[refCur->ptCycleBlk]; int szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; // 考虑 si 前面的部分连接 sj 后面的部分 int blk1[MAXBSZ + MAXBSZ]; int sz1 = 0; // 抽出 si 前面的部分 for(int i = 0; i <= refSi.cycleBlkEntr; i++) { blk1[sz1] = blkSi[i]; sz1++; } int blk2[MAXBSZ + MAXBSZ]; int sz2 = 0; // 抽出 sj 后面的部分 for(int i = refSj.cycleBlkEntr + 1; i < szSj; i++) { blk2[sz2] = blkSj[i]; sz2++; } if (sz2 > 0) { // blk2 插入下一个 cycle block 前 insertIntoLongCycleBlock(blk2, sz2, incSj, refNxt->ptCycleBlk, 0); } if (sz2 > 0) { // 如果 blk2 不为空，把 blk1 插到 blk2 前 int fnt = blk2[0]; RefToCycleBlock* refFnt = &(refToCycleBlocks[fnt]); insertIntoLongCycleBlock(blk1, sz1, incSi, refFnt->ptCycleBlk, 0); } else { // blk2 为空，则直接插入到下一个 cycle block 前 insertIntoLongCycleBlock(blk1, sz1, incSi, refNxt->ptCycleBlk, 0); } // 历遍 sj 所在的 cycle 至 sj 的上一个 cycle block refCur = &(refToCycleBlocks[bck]); blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); while (refNxt->ptCycleBlk != refSj.ptCycleBlk) { refCur = refNxt; blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); } // 然后考虑 sj 前面的部分连接上 si 后面的部分 sz1 = 0; // 抽出 sj 前面的部分 for(int i = 0; i <= refSj.cycleBlkEntr; i++) { blk1[sz1] = blkSj[i]; sz1++; } sz2 = 0; // 抽出 si 后面的部分 for(int i = refSi.cycleBlkEntr + 1; i < szSi; i++) { blk2[sz2] = blkSi[i]; sz2++; } // 把 blk1 插到 sj 的上一个 cycle block 后面 // blk1 不会为空，至少有 sj 在里面 insertIntoLongCycleBlock(blk1, sz1, incSj, refCur->ptCycleBlk, szCur); // 如果 blk2 的长度已经达到 bsz , // 添加到新的 block 上, if (sz2 > 0) { // 否则把 blk2 插到 sj 后面 RefToCycleBlock* refBck = &(refToCycleBlocks[sj]); int szBck = longCycleBlockSzs[refBck->ptCycleBlk]; insertIntoLongCycleBlock(blk2, sz2, incSi, refBck->ptCycleBlk, szBck); } } // 一定把原 si 所在的 block 移除 eraseLongCycleBlock(refSi.ptCycleBlk); // 一定把原 sj 所在的 block 移除 eraseLongCycleBlock(refSj.ptCycleBlk); } void turnLongCycleBackToShort(int* blk, int sz, long long inc) { // blk 为长类型 cycle block 中抽出来的部分 // blk 上的增加值为 inc // blk 要转为短类型 cycle // 不在此更新 longCycleBlocks // 不在此更新 longCycleInc // 不在此更新 array block 位处 cycle block 的映射关系 prefsInCycleBlks // 更新 refToCycleBlocks for (int i = 0; i < sz; i++) { int a = blk[i]; // 标记已不再处于长类型 cycle block refToCycleBlocks[a].ptCycleBlk = -1; refToCycleBlocks[a].cycleBlkEntr = -1; } // 把增加值转到 arrayBlocksums 上 transLongCycleIncToArrayBlockSum(blk, sz, inc); } void breakShortCycle(int si, int sj) { // do nothing } void breakLongCycle(int si, int sj) { // si 和 sj 在同一长类型 cycle 里面 // 交换 si sj 相当于把长类型 cycle 切成两个 cycle RefToCycleBlock refSi = refToCycleBlocks[si]; RefToCycleBlock refSj = refToCycleBlocks[sj]; // 如果 si 和 sj 都在同一 cycle block 里面 if(refSi.ptCycleBlk == refSj.ptCycleBlk) { int* blk = longCycleBlocks[refSi.ptCycleBlk]; int sz = longCycleBlockSzs[refSi.ptCycleBlk]; long long inc = longCycleInc[refSi.ptCycleBlk]; int entrL = refSi.cycleBlkEntr; int entrH = refSj.cycleBlkEntr; if(entrH < entrL) { entrL = refSj.cycleBlkEntr; entrH = refSi.cycleBlkEntr; } // 指向下一个 cycle block int bck = blk[sz - 1]; int nxt = ps[bck]; RefToCycleBlock* refNxt = &(refToCycleBlocks[nxt]); // 如果下一个 block 就是 si 所在的 block, // 表示 si 和 sj 不仅在同一个 cycle block 上， // 而且所在的 cycle 只有一个 block // 把 entrH 后面的部分连接上 entrL 前面的部分处理 if(refNxt->ptCycleBlk == refSi.ptCycleBlk) { int blk3[MAXBSZ + MAXBSZ]; int sz3 = 0; // 抽出 entrH 后面的部分 for(int i = entrH + 1; i < sz; i++) { blk3[sz3] = blk[i]; sz3++; } // 抽出 entrL 前面的部分处理 for(int i = 0; i <= entrL; i++) { blk3[sz3] = blk[i]; sz3++; } // 如果拼接在一起还是长类型的 block // 添加新的 block. if(sz3 >= bsz) { addLongCycleBlock(blk3, sz3); transLongCycleIncToArrayBlockSum(blk3, sz3, inc); } else { // 如果拼接在一起不是长类型 block, // 把所有元素移出长类型 block, // 后面会删除 si 和 sj 所在的 block 的 turnLongCycleBackToShort(blk3, sz3, inc); } } else { // 如果下一个 cycle block 不是 sj 所在的 cycle block, // 下一个 cycle block 一定仍是长类型的 cycle block // 先转移指向下一个 cycle block 的末尾 RefToCycleBlock* refCur = refNxt; int* blkCur = longCycleBlocks[refCur->ptCycleBlk]; int szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; // 把 entrH 后面的部分合并到下一个 cycle block int blk3[MAXBSZ + MAXBSZ]; int sz3 = 0; // 抽出 entrH 后面的部分 for(int i = entrH + 1; i < sz; i++) { blk3[sz3] = blk[i]; sz3++; } // 把 blk3 插入下一个 cycle block 前面 insertIntoLongCycleBlock(blk3, sz3, inc, refNxt->ptCycleBlk, 0); // 历遍 cycle block 历遍到 si 的上一个 cycle block refCur = &(refToCycleBlocks[bck]); blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); while(refNxt->ptCycleBlk != refSi.ptCycleBlk) { refCur = refNxt; blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); } // 拷贝 entrL 之前的那些 sz3 = 0; for(int i = 0; i <= entrL; i++) { blk3[sz3] = blk[i]; sz3++; } // 把 blk3 插入上一个 cycle block 后面 insertIntoLongCycleBlock(blk3, sz3, inc, refCur->ptCycleBlk, szCur); } // 抽出 entrL 到 entrH 之间的部分 int blk2[MAXBSZ + MAXBSZ]; int sz2 = 0; for(int i = entrL + 1; i <= entrH; i++) { blk2[sz2] = blk[i]; sz2++; } // 如果 entrL 到 entrH 之间的部分长度达到 bsz // 抽出来添加一个新的长类型 block if(sz2 >= bsz) { addLongCycleBlock(blk2, sz2); transLongCycleIncToArrayBlockSum(blk2, sz2, inc); } else { // 如果 entrL 到 entrH 之间的部分长度不足 bsz // 都转为短类型 block turnLongCycleBackToShort(blk2, sz2, inc); } // 一定把原 si 所在的 block 移除 eraseLongCycleBlock(refSi.ptCycleBlk); } else { // si 和 sj 不在同一个 cycle block 里面 // 先处理 si 到 sj 之间的部分 int* blkSi = longCycleBlocks[refSi.ptCycleBlk]; int szSi = longCycleBlockSzs[refSi.ptCycleBlk]; int* blkSj = longCycleBlocks[refSj.ptCycleBlk]; int szSj = longCycleBlockSzs[refSj.ptCycleBlk]; long long incSi = longCycleInc[refSi.ptCycleBlk]; long long incSj = longCycleInc[refSj.ptCycleBlk]; // 抽出 si 后面的部分 int blk2[MAXBSZ + MAXBSZ]; int sz2 = 0; for(int i = refSi.cycleBlkEntr + 1; i < szSi; i++) { blk2[sz2] = blkSi[i]; sz2++; } // 抽出 sj 前面的部分 int blk3[MAXBSZ + MAXBSZ]; int sz3 = 0; for(int i = 0; i <= refSj.cycleBlkEntr; i++) { blk3[sz3] = blkSj[i]; sz3++; } // 指向下一个 block int bck = blkSi[szSi - 1]; int nxt = ps[bck]; RefToCycleBlock* refNxt = &(refToCycleBlocks[nxt]); // 如果下一个 block 就是 sj 所在的 block, // 只要把 blk3 拼接到 blk2 后面. if(refNxt->ptCycleBlk == refSj.ptCycleBlk) { // blk2 和 blk3 要拼起来长度能够达到 bsz // 则保留其长类型 cycle block 的特性 if (sz2 + sz3 >= bsz) { if (sz2 > 0) { // 因为已知总长度足够 bsz ， // 所以破例不管 blk2 长度是否足够 bsz ， // 都添加一个长类型 cycle block addLongCycleBlock(blk2, sz2); transLongCycleIncToArrayBlockSum(blk2, sz2, incSi); int bck2 = blk2[sz2 - 1]; RefToCycleBlock* ref2 = &(refToCycleBlocks[bck2]); // 把 blk3 拼接到 blk2 后面. insertIntoLongCycleBlock(blk3, sz3, incSj, ref2->ptCycleBlk, sz2); } else { // blk2 为空 // 表示 blk3 的长度达到 bsz // 把 blk3 添加为长类型 cycle block addLongCycleBlock(blk3, sz3); transLongCycleIncToArrayBlockSum(blk3, sz3, incSj); } } else { // blk2 和 blk3 要拼起来长度不足 bsz // 把元素都转为短类型 cycle turnLongCycleBackToShort(blk2, sz2, incSi); turnLongCycleBackToShort(blk3, sz3, incSj); } } else { // 如果下一个 block 不是 sj 所在的 block, // 那一定还是长类型的 block, // 先转移指向下一个 cycle block 的末尾 RefToCycleBlock* refCur = refNxt; int* blkCur = longCycleBlocks[refCur->ptCycleBlk]; int szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; // 先把 si 后面的元素合拼到下一个 block 前面 insertIntoLongCycleBlock(blk2, sz2, incSi, refNxt->ptCycleBlk, 0); // 历遍 cycle block 历遍到 sj 的上一个 cycle block refCur = &(refToCycleBlocks[bck]); blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); while(refNxt->ptCycleBlk != refSj.ptCycleBlk) { refCur = refNxt; blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); } // 合并 block insertIntoLongCycleBlock(blk3, sz3, incSj, refCur->ptCycleBlk, szCur); } / // 再处理 sj 绕回到 si 之间的部分 sz2 = 0; // 抽出 sj 后面的部分 for(int i = refSj.cycleBlkEntr + 1; i < szSj; i++) { blk2[sz2] = blkSj[i]; sz2++; } sz3 = 0; // 抽出 si 前面的部分 for(int i = 0; i <= refSi.cycleBlkEntr; i++) { blk3[sz3] = blkSi[i]; sz3++; } // 指向 blkSj 的下一个 cycle block bck = blkSj[szSj - 1]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); // 如果下一个 cycle block 就是 si 所在的 block, // 只要把 blk3 拼接到 blk2 后面. if(refNxt->ptCycleBlk == refSi.ptCycleBlk) { // blk2 和 blk3 要拼起来长度能够达到 bsz // 则保留其长类型 cycle block 的特性 if (sz2 + sz3 >= bsz) { if (sz2 > 0) { // 因为已知总长度足够 bsz ， // 所以破例不管 blk2 长度是否足够 bsz ， // 都添加一个长类型 cycle block addLongCycleBlock(blk2, sz2); transLongCycleIncToArrayBlockSum(blk2, sz2, incSj); int bck2 = blk2[sz2 - 1]; RefToCycleBlock* ref2 = &(refToCycleBlocks[bck2]); // 把 blk3 拼接到 blk2 后面. insertIntoLongCycleBlock(blk3, sz3, incSi, ref2->ptCycleBlk, sz2); } else { // blk2 为空 // 表示 blk3 的长度达到 bsz // 把 blk3 添加为长类型 cycle block addLongCycleBlock(blk3, sz3); transLongCycleIncToArrayBlockSum(blk3, sz3, incSi); } } else { // blk2 和 blk3 要拼起来长度不足 bsz // 把元素都转为短类型 cycle turnLongCycleBackToShort(blk2, sz2, incSj); turnLongCycleBackToShort(blk3, sz3, incSi); } } else { // 如果下一个 cycle block 不是 si 所在的 cycle block, // 那一定还是长类型的 block, // 先转移指向下一个 cycle block 的末尾 RefToCycleBlock* refCur = refNxt; int* blkCur = longCycleBlocks[refCur->ptCycleBlk]; int szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; // 先把 sj 后面的元素合拼到下一个 block 前面 insertIntoLongCycleBlock(blk2, sz2, incSj, refNxt->ptCycleBlk, 0); // 历遍 cycle block 历遍到 sj 的上一个 cycle block refCur = &(refToCycleBlocks[bck]); blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); while(refNxt->ptCycleBlk != refSi.ptCycleBlk) { refCur = refNxt; blkCur = longCycleBlocks[refCur->ptCycleBlk]; szCur = longCycleBlockSzs[refCur->ptCycleBlk]; bck = blkCur[szCur - 1]; nxt = ps[bck]; refNxt = &(refToCycleBlocks[nxt]); } // 合并 block insertIntoLongCycleBlock(blk3, sz3, incSi, refCur->ptCycleBlk, szCur); } // 一定把原 si 所在的 block 移除 eraseLongCycleBlock(refSi.ptCycleBlk); // 一定把原 sj 所在的 block 移除 eraseLongCycleBlock(refSj.ptCycleBlk); } } bool isInLongCycle(int si) { RefToCycleBlock* ref = &(refToCycleBlocks[si]); if(ref->ptCycleBlk >= 0) { return true; } return false; } bool isInTheSameCycle(int si, int sj) { RefToCycleBlock* ref = &(refToCycleBlocks[si]); // 如果是短类型的圈, // 直接历遍圈 if(ref->ptCycleBlk < 0) { int k = si; while(ps[k] != si) { k = ps[k]; if(k == sj) { return true; } } } else { // si 处于长类型 cycle 中 RefToCycleBlock* ref2 = &(refToCycleBlocks[sj]); if(ref2->ptCycleBlk >= 0) { // sj 也处于长类型 cycle 才有可能与 si 在同一个 cycle 中 int k = ref->ptCycleBlk; if(k == ref2->ptCycleBlk) { return true; } do { // 历遍 cycle 判断会不会到达 sj 所在的 cycle block int* blk = longCycleBlocks[k]; int sz = longCycleBlockSzs[k]; int bck = blk[sz - 1]; int nxt = ps[bck]; RefToCycleBlock* ref3 = &(refToCycleBlocks[nxt]); k = ref3->ptCycleBlk; if(k == ref2->ptCycleBlk) { return true; } } while(k != ref->ptCycleBlk); } } return false; } void answerQueryThree() { // 处理访问类型三 int si, sj; scanf("%d%d", &si, &sj); if (si != sj) { si--; sj--; bool isSiInLongCycle = isInLongCycle(si); bool isSjInLongCycle = isInLongCycle(sj); bool isSameCycle = isInTheSameCycle(si, sj); if(isSameCycle) { // 如果在同一个 cycle ,则一定是分为两个 cycle if(isSiInLongCycle) { breakLongCycle(si, sj); } else { breakShortCycle(si, sj); } } else { // 不在同一个 cycle ,则一定是连接为一个 cycle if(isSiInLongCycle && isSjInLongCycle) { linkLongCycles(si, sj); } else if(isSiInLongCycle) { linkLongCycleWithShortCycle(si, sj); } else if(isSjInLongCycle) { linkLongCycleWithShortCycle(sj, si); } else { linkShortCycles(si, sj); } } // 在排列上交换 int tmp = ps[si]; ps[si] = ps[sj]; ps[sj] = tmp; } } int main() { scanf("%d", &n); // 定义 block 的大小 bsz = blockSize(n); // printf("bsz: %drn", bsz); // array 值 for(int i = 0; i < n; i++) { scanf("%lld", as + i); } // permute 值 for(int i = 0; i < n; i++) { scanf("%d", ps + i); ps[i]--; vis[i] = false; } // 初始化 array block 累积值 initArrayBlkSums(); // printf("after initArrayBlkSumsrn"); // printf("number of array blocks: %drn", nArrayBlks); // for(int i = 0; i < nArrayBlks; i++) { // printf("%lld ", arrayBlockSums[i]); // } // printf("rn"); // 初始化长类型 cycle block initLongCycleBlock(); // printf("after initLongCycleBlockrn"); // debugPrintInformation(); scanf("%d", &q); for(int i = 0; i < q; i++) { int qtype; scanf("%d", &qtype); if(qtype == 1) { // 处理访问类型一 long long sum = answerQueryOne(); printf("%lldrn", sum); } else if(qtype == 2) { // 处理访问类型二 answerQueryTwo(); // debugPrintInformation(); } else if(qtype == 3) { // 处理访问类型三 answerQueryThree(); // debugPrintInformation(); } } return 0; }
input: 5 6 9 -5 3 0 2 3 1 5 4 6 1 1 5 2 1 1 1 1 5 3 1 5 2 1 -1 1 1 5 output: 13 16 11 input: 8 -15 52 -4 3 5 9 0 5 2 4 6 8 1 3 5 7 10 2 2 2 2 5 -1 1 1 8 1 1 5 1 5 8 3 1 6 2 1 50 1 1 8 2 6 -20 1 1 8 output: 61 45 22 461 301 input: 1 1 1 1 1 1 1 output: 1 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 4 3 1 1 5 2 1 1 1 1 5 output: 16 19 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 4 3 1 1 5 2 1 1 1 1 5 output: 16 19 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 1 3 5 6 4 8 9 7 11 12 13 14 15 16 17 18 19 20 10 8 1 1 5 3 2 3 2 1 1 1 1 5 3 5 7 2 6 1 1 1 5 1 1 6 output: 16 19 21 27 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 4 13 14 15 16 17 18 19 20 12 4 1 1 5 3 1 4 2 1 1 1 1 5 output: 16 21 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 4 13 14 15 16 17 18 19 20 12 4 1 1 5 3 1 11 2 8 1 1 1 5 output: 16 21 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 4 13 14 15 16 17 18 19 20 12 4 1 1 5 3 1 6 2 8 1 1 1 5 output: 16 21 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 4 13 14 15 16 17 18 19 20 12 4 1 1 5 3 1 7 2 8 1 1 1 5 output: 16 21 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 4 13 14 15 16 17 18 19 20 12 4 1 1 5 3 1 8 2 8 1 1 1 5 output: 16 21 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 4 13 14 15 16 17 18 19 20 12 5 1 1 5 2 8 1 3 1 7 2 8 1 1 1 5 output: 16 23 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 4 12 13 14 15 16 17 18 19 20 11 5 1 1 5 2 8 1 3 1 7 2 8 1 1 1 5 output: 16 23 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 1 6 7 8 9 10 11 5 13 14 15 16 17 18 19 20 12 5 1 1 5 2 8 1 3 8 3 2 8 1 1 1 5 output: 16 22 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 7 1 9 10 11 12 13 14 15 16 17 18 19 20 8 6 1 1 5 2 5 1 2 8 2 3 1 9 2 8 1 1 1 5 output: 16 26 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 4 6 1 1 5 2 3 1 2 8 2 3 1 3 2 3 1 1 1 5 output: 16 25 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 7 1 9 10 11 12 13 14 15 16 17 18 19 20 8 5 1 1 5 2 5 1 3 1 7 2 3 1 1 1 5 output: 16 25 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 1 8 9 10 11 12 13 14 15 16 17 18 19 20 7 5 1 1 5 2 5 1 3 2 5 2 3 1 1 1 5 output: 16 24 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 7 1 9 10 11 12 13 14 15 16 17 18 19 20 8 10 1 1 5 2 5 1 2 8 2 3 1 9 2 8 1 1 1 5 3 1 15 2 10 1 1 1 5 1 10 10 output: 16 26 26 10 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 7 1 9 10 11 12 13 14 15 16 17 18 19 20 8 7 1 1 5 2 5 1 2 8 2 3 1 9 2 8 1 1 1 5 3 15 18 output: 16 26 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 7 1 9 10 11 12 13 14 15 16 17 18 19 20 8 7 1 1 5 2 5 1 2 8 2 3 1 9 2 8 1 1 1 5 3 13 18 output: 16 26 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 7 1 9 10 11 12 13 14 15 16 17 18 19 20 8 7 1 1 5 2 5 1 2 8 2 3 1 9 2 8 1 1 1 5 3 4 11 output: 16 26 input: 20 3 -6 7 5 7 5 4 1 9 6 -6 10 7 1 -7 -3 -10 -2 -4 0 2 3 4 5 6 7 1 9 10 11 12 13 14 15 16 17 18 19 20 8 7 1 1 5 2 5 1 2 8 2 3 1 9 2 8 1 1 1 5 3 1 5 output: 16 26 input: 30 72 -60 64 -40 -37 53 -76 9 19 18 -70 -70 47 69 80 -41 -85 99 -33 -32 -83 36 16 -32 -56 -68 -2 5 -85 -75 25 8 3 4 26 5 16 17 30 22 7 18 1 21 15 13 14 24 19 11 29 9 23 12 20 2 27 28 10 6 100 2 5 19 2 1 -90 3 9 23 1 6 26 1 30 30 1 17 22 2 1 -29 1 1 4 1 5 29 3 12 29 2 30 73 2 22 -69 1 22 27 3 25 25 2 19 55 1 4 23 2 4 47 2 19 -70 2 4 62 2 22 -84 2 25 -49 1 1 15 3 28 28 3 4 7 1 2 14 3 18 21 1 11 27 1 20 29 1 28 30 3 11 13 1 3 20 1 16 20 1 6 23 3 22 22 1 18 30 3 2 25 1 18 18 1 24 27 1 9 9 1 24 24 3 14 14 3 20 26 2 12 41 1 27 30 3 21 28 1 21 28 3 8 15 3 12 28 2 17 -94 3 19 26 1 14 30 2 5 -29 3 13 30 2 25 -93 1 17 23 3 10 21 2 1 -71 2 17 -69 2 7 -98 1 26 26 3 13 30 3 19 26 3 4 20 2 4 -50 3 11 28 1 16 17 1 8 22 2 10 -79 3 8 22 1 30 30 2 25 88 2 11 4 3 30 30 2 9 23 3 17 30 2 12 -90 1 8 11 1 25 26 1 19 24 1 8 25 3 22 26 1 21 28 1 13 13 2 7 -82 3 27 28 3 13 23 3 13 27 3 1 15 1 13 23 2 5 -69 3 27 28 1 9 17 2 12 7 2 26 71 3 28 28 3 3 3 1 11 19 3 25 25 1 27 30 2 16 22 output: -569 -56 -131 -64 -824 -171 -442 -992 -976 -1705 -1041 -277 -1359 -584 -1627 -1206 19 -467 -42 -112 -238 -449 -2044 -1430 -542 -1149 -5962 -628 -1645 -1107 -2413 -7506 -3039 -502 -5146 -4591 -4019 -836 input: 100 84 -26 35 -40 34 61 92 -72 -22 79 -99 61 86 -90 90 14 43 70 -27 24 -50 27 -65 84 74 -20 54 -17 -65 67 97 42 -9 -93 93 57 60 8 -15 -29 53 -74 -65 -87 22 25 -67 -71 -14 -22 51 76 62 -86 96 -59 -25 -1 -55 -88 14 88 -5 34 91 24 -6 -17 -53 -100 62 -21 -75 51 -32 71 42 40 90 63 14 -35 34 91 70 -92 -42 -73 -35 -95 24 -79 71 22 63 62 -54 -20 -21 27 100 29 3 93 5 6 7 76 9 10 83 90 13 14 77 46 17 24 36 89 15 56 23 98 4 67 66 28 97 49 58 32 33 34 73 78 71 38 39 53 41 22 43 44 42 16 84 68 99 21 51 52 30 54 55 45 57 60 63 50 61 62 64 2 65 27 11 79 85 70 31 72 35 69 75 82 40 80 92 19 12 18 26 47 74 20 87 88 86 37 81 59 25 94 95 96 91 8 48 1 100 2 68 42 2 10 -72 2 10 -50 1 14 25 3 35 12 3 18 34 3 30 34 3 35 63 1 13 64 1 11 90 1 72 91 2 3 37 1 83 84 3 83 52 2 22 97 3 79 92 2 93 44 1 97 97 2 63 -27 3 7 15 2 40 14 1 17 33 3 44 12 1 11 89 1 62 66 2 41 -68 2 92 -98 2 48 46 1 96 98 1 83 92 3 91 80 3 50 68 1 57 90 3 61 96 2 78 93 3 87 78 1 86 86 3 28 52 2 69 68 2 22 -34 2 28 -57 2 72 -68 3 26 27 3 8 94 2 60 17 3 75 63 3 5 53 3 91 100 2 32 25 2 54 -72 1 97 99 2 95 85 2 33 -38 1 28 48 3 50 58 2 37 19 2 90 -85 1 76 97 1 98 100 2 24 -1 2 82 23 3 51 23 3 83 51 3 12 100 3 85 77 1 92 93 1 27 29 2 48 -24 1 72 84 1 53 92 1 19 69 2 49 -44 3 85 10 2 28 -83 2 67 -10 3 72 100 3 67 76 3 53 53 1 78 93 1 32 83 1 46 99 1 77 89 3 1 76 2 80 37 3 87 91 1 42 53 2 30 -13 1 2 32 3 55 81 3 93 25 1 40 61 2 63 87 3 39 49 2 13 41 3 60 76 1 1 49 3 83 50 2 43 -59 3 35 33 2 48 -14 output: 278 984 1307 300 125 -12 573 1493 303 63 -136 854 -92 148 776 1120 94 -20 50 761 1019 1626 379 728 630 380 -9 376 -184 801
