20251120

· · 个人记录

T1

从小到大枚举每个数。这类似CDQ中排序省掉一维。只用维护比第一个数靠前的有多少就行了。

我最开始以为线段树需要维护：

然后准备用树状数组区修区查那一套。然后发现维护不了 a_i \times i。卡了我15min。

然后发现只用查询前缀和就行了。然后就过了。

调试的时候调出来一个问题：前面有多个相同数不会多次影响离散化。没离散化导致的。

T2

我考场上转化到了树的那一步(网格 > 图 > 树)。

然后不会 kruskarl 重构树。

CBC 有一种不用 kruskarl 重构树的做法，但是和 kruskarl 重构树没啥区别。

所以我就卡这了。只能打暴力。

今天学了 kruskarl 重构树，这道题改了,但是没做点练习题。啥时候把归程做了。

T3

杨表。模板。没学。不会。

我能总结的只有 n=2 没看出它是 Catlan Number。

故意出一个打表题来搞搞心态。--题解

T4

分两部分的缝合题。

第一部分是一个复杂的断环为链转为区间问题，使用BIT维护区间。思维链很长，不容易想到。

第二部分是一个根号分治。在没想出第一部分的情况下，我没有分时间去思考

所以我T4只剩暴力了。