省选测试37

A.小A的树

首先dfs整颗树搜出dfn序列

然后发现每个点对都可以由(i)与其对应的(dfn)序列中的位置前面的点构成

将每个当前最远点对扔进堆里，堆中取出最大值

然后将原区间分成两个小区间 对于小区间一样操作就可以了

求出一个点集中距离当前点最远的点线段树维护直径就可以了

B.小B的序列

势能分析线段树

维护与，或的懒标记

强制先'与'后'或'

(a and b or c or d =a and b or (c or d))
(a and b or c and d = a and (b and d) or (c and d))

考虑一个区间的大小关系会发生变化的情况：

1.某一个二进制位有不同的0，1状态，并且当前位置( or 1)

2.某一个二进制位有不同的0，1状态，并且当前位置( and 1)

而其他情况对于大小关系的顺序是不变的

考虑如何快速求不同0，1状态的二进制位

可以维护一个区间或 和 区间与

发现如果某一位既有0也有1，那么区间或 和 区间与 异或起来这一位为1，其他情况当前位为0

对于上面的情况知道：

1. 处理与时，当前异或之后的值为与值k的子集时，大小关系不变
2. 处理或时，当前异或之后的值与值k没有交集，大小关系不变

然后就按照这个判断法则直接做就可以了， 如果大小关系不变打标记，其他情况暴力递归

另一种做法：

不去记录与和或的懒标记

发现如果满足上述法则，那么一定是整个区间的变化量相同，所以直接去做区间减法就可以了

C.小C的利是

发现这个定义特别像行列式，但是行列式对于这部分的处理是连乘

所以想到去构造一个新矩形，然后此时原矩形作为新矩形的权值的指数

所以先去找一个大质数P满足(P equiv 1 (mod k))

然后找出(P)的(k)次单位根(g)满足(g^k equiv 1 (mod P))

以((g^{A_{i,j}})^a)作为新矩形的权值 发现对于这个东西，将其(a)次方挨个代入(a in 0,1,2...,k-1)

设(S=sum_{i=1}^{n}A_{i,p_i})

对于所有行列式求和，发现最终将前面的系数提出来后是(g^0+g^S+g^{2S}+...+g^{(k-1)S})

对于(S=0)的情况，显然最终答案是(k)

对于(S!=0)的情况，根据等比数列求和公式，最后模P之后答案是0

所以最后只要判断一堆行列式的和是否为0就可以了

但是由于这种做法可能会被(-1)的系数将本来的贡献清掉

所以给每个位置再随机一个权值