0905练习记录

· · 个人记录

小A的树

可以先二分答案然后树分治,也可以直接树分治然后套个堆.

用堆常熟小但是脑瘫没想到.二分答案的话大概就是二分第K大的长度,转化为统计比他小的路径数.直接淀粉质双指针或者边分治双指针就行了.

code

小B的序列

神奇的玩意儿。。。

用线段树维护这个东西。在线段树上重复：

1.如果当前操作不会影响当前区间之间数的相对大小，直接操作，打标记然后返回

2.否则向下递归

标记的话，维护先and后or的两个lazy标记，再维护区间或以及区间与以及区间max就行了

复杂度分析的话要势能分析。可以证明是两个log的

code

小C的利是

根据他这个选法，可以联想到det的定义

所以可以根据这个做一个像是单位根繁衍的操作

具体看dalao博客 我好懒啊

code