signed

QiShunwang

“诚信为本、客户至上”

辣鸡错误合集&各种奇妙♂的小技巧

2020/8/19 21:36:17   来源:

策略

  • 最后15分钟检查题目n,m之类的东西,小心暴力和正解同时打错
  • GDOI赛制:先看题并想暴力能拿多少分,看懂所有题再深入思考。
  • 再难懂 / 再不可做的题也要留出一定时间思考,不要丢了容易拿的分。
  • 看起来不可做的题一般是没发现结论,这时候多猜测,多对拍。
  • 不要死磕一种思路,想不出来可以先跳出来,看看有什么其他想法。
  • 千万不要抱着就拿这题100分就够了的心态。拿好大部分人都能拿的分才是第一要做的。
  • 尽量对拍。数据结构题一定要测极限。
  • 做比赛不要神游。
  • 一般图的题不能只对拍,因为很多情况都难随机到,要手出数据,所有题目没明说不可能的情况都要试一下,尽量兼容。
  • 遇到一套难题千万不要慌,把可能拿到的部分分列一下,把各题暴力打打,也许会有意想不到的收获。一直想题不一定能想出来,而且时间一长容易紧张。
  • 想完算法复述一下题面,看看算法靠不靠谱,有没有漏掉的关键细节。

实现

  • 高斯消元错误示范,f[j][i]f[j][i]在中途被更新了。
for(int j=i+1;j<=stm+1;j++)if(f[j][i]!=0){
			for(int z=0;z<=stm;z++){
				f[j][z]=(f[j][z]-f[i][z]*f[j][i])%mo;
			}
		}
  • C(n,m)是可以O(m),O(m),O(m)求的!

  • kth不要忘了down!

  • 二进制trie的空间上界不是nlogwn \log w。前logn\log n层最坏是填满,所以是O(2n+n(logwlogn))O(2n +n(\log w - \log n))

  • 倍增的循环顺序错了,假如树是保证fa[x]<x时答案是不会错的。(这恰恰是很多人生成树的方式)
    错误示范:

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j < 20; j++) {
			mad[i][j] = max(mad[i][j - 1], mad[g[i][j - 1]][j - 1]);
			mmi[i][j] = max(mmi[i][j - 1], mmi[g[i][j - 1]][j - 1]);
		}
	}
  • 随机字符串长度大概5000就开始卡1e9+7或998244353的哈希了。这时候就可以祭出杀手锏2+3*16配以快速加,1e5都莫得问题(目前)。(自然溢出听说会被卡)
ll mul(ll a,ll b){
	a%=mo,b%=mo;
	ll c=(long double)a*b/mo,z=a*b-c*mo;
	if (z>mo)z-=mo;
	if (z<0)z+=mo;
	return z;
}
  • 点剖老是忘记算分治中心的答案和影响,光顾着算子树答案了。

  • 可以开O2测试会不会RE!

  • 不要位移负数位,在某些环境中会RE!!!

  • 检查头文件!!!!!有时候少头文件也能正常编译!!

  • 取上整不要用(x-1)/a+1,x=0时会鬼畜。用(x+a-1)/a就好。

  • 务必测极限数据,特别是数据结构题。RE很恐怖!!经历过被卡成暴力分的绝望吗???

  • 输出优化记得判0

  • 记得判断第i为是否为0是(x&1)!=0而不是==1.

  • memcpy中的size要写成接受者的size,否则容易出现数组大小不一致导致的奇妙溢出。

  • 打错会TLE但是答案不会错的算法目前有:树链剖分(未正确划分树链),manacher(未正确维护mx)树分块(重心找错)

  • 想完算法,记得算空间,打完后用任务管理器再测一下。

  • 等比数列求和要注意公比=1的情况!!!这时候不能用一般求和公式!

  • 无向边集数组应该开两倍!!!线段树节点数应该开四倍!所有线段树数组都要!

  • std有些东西在不开O2的时候常数炒鸡大,开O2的时候就比自己写的都要快了。

  • 永远不要把除法(或mod)放在频繁使用的地方,比如循环条件.

  • 如果题目给出了精度要求,那么最好多开2到3位.

  • double x=1; int y=(int)x;这种将double转化成int的方法可能有点精度问题
    最好这样写y=round(x)

  • 二分的ans有可能是没有的,注意判断合法性

  • splay等数据结构能不写成struct就不写成struct,不然写起来很别扭。

  • splay的down可以在kth的时候完成,这样就不需要再写一个 down了。 (如果被splay的点一定是被kth出来的话)

  • 在c++中x0modk (x0<=0)等价于x0不断加k直到正好小于等于 0.

  • 实现lct的splay需要注意的一些地方:

