T1

简要题意：

给你一个 $n$ 和一个质数 $m$，然后给你一个长度为 $n$，互不相同的 $a$ 序列，求是否存在一种 $a$ 的排列方式使得 $a$ 是一个 $\bmod \ m$ 意义下的等差数列。如果存在，输出任意一组可能的首项 $x$ 及公差 $d$，否则输出 $−1$。

$n \le 10^5, m \le 10^9+7$

提交记录：http://172.3.10.101/submission/130583

T2

简要题意：

求解长度为 $n$ 的且逆序对数也为 $n$ 的排列的数目，$\bmod \ 10^9+7$。

$n\le 10^5$

提交记录：http://172.3.10.101/submission/129930

T3

简要题意：

给出一个 $n$ 个点 $m$ 条边的无向简单图，对于每一条边 $u, v$ 保证 $|u-v|\le k$，有 $q$ 次询问，每次询问一个区间 $l,r$，只保留 $[l,r]$ 内的点和边，求连通块个数。

$n, q \le 10^5, 1 \le k \le 5$

题解

考虑离线询问然后分治（或者直接猫树在线查询，异曲同工）。

令 $solve(l,r,q)$ 表示当前正在考虑区间 $[l,r]$ 上的 $q$ 个查询。

对于 $r-l+1\le k$ 的区间，直接暴力求解。

对于没有跨过区间中点的询问，取出查询（令左区间的查询为 $ql$，右区间为 $qr$）后，可以直接递归到两边即 $solve(l,mid,ql)$，$solve(mid + 1, r, qr)$。

对于跨过区间中点的询问。

令 $c_i, i \le mid$ 表示从 $i \sim mid$ 的连通块个数。
令 $c_i, i > mid$ 表示从 $mid + 1$ 到 $i$ 的连通块个数。

那么区间 $[l,r]$ 的答案为 $c_l+c_r-dec$，其中 $dec$ 为合并左右两个区间后减少的连通块数量。

显然只有 $|i-mid|\le k$ 的位置 $i$ 会让左右两个区间的连通块合并，由于 $k\le 5$，如果知道 $[mid-k,mid+k]$ 在考虑 $l,r$ 后的连通状态，就可以直接合并。

但我们显然不能再重新对 $l,r$ 求一遍连通状态，因此我们在求 $c$ 时记录 $anc_{i,j}$ 表示 $mid \sim mid+j$ 或者 $mid-j \sim mid$ 的连通块状态即可。

提交记录：http://172.3.10.101/submission/130544

T4

简要题意：

给出一个长度为 $n$ 的序列，定义两个等长序列相似为两个序列排序后最多只有一个位置不同，每次询问这个序列上的两个等长区间 $[p,q]$ 和 $[l,r]$ 是否相似。

$n, q \le 10^5, 1 \le a_i \le 10^5$

题解

考虑给每一个数随机赋权，$a_i$ 的权值为 $val_{a_i}$ 那么区间 $[p,q]$ 和 $[l,r]$ 的必要不充分条件是：$\sum_{i=l}^r val_{a_i}=\sum_{i=p}^q val_{a_i}$ 或 $(\sum_{i=l}^r val_{a_i}) - val_{a_x}=(\sum_{i=p}^q val_{a_i})-val_{a_y}$，其中 $x \in [l,r], y \in [p, q]$。

容易想到用权值主席树维护权值，主席树的每一个节点存储子节点的权值和，那么可以主席树上二分找到第一个不同的位置和最后一个不同的位置（显然如果合法最多有两个不同的数字）。

但上面那个条件并不是充分条件，我们还需要满足对于这两个不同的数字 $x, y$，有 $\sum_{i=l}^r[a_i<x]=\sum_{i=p}^q[a_i<y]$。

这个条件主席树/分块都可以直接做。

提交记录：http://172.3.10.101/submission/130290