输出n成功骗到10分

回复 @Cydia :
6666666666666666666

官方题解用的是二分答案。
设二分的答案为$a$，将整个序列中>=$a$的值变为1，<$a$的变成0，对于每次部分排序，可以通过线段树的区间更新实现，若为升序则把区间内0全部排在前边，1排在后边，反之亦然。全部部分排序结束后检查p上的值是1还是0，从而继续调整下一次二分。
总时间复杂度:$O(mlog^2n)$.
ps:真的是$log^2n$,不是$log_2n$......
pss:其实当时想到了线段树，然而没有二分答案线段树根本无从谈起，最后用的$O(nm)$的桶排暴力，数据过鶸成功骗到80分

小金明

回复 @智霞Forever :
[size=56]
我想静静❤ [/size]

裸DP80分。。。

回复 @Cydia :
本来就是,数据过水
你能想到考场上好不容易想出正解然后爆零的感觉么

据说代码最长10K，然后我打了5000个表50+K。。。

回复 @葳棠殇 :
写了个暴搜的路过

这题正解是并查集，由于路径压缩不可逆，所以需要倒序处理操作，在第一个有标记的点停止路径压缩。
这里是一个考场上写了并查集然而莫名WWWWWWWWWW的渣渣，或许是需要用bfs建图？
顺便，findroot最好改成迭代版(虽然辣鸡数据并不需要)，还有倒序处理时抹掉一个点的标记仅限于第一次给它打标记时。

QAQ

出题人有没有良心地做数据，竟然让暴力随意地就过了，简直就是半星题连普及组难度都没有啊好不好QAQ

渣渣O(n^2*100)的渣渣dp，完全是考场代码。

回复 @智霞Forever :
你能想到正解和暴力分一样多的感觉吗？

本来以为考试的时候没加特判，不会AC的，结果后来看我的代码才发现，其实我已经不知不觉加了一个特判…所以成为全场仅有的2个AC的之一…

高一表示并不知道单点不算食物链orz

我又一次证明了后缀数组能做到的后缀自动机也能做！
要不是考场上看错题了呜呜

k-d树被卡成狗啊 QAQ

不知道有没有和我一样看错题的小伙伴QAQ。。

考场上CE了.... linux下宏定义unsigned一定要写在库的底下..血的教训