void rotate(int x) {
	int y=fa[x],z=get(x);
	if (c[x][1-z]) fa[c[x][1-z]]=y;
	c[y][z]=c[x][1-z];
	fa[x]=fa[y];
	if (!isroot(y)/*这里容易漏掉,并不是简单判断fa为0即可*/) c[fa[y]][get(y)]=x;
	fa[y]=x;
	c[x][1-z]=y;
	update(y);
}
void downs(int x) {
	while (!isroot(x)) Q[++Q[0]]=x,x=fa[x];
	Q[++Q[0]]=x; //要补加一个
	while (Q[0]) down(Q[Q[0]--]);
}
  • 数论分块些要注意的地方
ll nn,mm;
ll calc(ll a,ll x) {
	a=min(a,x);
	ll ret=0,l=1,r;
	while (l<=a) {
		r=min(x/(x/l),a); //若a!=x,这里必须要取min
		ret=(ret+(x/l)%mo*sum(l,r)%mo)%mo;
		l=r+1;
	}
	return ret;
}
  • long long 相乘模long long,用加法代替乘法,时间换正确性。
ll mult( ll A, ll B, ll Mo ) {
	ll ret=0;
	while (B) {
		if ((B&1)>0) ret=(ret+A)%Mo;
		A=(A+A)%Mo; B=B>>1;
	}
	return ret;
}
  • zz操作: 如果记得判当前剩余数是个质数的话(当前质数大于\sqrt {剩余的数}),分解质因数的时间是稳定小于x\sqrt x的!

  • 数据结构区间tag无论是修改还是查询,只要需要update就要down,不然update就会把原tag的修改覆盖掉。

  • (dij)迪杰特斯拉求最短路若原图不连通则算法停止条件不是i< n,而是堆中点数是否为0.

  • 注意爆栈问题,保守起见尽量不要有超过1w层的递归 (jzoj上好像15w才会爆?而且测试测不出来!?)。

  • 遇到头疼的数位DP时,有两种解决办法:
    1.直接枚举两个相关状态,并将所有不合法转移判掉.
    2.枚举之前的状态与当前数,生成当前状态.

  • struct重载运算符的姿势

struct line {
	ll l,r,no;
	friend bool operator<(line x,line y){
		return x.r<y.r || x.r==y.r && x.l>y.l;
	}
	
	line(ll l,ll r,ll no) 
	{this->l=l, this->r=r, this->no=no;}
	line() {l=r=no=0;}
} a[N],b[N];
//高精度数直接取的姿势,**不开O2慎用!** 
struct _int {
	ll a[Mx];
	ll * operator[](ll i) {return a[i];}
} n;

struct mat{
	int h[100][100];
	int * operator[](int x) {return h[x];}
} a;

  • 线段树上第k小只需要一个log,不需要二分!!!!

double
4 byte15位有效数字 max = 1e308
long double
8 byte 18位有效数字 max = 1e4000

  • c++自带log的常数很大!可以预处理数组!

  • 快速幂尽量写非递归版的

ll pow(ll x,ll y){
	ll t;
	for(t=1; y; y>>=1,x=x*x%mo) if(y&1) t=t*x%mo;
	return t;
}
  • 用define打的min千万不要放时间长的函数进去!
错误示范
    return min( query(x*2,l,mid,tl,tr),query(x*2+1,mid+1,r,tl,tr));
正确姿势
    int fm1=query(x*2,l,mid,tl,tr),fm2=query(x*2+1,mid+1,r,tl,tr);
    return min( fm1,fm2 );
  • 常用的编译参数
    devcpp用法:工具-编译选项-编译时加入以下命令
-Wl,--stack=167772160 开栈
-O2 你懂得

两个加起来并排打,也就是(不含引号)
"-Wl,--stack=167772160 -O2"

