置换环建笛卡尔树：AT_wtf22Day1B
置换环建笛卡尔树：AT_wtf22Day1B
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133644610
https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_b?lang=en
置换环是用值连位
首先肯定要分成每个置换环，每个置换环操作次数只能是 （置换环性质）
我们考虑置换环任意一次操作，会划分成两个小置换环，且他们都是连续段
考虑把环拉成一条链，两个位置交换就会划分成两个子区间（头尾再重新连在一起）
为了使结果合法（这里只的是能还原成排列），我们只能在这个子区间递归下去。
我们考虑这种情况，能够巧妙利用题目=的性质。
我们可以在左右跳来跳去
考虑回之前区间的限制，似乎建笛卡尔树能很好利用这堆性质
建好之后向上必然是更小，向下必然更大。我们进行中序遍历必然可以
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-06
排列 -＞ 位置与值域相对应：1006T2
排列 -＞ 位置与值域相对应：1006T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133611553 http://47.92.197.167:5283/problem/5513 考场上转化后的是max（每个数的位置 - 其应该的位置） 但对于排列问题，此题可以直接转化为每个数之前有多少个数比他大
2026-07-07
平衡树全家桶 2
平衡树全家桶 2 笛卡尔树 仅支持静态，不支持动态 建树过程：单调栈。对于每个新加入的点 xxx 最后pop掉的点 yyy，则 yyy 是 xxx 左子树 最后pop不走的点 zzz，则 xxx 是 zzz 右子树 用于静态区间最大值之类的维护 Size Balanced Tree 树的性质：叔叔比侄子大，即： 1234size(N.left) >= size(N.right.left)size(N.left) >= size(N.right.right)size(N.right) >= size(N.left.left)size(N.right) >= s...
2023-10-24
分析性质+排列置换环+最小割：1024T4
分析性质+排列置换环+最小割：1024T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134022318 http://cplusoj.com/d/senior/p/SS231024D 相当于各选一些置换环进行一次位移 我们考虑只对A进行置换。对于一个大小>1的环，如果对其进行位移，一定可以使这些位完全不同。 因此，如果我们置换B，置换的意义是什么？是把A中自环的位置统计掉，使这些位置不同。 但如果我们再置换B，可能会和之前已经置换的A在某些地方相...
2023-11-06
排列与置换换+容斥+多项式生成函数启发式合并：[Gym-103446B]
排列与置换换+容斥+多项式生成函数启发式合并：[Gym-103446B] 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134243178 https://vjudge.net/contest/591700#problem/G 看到排列，先考虑置换换，题意转化为置换环相邻的不能再最终序列上相邻 而这个过程看起来很容斥，所以我们容斥：至少要 xxx 个相邻 我们发现每个置换环的所有边不能全部同时被选，所以我们每个置换环要分开考虑，最后再乘起来 然而这样的复杂度...
2023-09-15
笛卡尔树建树
笛卡尔树建树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906457 拿个单调队列维护 最后pop出来的就是它的左儿子 现在还在的，它是他的右儿子 1234567891011int build() { int S[N]; for(int i=1; i<=n; ++i) { while(top && T[S[top]].val < T[i].val) T[i].son[0]=S[top], -...
2023-10-25
排列置换环上构造：1025T3
排列置换环上构造：1025T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134035399 http://cplusoj.com/d/senior/p/SS231025C 排列构造的新知识：上置换环！ 我们发现朴素做法是 n2n^2n2 级别的，但数据范围希望我们是 n22\frac {n^2}2 2n2 级别的。我们发现我们暴力复制序列显得非常蠢，因为很多序列前后我们其实可以考虑合并。 至于怎么合并？我们直接维护指针。然后我们现在要“运”东西到相应...