A

考虑把每个$abcabc$当做一个位置，那么$acbacb$要么分别位于三个位置，要么$acac$在一个位置，$bb$在一个位置，所以答案为$C(n,3)+C(n,2)C(n,3)+C(n,2)$

B

首先能发现一个结论，一棵树最长直径=度数大于$11$的节点个数$+2(n>1)+2(n>1)$

所以我们只需要枚举度数大于$11$的节点的度数，剩下就是一个插板问题

C​

验题的时候有人写了维护10个变量的矩阵乘法，较为复杂

注意到$pp$只有$100100$，我们观察发现一旦三元组$(a_i,b_i,c_i)(a\_i,b\_i,c\_i)$与之前的$(a_j,b_j,c_j)(a\_j,b\_j,c\_j)$相同

那么这个序列就构成了循环

而$(a_i,b_i,c_i)(a\_i,b\_i,c\_i)$只有$10^{6}10^6$种，所以直接暴力即可

D

首先二分答案，那么问题变成是否有一个区间满足$aa$的和$>mid>mid$且$bb$的和$>mid>mid$

转化成前缀和变成$sum1[r]-sum1[l-1]>mid,sum2[r]-sum2[l-1]>midsum1[r]-sum1[l-1]>mid,sum2[r]-sum2[l-1]>mid$

考虑从左到右扫描序列，将$sum1sum1$映射到树状数组的下标，$sum2sum2$对应到树状数组维护的值

时间复杂度：$nlo{g}^{2}nnlog^2n$

这个题也可以做到一个$loglog$

强制令

那么我们其实只需要找到满足这个的$sum1[r]-sum1[l-1]sum1[r]-sum1[l-1]$的最大值即可

扫一遍直接维护即可

由于$nn$只有$10^{5}10^5$,两种做法都可以通过

E

观察题目保证$a_{i}a\_i$互不相同

打表发现可能同时出现在$SS$集合和$TT$集合的只有$150150$和$294294$

枚举这两个数到底在$SS$集合还是$TT$集合，问题变成了比较经典的拆边费用流

对于流量从$1\sim m1\backslash sim\; m$,每次增加$11$的流量跑一次$spfaspfa$

F

两点距离$dis(i,j)dis(i,j)$可以看成$(x_i,x_j)(x\_i,x\_j)$到$(y_i,y_j),(y_j,y_i)(y\_i,y\_j),(y\_j,y\_i)$的哈夫曼距离取$minmin$

将坐标系旋转$4545$度，到一个点哈夫曼距离相同的点是一个正方形

于是每一次$33$操作其实只需要查询两个矩形的并内的点的个数

由于这两个矩形是平行的 所以矩形的并要么是一个大矩形 要么是两个小矩形

这个可以利用树套树或者离线三维偏序维护

对于每次$22$操作考虑重构，等价于查询$nn$个矩阵内有多少个点

这个可以扫描线+树状数组统计

总时间复杂度$nlo{g}^{2}nnlog^2\{n\}$

由于时间没有卡的很紧，赛时一些$nlo{g}^{3}nnlog^3\{n\}$的做法也通过了

G

首先不考虑晋升,那么每个位置上的选择可以写成$\frac{1}{y}\ast x,\frac{1}{y}\ast \frac{y-1}{y}\ast x^2+\frac{1}{y}\ast {(\frac{y-1}{y})}^2\ast x^3+\mathrm{.}\mathrm{.}\mathrm{.}\backslash frac\{1\}\{y\}*x,\backslash frac\{1\}\{y\}*\backslash frac\{y-1\}\{y\}*x^2+\backslash frac\{1\}\{y\}*\{(\backslash frac\{y-1\}\{y\})\}^2*x^3+...$

这个可以写成$t\ast \frac{x}{1-kx}t*\backslash frac\{x\}\{1-kx\}$的形式

于是不晋升时问题就可以用一次分治$NTTNTT$+求逆来解决

观察到有一次晋升其实是一个前缀多项式乘后缀多项式

把这个转化成全局多项式相乘除掉中间那一段多项式

于是我们可以考虑维护每一段长度为$oo$的多项式的乘积

考虑从左到右扫过去，相邻两个位置相当于是除掉一个多项式，乘上一个多项式

由于多项式系数只有1,所以我们利用类似背包可以$O(o)O(o)$维护

总时间复杂度$nlo{g}^{2}n+nonlog^2\{n\}+no$