-Wall 编译选项可以规避很多小错误。
  • 函数,变量名不要用hash,next,y0,x0,time等可能引起编译错误的变量。

  • 如果ans是个ll,n,q是int,那么
    ans+(ll)(n-1)*Q 不会爆炸
    ans+(n-1)*Q 会
    因为当int与ll运算时,int才会自动转ll,而这个是(n-1)先与Q运算。

  • 如何生成n个互异随机数:< algotihm > random_shuffle打乱数组

  • ll取模黑科技,先用longdouble计算d=ab/mo(可能会有较小误差),再用ll计算ab-d
    乘法存不下会溢出,但是63位之前的是安全的,正好符合要求,再调整符号位即可。
    注意x,y必须先对mo取模。

ll mul(ll x, ll y,ll mo) {
	x%=mo,y%=mo; //这样才能保证z在ll范围之内
    ll z=(ld) x * y / mo;
	z = x * y - z * mo;
    if(z < 0) z += mo; else if(z > mo) z -= mo;
    return z;
}
  • fft的时候注意数组要开大一些,只多开5~10是不够的,比如说2^20是一百万多5000左右。

  • o2对加减法优化特别好,对/与%不友善。

  • 复数dft的单位根必须每一次去算,不能算一个主根然后一次次乘,这样会损失很大精度


思路

  • 求欧拉回路:充要条件是度数为偶数,所以可以每次删掉一个环。
  • 次幂与上升/下降幂的转化,组合意义理解。nm=i=0mS2(m,i)ni=i=0mS2(m,i)ni(1)min^m=\sum_{i=0}^m S2(m,i)n^{\underline{i}}=\sum_{i=0}^m S2(m,i)n^{\overline{i}}(-1)^{m-i}
    在这里插入图片描述
  • 求逆矩阵:将一个单位矩阵放在右侧同步变换,然后将原矩阵消成单位矩阵。
