洛谷题目传送门
你谷无题解于是来补一发
随便百度题解，发现了不少诸如树剖LCT的可怕描述。。。。。。
于是来想想怎么利用题目的性质，把复杂度降下来。
首先，每个点的输出状态只有，于是每个点的总状态也非常有限，可以根据权值为的儿子数量分为四种，记为该点的点权。
我们都会模拟暴力过程——先改叶子节点（先默认为改为），如果它的父亲此时权值为的儿子数量从原来小于的变成大于的，那么父亲的权值也要改。以此类推，直到有一个节点输出状态没有变化，那么它的所有祖先肯定不会变。
通过模拟我们发现，每次修改的一定是一段自底向上的连续区间！
接着也就不难想到，只有当点权为时，才能通过修改点权变成，使输出由变成，从而继续引发祖先的变化。那么我们需要知道的就是，对于每一个叶子节点，它自底向上的连续一段点权为的部分。
再讨论叶子节点改的情况，同理也可以发现我们还要维护自底向上的连续一段点权为的部分。
这个可以树剖（有很多维护法，都是的，跳链和链修改都有）正在学树剖，先留个坑，到时候再补。。。
当然可以LCT，讲两个维护法。第一种是用bool值维护区间是否有权值不为的点，每次Splay上二分查找最深的不为的点，把它伸展上来，右子树做区间修改，这个点做单点修改。
因为写二分比较麻烦（其实就是几行的事），所以还不如直接维护最深的不为点的编号，找都不用找。直接把它伸展上来。修改同上。容易发现这里的LCT连换根都不要。
两种写法都需要注意特判：如果整条从根到叶子的链没有一个不为的点，直接做区间修改。
分享一个naive的错误——蒟蒻默认父节点的编号比子节点小，然后pushup直接取，竟然获得了95分？！调了半天本机对拍又是全AC（自己的数据生成器肯定是父节点的编号比子节点小啦。。。）
刚掉这题后还收获了一点小经验——不要给LCT永久化地贴上常数大的标签！因为少一个，所以越大越有优势（这题），还不用reverse。看看统计，就知道什么叫LCT全方位（时间、空间、码量）完爆树剖的感觉了哈哈哈哈hhhh
https://www.luogu.org/recordnew/lists?uid=&pid=P4332&status=&sort=1
https://loj.ac/problem/2187/statistics/fastest
#include<cstdio>
#include<algorithm>
#define RG register
#define I inline
#define R RG int
#define lc c[x][0]
#define rc c[x][1]
#define G if(++ip==ie)if(fread(ip=ibuf,1,L,stdin))
using namespace std;
const int N=5e5+9,M=1.5e6+9,L=1<<19;
char ibuf[L],*ie=ibuf+L,*ip=ie-1;
int n,f[M],c[N][2],t[N],n1[N],n2[N],v[M],q[M],d[N];
I int max(R x,R y){return x>y?x:y;}
I int in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){(x*=10)+=*ip&15;G;}
return x;
}
I bool nrt(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I void up(R x)
I void dn(R x,R tg){//被区间修改的要么都是1要么都是2，直接反转信息
v[x]^=3;swap(n1[x],n2[x]);t[x]+=tg;
}
I void all(R x)
I void rot(R x)
I void sp(R x)
I void ac(R x){
for(R y=0;x;sp(x),rc=y,up(y=x),x=f[x]);
}
int main()
nowrt=v[1]>>1;
for(R q=in();q;--q)
else dn(x,tp),up(x),nowrt^=1;//注意特判
putchar(nowrt|'0');putchar('
');
}
return 0;
}
