1001
签到
1002
有向树上路径加上从 $1$ 开始逐渐递增 $1$ 的平方数，即每个点分别加上 $1^2,2^2,3^2…$，询问单点值。
这种题首先可以考虑序列做法，然后把序列搬到树上路径只需树剖就可以解决。
对于一个序列区间加上平方数，既然是区间操作，肯定用线段树。
常见的询问平方和，一般是用 $pushup$ 来做到，一般是维护 $\sum x^2$，$\sum x$，在考虑其他修改操作的影响，来继续维护这些值，就能做到。
而这里是区间加平方数的操作，是对于修改有递增的情况，这个可以用 $pushdown$来维护。
考虑给区间 $[l,r]$ 加递增的平方值 $v^2,(v+1)^2…$，先考虑只给区间的左端点加上一个确切的平方值 $v^2$，那么考虑这个区间的其他点该加上啥？
应该是 $(v+len)^2$ ， $len$ 表示里左端点的距离。
展开后发现只需维护 $v^2$，$2*v$， $1$，在乘上对应的 $len$ 部分即可，这个可以在线段树中的 $pushdown$ 里将所有点的递增影响都搞定。
有向的话，依然让区间递增是 $1$ ，考虑一个初值给一个负数即可。
不难发现这样做的正确性，虽然我也是第一次见。
搬到树上，只需维护一下当前要处理加上的 $[l,r]$的平方值，按树剖划分的重链进行序列操作来搞即可。
1003
$n$ 个点 $m$ 条边的无向图，两人一人在 $x$ 点，一个人在 $y$ 点，都想到 $z$ 点，每一轮中两人先后移动，在某轮结束后，如果一人到了但另一人没到就谁赢，都没到或者都到不了算平局。合法 $move$ 是不动或者走邻边，除了起点和终点以外不能同时存在超过两个人。
分析：
$n<=1000$ 允许 $n^2$ 做法。
$Case_1$：首先，谁离 $z$ 近谁一定赢，另一个人因为距离最远，无法破坏更近的人先到。
$Case_2$：距离一样的时候，因为最短路可能有多条，点会重，有不能共点的性质，比较麻烦，考虑一个显然的 $dp[x][y][0/1]$ 表示第一个人在 $x$ ，第二个人在 $y$ ，轮到谁移动，两个人都想先到，所以转移一定枚举到 $z$ 最短路上的边进行转移。只需记忆化搜索一下即可。
证明：如果你不走到 $z$ 的最短路，那么另一人走了，转为 $Case_1$你就莓樂。
因为目的是最快到 $z$ ， $bfs$ 预处理从 $z$ 出发所有走最短路的边即可。
每个状态，每个转移只会遍历到一次，故复杂度 $O(n^2+m)$。
1004
一个序列 $c_i$ $(1 \leq c_i \leq n)$，每次询问一个区间 $[l,r]$ 有多少不同的 $c_i$ 满足 $c_i\bigoplus a \leq b$ 。
发现是前面几天两个题的结合。
询问 $c_i\bigoplus a \leq b$ ，属于是经典题，很容易可以在字典树上维护信息贪心做到。
询问区间不同数个数，杭电 1 也有题，又属于是经典题了，这个可以用莫队离线做。
两者结合在一起，很显然，我们有一个维护字典树的莫队离线做法。维护数出现的次数在字典树上修改，查询在对应的一棵区间的字典树上找答案即可。这样复杂度上界是 $O(n \sqrt n log_2n+qlog_2n)$ 的。因为莫队的修改，可能会让数在字典树上频繁插删。(只要你不像我傻逼一样写，在字典树上维护 $cnt$ ，$2s$ 是能卡过的)
实际上，在字典树上找数，其实对应的是一个连续的区间，我们可以对值域分块。这样修改很简单，不需要搞字典树，只需要维护块的变换即可。而查询类似在字典树上，按位走，查询连续的一块区间，虽然看起来一次询问是 $O(\sqrt n)$ 的，对一个询问 $log$ 位次，但实际上询问的区间长度是 $2^k$ 不断缩小的。似乎可以除掉一个 $log$ 。单次总共询问的区间长度是 $n$ 级别的，故是个 $\sqrt n$ ？
最终复杂度是 $O(n\sqrt n + q \sqrt n)$ 的。
1005
签到
1006
1007
每个点有 $a_i,b_i$，维护下列操作
- 区间给 $a_i$ 或 $b_i$ 加 $x$
- 区间 a 变 $3a+2b$， b 变 $3a-2b$
- 区间交换 $a,b$
- 求 $\sum_l^r a_i \cdot b_i$
有个显然的线段树维护 $6$ 阶矩阵，我冲了，但我 T 了。
维护 5 阶似乎比赛可过，正确做法是只需维护变换的两阶，剩下的可以算出来？
没学(
1008
简单 dp 一下即可。
1010
给一个序列 $b_x = ax \mod p$ $ (1 <= x <= p-1)$。求这个序列逆序对的奇偶性。
8 会，题解抽象，经 jly 讲解懂了一点。
显然 $b$ 序列 是一个长度为 $p-1$ 的排列。
设一个排列 $\pi$，第 $i$ 项是 $\pi_i$ ，设逆序对数为 $n$， 设他的奇偶性 $sgn(\pi)=(-1)^n$ $$ sgn(\pi)=\frac{\prod _{1 <= j < i <= p-1} \pi_i-\pi_j}{\prod _{1 <= j < i <= p-1} i-j} = \prod _{1 <= j < i <= p-1} \frac{\pi_i-\pi_j}{i-j}=\prod _{1 <= j < i <= p-1} \frac{ai-aj}{i-j} $$ 意思就是说你可以枚举排列的值，和排列的下标情况，如果他是逆序的，就会贡献一个 $-1$ ，否则是 $1$ ，这就是逆序对的所有情况，一个逆序对会贡献一个 $-1$。
化简式子可以直接得到答案。
1009
1011
给长为 $n$ 的数组 $A$ ， $B$ ，定义 $C_i = \max (A_i, B_j), (i \And j \geq k) $，求 $\sum _{i=0}^{n-1}C_i$
假设你要求一个二进制状态 $k$ 的答案。
那么对于 $k$ 的超集 $i$ ，超集就是所有的 $ k \And i=k $ 的 $i$，他的超集状态 $\And$ 起来一定能够超过他。对于一个 $k$ ，我们类似 $sosdp$， 可以维护出他的超集 $max$ 和 $min$ ，那么这些一定可以成为当前的答案。
但还有一些不是他的超集的状态，但能 通过 $\And$ 出来比他大的数，那么可以对更大的 $k$ ，做一样的事情，于是记录答案的后缀 $max$ 即可。
1012
签到
我居然因为 $s.size()$ 返回的是无符号数，减到负数会烂导致 wa 了一发。