void gauss() {
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) if (a[j][i]) {
			swap(a[i], a[j]); break;
		}
		if (abs(a[i][i]) <= 1e-8) {
			printf("no inverse!"); exit(0);
		}
		for(int j = 1; j <= n; j++) if (i != j && abs(a[j][i]) >= 1e-8) {
			db rat = a[i][i] / a[j][i];
			for(int z = 1; z <= n + n; z++) {
				a[j][z] = a[j][z] * rat - a[i][z];
			}
		}
	}
	for(int i = 1; i <= n; i++) if (a[i][i] != 1) {
		db rat = 1.0 / a[i][i];
		for(int j = 1; j <= n + n; j++) a[i][j] *= rat;
	}
}

  • 两个串的无限串相同,当且仅当其最小周期循环重构。证明暂缺。

  • 对于多重组合数也有卢卡斯定理。

  • minmax容斥是一种子集容斥。将难以整体计数的问题转化为子集计数的问题往往有奇效。
    max(S)=TSmax(T)(1)T1max(S)=\sum_{T属于S}max(T)(-1)^{|T|-1},minmax可以互换。

  • gcd(x,y)的复杂度是O(logxloggcd(x,y))O(\log x - \log gcd(x,y))

  • dinic跑二分图等特殊图有奇效。(记得所有网络流都需要当前弧优化)
    在这里插入图片描述

  • 最优化问题可以允许不合法的贡献,只要他一定不比答案优。

  • momo1=0mo^{mo-1}=0,直接对指数取模mo-1后会算成mo0=1mo^0=1
    即当需要对指数取模mo-1的时候,注意需要保证(,mo)=1(底数,mo)=1

  • 平面图欧拉公式:点数+面数=边数+2;V+F=E+2V+F=E+2

  • 树上,某条直径的两个端点之一必定是距离点x最远的点之一。

  • 将一个数拆分成若干个不同的斐波那契数之和,求方案数。
    https://www.luogu.com.cn/problemnew/solution/P4133
    结论1:一个数可以被唯一拆分成不相邻的斐波那契数之和
    结论2:任意一个fib拆分都可以由上述拆分由始至终不重复的拆分得来。

  • 点分树合并问题:点分树可以理解为点的先后选取偏序。如何计算点分树数量?考虑添加一条边合并两棵树后,点分树的数量,两边内部的偏序已经确定,需要确定的即为新边的两个端点分别到其点分树根的点的顺序。采用dp+挡板解决。https://ac.nowcoder.com/discuss/363557?type=101&order=0&pos=1&page=1

  • (x-y)/c=x/c-y/c-(x%c<y%c),下取整。前提:x>=0,y>=0,x-y>=0.所以可以用一维偏序来拆开下取整求和问题.

  • gcd的乘积可以先拆质因子,然后转化成指数上的min.

  • 树剖的那个线段树,本质还是dfs序,所以能顺带维护子树和。

  • 括号序列,第一个+,第二个-,只能查祖孙路径。

  • μ(lcm(a,b))=μ(a)μ(b)μ(gcd(a,b))\mu(lcm(a,b))=\mu(a)\mu(b)\mu(gcd(a,b)),若a,b中有平方因子显然正确,否则依然可根据函数值仅有1与-1推知正确。

  • 有一种费用流叫做一个个流量流的费用流。并且容易证明费用流增广费用是不增的(?)。

  • 并不是只有1e1000之类的才是数位dp。

  • i2=n(2n+1)(n+1)/6\sum i^2 = n(2n + 1)(n + 1) / 6,忘记就猜!

  • 虚树中预处理通常是设g[x]表示父亲去掉x这颗子树后的信息。方便计算边上伸出来的毛。

  • 组合恒等式zi=(z1+1)iz^i=(z-1+1)^i,二项式展开后可以用于子集容斥。

  • a+b=nxayb=(xn+1yn+1)/(xy)\sum_{a+b=n}x^ay^b=(x^{n+1}-y^{n+1})/(x-y)

  • 二分图最小顶标(边两端顶点权值之和>=边权)问题=二分图最大匹配

  • 组合数求模假如素数小,那么可以使用卢卡斯+预处理加速计算~

  • 线段树区间修改最多只会走到2 log 个点,因为每层最多两个 (再多就合并了)

  • lca的查询复杂度是O(1)的 _______by RMQ&ST

  • 只带路径压缩或者带秩合并的并查集的时间复杂度其实都是均摊logn的 (但是一般卡不到),一起带才是nα(n) by 栋爷《数据结构小入门》

  • CDQ分治与整体二分的异同
    cdq分治=按(操作)时间分治。先处理前半部分修改对后半部分的影响,再两边分别分治下去。
    整体二分=同时二分所有询问的答案,将可能区间相同的询问放到一起。 枚举所有操作,先处理好每一询问判定需要的信息,再判定每一询问该被分到哪一部分。
    比如说二分第k大数为mid,先将原序列排序变为用来二分的答案序列,当前可能区间为[l,r]。 标记所有大于mid=(l+r)/2的位置,查询区间[l,r]中有多少大于mid.从而判定答案大于mid还是小于等于mid.
    记得统计在询问x之前但被分到另一区间的y操作的贡献。
    http://blog.csdn.net/jokerwyt/article/details/78482831

  • 三角形面积可以转化为叉积(axbybxay2\frac {ax*by-bx*ay} 2),线段长度可以转化为点积(axbx+ayby=长度的平方).

  • 枚举xxdxd|x所用的时间可以做到O(nlgn)O(nlgn)

  • 树分治大多数时候是容斥(lca不是当前分治中心的情况要减去之类的)类似当前算一遍答案,然后减去子树答案.

  • 数学题如果碰到带下取整的,考虑分块。
    如果是函数,则分块自变量。
    比如说我们现在要分块的是F(x)这个式子。
    设F(x)>=trunc(F(l)),x>=l.
    解出来所得到的x取值范围就是相同的个数。

  • 若存在ax+by=cax+by=c​,c必然有因数(a,b),(a,y),(x,b),(x,y)(a,b),(a,y),(x,b),(x,y)​。将原方程看作以选定两个数为系数的不定方程可得。
    反过来,当c没有因数(a,y)(a,y)时,必定不存在x,b满足ax+by=cax+by=c

  • 最小割经典约束:当前决策x,某个决策y就必须满足某些条件f(x,y)
    【Srm590】Fox And City(fox) 3749
    【HNOI2013】切糕 3222

  • 莫比乌斯反演的两种常见套路:
    要求的函数为g。
    1.f为其所有约数的g函数之和。\Rightarrow g(x)为约数的fmui之和。 (容斥范围:x的约数)
    2.f为n以内其所有倍数的g函数之和。\Rightarrow g(x)为n以内所有倍数的f
    mui之和(容斥范围:x的倍数)

  • (n/d)/i=n/(i*d),整除。 证明略去。所以分块n/(id)等价于分块(n/d)/i

  • 欧拉函数和莫比乌斯函数的两个性质 (狄利克雷卷积)

  1. n=dnφ(d)n=\sum_{d|n} \varphi(d)
    n=pkn=p^k时上式成立,又因为f(n)是积性函数(莫比乌斯反演可推),得证!
    (其实理解成最简分数也可以)
    dndμ(n/d)=φ(d)\sum_{d|n}d \cdot \mu(n/d) = \varphi(d)
    理解:容斥,考虑一个数x被计算的系数是d(n,x)μ(d)\sum_{d|(n,x)}\mu(d)

  2. dnμ(d)=[n==1]\sum_{d|n}\mu(d)=[n==1]
    使得μ(d)\mu(d)不为0则d不能有平方因子,二项式定理可证。

  • O(n)O(n)求阶乘逆元,有逆元的充要条件是(p,x)=1(1<=x<=n)(p,x)=1 (1<=x<=n)
    f(x)=x!1(modp)f(x)=x!^{-1} (mod p),
    f(x)=x1(x+1)!=xf(x+1)f(x)=x*{\frac 1 {(x+1)!}}=x*f(x+1)

  • O(n)求1…n关于p的逆元,前提是1…n与p互质。
    下面是在%m意义下的:
    x(m/x)+(mmod  x)=0x*(m/x)+(m\mod x)=0
    x=(mmod  x)m/xx=\frac {-(m \mod x)} {m/x}
    x1=(m/x)(mmod  x)1x^{-1} = -(m/x) * (m \mod x)^{-1}
    代码就一行: A[i] = -(m / i) * A[m % i];
    UPD:SB才背这个,直接用阶乘算。

  • 卢卡斯定理求Cnm,C_n^m, %p,p is a prime.
    设ni,mi满足n=i=0knipi,m=i=0kmipin = \sum_{i = 0}^{k}{n_i \cdot p^i}, m = \sum_{i = 0}^{k}{m_i \cdot p^i},也就是表示n,m在p进制下的第i位数字
    C(n,m)i=0kC(ni,mi)(modp)C(n, m) \equiv \prod_{i = 0}^{k}{C(n_i, m_i)} \pmod{p},

    递归形式是Cnm=Cn/pm/p  Cn mod pm mod pC_n^m=C_{n/p}^{m/p}~*~C_{n~mod~p}^{m~mod~p} (整除)
    注意卢卡斯定理的局限性:它只适用于模质数的情况。其他方法

  • 对于不平凡的参数求组合数先考虑约分,比如求C(n+i,i)

  • 多重背包有两个办法,一是按位分物品(1,2,4,8…+一个数可实现所有取法覆盖),一是单调队列。前者比后找多一个log 总结原文

  • 次小生成树的O(m log n)O(m~log~n)方法:选上一条没选的边,减去mst上的瓶颈路。
    http://blog.csdn.net/sluqy671/article/details/41720785

  • 有、无向图tarjan缩环(边双连通分量)
    http://blog.csdn.net/jokerwyt/article/details/52516186

  • 如何判断树上路径相交?+ 树状数组+dfs序维护各种信息 jzoj5290行程的交集

  • 给定二叉树的前序遍历与后序遍历,若每个点都有两个儿子或没儿子,那么只有唯一一种构造方法。 (否则x个点有1个儿子就有2^x种方案,k叉树可以用C函数类似推广)

  • 自然数幂和的几种求法:

O(k^2)递推式 http://blog.csdn.net/jokerwyt/article/details/54141757
拉格朗日插值法 http://blog.csdn.net/jokerwyt/article/details/78165667

  • 卡特兰数的通项公式
    http://blog.csdn.net/jokerwyt/article/details/77414853

  • i=1n[(i,n)=1]i\sum_{i=1}^n [(i,n)=1] i
    =φ(i)i/2= \varphi(i)*i/2 (当i不等于1时,否则=1)
    若包括1的情况可以加上0.5来补足。

  • 【51Nod1833】环 有向图的每个简单环覆盖对应着二分图(原有边i,j拆为i,j’)中的一组完美匹配. (任意点保证一条入边,一条出边)

  • 曼哈顿距离(斜着的正方形)转正方形,坐标轴顺时针旋转45",并放大2\sqrt 2倍(x,y)->(x-y,x+y)。关注原坐标轴上的点可得。

  • 为了减少记忆量,坐标旋转公式可用复数乘法轻易推得。 (复数乘法性质: 两复数相乘,其结果模长相乘,极角相加。)

  • 带绝对值的式子,考虑用数据结构分符号分类求解! (如数据结构+cdq分治等)

  • 多边形的三角剖分的一个结论:必定存在一条将两边都分为>=1/3的对角线

  • n个数不能组成三角形的性质=排序后任意两相邻两项和小于下一项
    因此不能组三角形最密集的数列就是斐波那契数列。
    换句话说,1e9级别的边长,多于50~60个,一定能组成三角形


#模板

heap:
#include<queue>
priority_queue<T,vector<T>,greater<T> > q; 小根
priority_queue<T> q; 默认大根,切记切记
少用operator<,容易翻车
//记得在开头结尾放一个与串中字符都不一样的字符(这两个也不能)
void manachar() {
	for (int i=1; i<=n; i++) {
		if (mx>i) {
			len[i]=min(mx-i,len[mxmid*2-i]);
		}
		
		while (t[i-len[i]-1] == t[i+len[i]+1]) {
			len[i]++;
			if (i+len[i]>mx) {
				mx=i+len[i],mxmid=i;
			}
		}
	}
}
//manachar
//先在开头结尾和字符中间插入#
//r[i]为回文串向右延伸长度,比如ababa,r[3]=3.
void Build() {
    int p = 0, mx = 0;
    fo(i, 1, n) {
        r[i] = mx > i ? min(r[p * 2 - i], mx - i + 1) : 1;
        while (i > r[i] && s[i - r[i]] == s[i + r[i]]) r[i] ++;
        if(i + r[i] - 1 > mx) p = i, mx = i + r[i] - 1;
    }
}
//堆
void swap(int &x,int &y) {
	int z=x; x=y; y=z;
}
void down(int x) {
	if(x*2>tt) return;
	int y=x*2; if(x*2<tt && d[y+1]<d[y]) y++;
	if(d[x]>d[y]) swap(d[x],d[y]),down(y);
}
void up(int x) {
	if(x==1) return;
	int y=x/2;
	if(d[x]<d[y]) swap(d[x],d[y]),up(y);
}

splay模板题
3599. 【CQOI2014】排序机械臂

#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 100100
#define fs first
#define sc second
#define isRc(x) ((c[fa[x]][1])==(x))
using namespace std;
typedef pair<int,int> mp;
int n,a[maxn],rmd[maxn],sum[maxn],c[maxn][2],lazy[maxn],root;
int fa[maxn];
mp tmp[maxn];

int build(int l,int r) {
	if (l>r) return 0;
	int x=l+r>>1;
	rmd[x]=1;
	sum[x]=r-l+1;
	if (l!=r) {
		c[x][0]=build(l,x-1);
		c[x][1]=build(x+1,r);
		fa[c[x][0]]=fa[c[x][1]]=x;
	}
	return x;
}
void update(int x) {
	sum[x]=sum[c[x][0]]+sum[c[x][1]]+rmd[x];
}
void putTag(int x) {
	lazy[x]^=1; swap(c[x][0],c[x][1]);
}
void downTag(int x) {
	if (lazy[x]==1) {
		lazy[x]=0;
		putTag(c[x][0]); putTag(c[x][1]);
	}
}
int Q[maxn];
void downTags(int x,int y) {
	while (fa[x]!=y) Q[++Q[0]]=x,x=fa[x];
	while (Q[0]) downTag(Q[Q[0]--]);
}
void rotate(int x) { 
	int y=fa[x],z=isRc(x);
	//Step 1. do y,c[x]
	c[y][z]=c[x][1-z];
	if (c[x][1-z]!=0) fa[c[x][1-z]]=y;
	
	//Step 2. do fa[y],x
	fa[x]=fa[y];
	if (fa[y]!=0) c[fa[y]][isRc(y)]=x;
	
	//Step 3. do x,y
	c[x][1-z]=y,fa[y]=x;
	update(y); //Final update y
}
void splay(int x,int y){ //必须按照如下方法旋转,否则无法保证势能
	downTags(x,y);
	if (y==0) root=x;
	while (fa[x]!=y) {
		if (fa[fa[x]]!=y) 
			if (isRc(x)==isRc(fa[x])) rotate(fa[x]); else rotate(x);
		rotate(x);
	}
	update(x);
}
void printTree(int x) {
	if (x==0) return;
	downTag(x);
	printTree(c[x][0]); if (rmd[x])cout<<x<<" "; printTree(c[x][1]);
}
int main() {
	freopen("3599.in","r",stdin);
	//freopen("3599.out","w",stdout);
	scanf("%d",&n);
	for (int i=1; i<=n; i++) scanf("%d",&a[i]),tmp[i]=make_pair(a[i],i);
	root=build(1,n);
	sort(tmp+1,tmp+1+n);
	int loc;
	for (int i=1; i<=n; i++) {
		loc=tmp[i].sc;
		splay(loc,0);
		printf("%d ",sum[c[loc][0]]+i);
		rmd[loc]=0;
		putTag(c[loc][0]);
		update(loc);
	}
}

3766【BJOI2014】大融合
lct虚边维护子树大小

#include <iostream>
#include <cstdio> 
#include <cstring>
#define N 100100
#define isroot(x) (c[fa[x]][0]!=(x) && c[fa[x]][1]!=(x))
#define get(x) ((c[fa[x]][1]==(x)))
typedef long long ll;

using namespace std;
ll c[N][2],fa[N],rev[N],add[N],size[N],fsum[N],ff[N];
ll n,q;
int Q[N];
void flip(int x) {
	if (x!=0) rev[x]^=1,swap(c[x][0],c[x][1]);
}
void down(int x) {if (rev[x]) flip(c[x][0]),flip(c[x][1]),rev[x]=0;}
void downs(int x) {
	while (!isroot(x)) Q[++Q[0]]=x,x=fa[x];
	Q[++Q[0]]=x;
	while (Q[0]) down(Q[Q[0]--]);
}
void update(int x) {
	size[x]=size[c[x][0]]+size[c[x][1]]+1;
	fsum[x]=fsum[c[x][0]]+fsum[c[x][1]]+ff[x];
}
void rotate(int x) {
	int y=fa[x],z=get(x);
	if (c[x][1-z]) fa[c[x][1-z]]=y;
	c[y][z]=c[x][1-z];
	fa[x]=fa[y];
	if (!isroot(y) && fa[y]) c[fa[y]][get(y)]=x;
	fa[y]=x;
	c[x][1-z]=y;
	update(y);
}
void clear(int x) {
	if (x==0) return;
	down(x);
	clear(c[x][0]),clear(c[x][1]);
}
void splay(int x) {
	downs(x);
	while (!isroot(x)) {
		if (!isroot(fa[x])) {
			if (get(x)==get(fa[x])) rotate(fa[x]); else rotate(x);
		}
		rotate(x);
	}
	update(x);
}
void access(int x) {
	for (int i=0; x!=0; i=x,x=fa[x]) {
		splay(x);
		ff[x]+=fsum[c[x][1]]+size[c[x][1]]-fsum[i]-size[i];
		c[x][1]=i;
		update(x);
	}
}
void makeroot(int x) {  
	access(x);
	splay(x);
	flip(x);
}
void link(int x,int y) {
	makeroot(x);
	access(y);
	splay(y);
	ff[y]+=fsum[x]+size[x];
	fsum[y]+=fsum[x]+size[x];
	fa[x]=y;
}
int main() {
	//freopen("2.in","r",stdin);
	//freopen("2.out","w",stdout);
	cin>>n>>q;
	for (int i=1; i<=n; i++) size[i]=1;
	for (int i=1; i<=q; i++) {
		char cc; int u,v;
		scanf("\n%c %d %d",&cc,&u,&v);
		if (cc=='A') link(u,v);
		if (cc=='Q') {
			makeroot(u);
			ll sizea=fsum[u]+size[u];
			access(v);
			splay(v);
			ll sizeu=ff[u]+1;
			printf("%lld\n",(sizea-sizeu)*sizeu);
		}
	}