2020-2021 ICPC Asia Yinchuan Regional

Summary

比赛地址 ：Codeforces Gym 104022

待补：CFIL

难度：AEJ - GK - BDM - CFHIL

A - Best Player

给定一个三维点集，问去掉哪一维之后本质不同的点最多。

模拟。map<pair<int, int>, bool> 去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 107

int x[N], y[N], z[N];

map<pair<int, int>, bool> vis;

int main() {
	int n = rd();
	for (int i = 1; i <= n; ++i) {
		x[i] = rd(); y[i] = rd(); z[i] = rd();
	}
	int X = 0, Y = 0, Z = 0;
	for (int i = 1; i <= n; ++i) {
		pii nw = make_pair(y[i], z[i]);
		if (vis[nw]) continue;
		vis[nw] = true; ++X;
	}
	vis.clear();
	for (int i = 1; i <= n; ++i) {
		pii nw = make_pair(x[i], y[i]);
		if (vis[nw]) continue;
		vis[nw] = true; ++Z;
	}
	vis.clear();
	for (int i = 1; i <= n; ++i) {
		pii nw = make_pair(x[i], z[i]);
		if (vis[nw]) continue;
		vis[nw] = true; ++Y;
	}
	if (X >= Y && X >= Z) puts("X");
	else if (Y >= X && Y >= Z) puts("Y");
	else puts("Z");
	return 0;
}

*B - The Great Wall

一个长度为 \(n\ (1\le n\le 10^4)\) 的数列 \(a_1,a_2,\dots,a_n\)，划分成 \(k\) 段，假设第 \(i\) 段是 \([l_i,r_i]\) ，最大化： \[ \sum_{i=1}^k\bigg(\max_{l_i\le j\le r_i} a_j-\min_{l_i\le j\le r_i} a_j\bigg) \] 对 \(k=1,2,\dots,n\) 求出答案。

Trick 题，需要转换一下。注意到 \[ \max_{l_i\le j\le r_i} a_j-\min_{l_i\le j\le r_i} a_j = \max_{l_i\le j,k\le r_i}\big(a_j-a_k\big) \] 目标优化的方向（要求差值和最大）和差值优化方向（差值最大）相同，所以问题可以变成最大化每段内任选两个的差值和。

设 f[i][j][0/1/2/3] 表示前 \(i\) 个分了 \(j\) 段，当前一个都没选 / 只选了一个 \(-a_k\) / 只选了一个 \(+a_j\) / 两个都选了的最大和。

注意初始化为 \(-\infty\) （因为 f[i][j][1] 状态可能有负值），转移要考虑 \(j=k\) （选在同一个数）的情况。

空间比较紧，需要把第一维滚动数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

template<typename T>
inline bool getmax(T &a, T b) {return a < b ? (a = b, true) : false;}

#define N 10007
#define mp make_pair
#define pb push_back

int a[N], f[2][N][4];

// 1 : - a[y]
// 2 : a[x]
// 3 : a[x] - a[y]

int main() {
	int n = rd();
	for (int i = 1; i <= n; ++i) a[i] = rd();
	memset(f, 0xcf, sizeof(f));
	f[0][0][3] = 0;
	for (int i = 1; i <= n; ++i) {
		int nw = (i & 1);
		int pre = 1 - nw;
		for (int j = 1; j <= n; ++j)
			for (int k = 0; k < 4; ++k) f[nw][j][k] = f[pre][j][k];
		for (int j = 1; j <= n; ++j) {
			getmax(f[nw][j][0], f[pre][j - 1][3]);
			getmax(f[nw][j][1], max(f[pre][j][0], f[pre][j - 1][3]) - a[i]);
			getmax(f[nw][j][2], max(f[pre][j][0], f[pre][j - 1][3]) + a[i]);
			getmax(f[nw][j][3], max({f[pre][j - 1][3], f[pre][j][1] + a[i], f[pre][j][2] - a[i]}));
		}
	}
	for (int j = 1; j <= n; ++j) printf("%d\n", f[n & 1][j][3]);
	return 0;	
}

*D - Farm

\(n\ (n\le 10^5)\) 个点的图，有 \(m\ (m\le 5\times 10^5)\) 条边可以选择是否加入，求连通最小代价。

此外有 \(q\ (q\le 16)\) 个要求，每个要求 \(a_i\) 和 \(b_i\) 两条边中至少有一条被加入。

先把要求涉及到的 \(2q\) 条边加入到图中，在此基础上跑 Kruskal ，新加入的边集称作 out 。

out 中的边一定是存在在最终答案中的。再把图清空，只加入 out 中的边，然后按照连通性缩点。

这样子顶点最多只有 \(64\) 个，有意义的边最多只有 \(\frac{64\times 63}{2}=2016\) 条。

然后 \(2^q\) 枚举每个条件至少选了哪一个，然后暴力把这些边加入，然后对这 \(2016\) 条边再跑 Kruskal 即可。

因为每次不用重新排序，所以复杂度是 \(\mathcal{O}(2^q\times 2016+m\log m)\) 的，约 \(2\times 10^8\) 几乎没常数。

*坑：缩点之后每条边的顶点要维护，不能用的时候再 find ，因为每次并查集不是所有点都恢复，find 会找到错误的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007
#define M 500007

#define all(s) (s).begin(), (s).end()

struct edge {int u, v, w;} e[M];

vector<int> vertex, sel;

vector<edge> E, out;

map<pair<int, int>, bool> vis;

int f[N], id[20][2];

int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}

inline bool merge(int u, int v) {
    u = find(u); v = find(v);
    return u == v ? false : (f[u] = v, true);
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) f[i] = i;
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd();
        E.push_back(e[i] = {u, v, w});
    }
    sort(all(E), [&](edge &a, edge &b){return a.w < b.w;});
    int q = rd(), cnt = n - 1;
    for (int i = 0; i < q; ++i)
        for (int j = 0; j <= 1; ++j) {
            id[i][j] = rd(); cnt -= merge(e[id[i][j]].u, e[id[i][j]].v);
        }

    int add = 0;
    for (auto ed : E) 
        if (merge(ed.u, ed.v)) {--cnt; add += ed.w; out.push_back(ed);}
    if (cnt) {puts("-1"); return 0;} // not connected
    
    int ans = 1e9;
    for (int i = 1; i <= n; ++i) f[i] = i;
    for (auto ed : out) merge(ed.u, ed.v);
    for (int i = 1; i <= n; ++i) if (f[i] == i) vertex.push_back(i);
    for (int i = 1; i <= m; ++i) {
        e[i].u = find(e[i].u); e[i].v = find(e[i].v);
    }
    for (auto ed : E) { // reduction
        int u = find(ed.u), v = find(ed.v);
        if (u == v || vis[make_pair(u, v)]) continue;
        vis[make_pair(u, v)] = true; E[cnt++] = {u, v, ed.w}; 
    }
    E.resize(cnt);
    for (int i = 0; i < (1 << q); ++i) {
        int tmp = 0; sel.clear();
        for (auto x : vertex) f[x] = x;
        for (int j = 0; j < q; ++j) sel.push_back(id[j][(i >> j) & 1]);
        sort(all(sel));
        sel.erase(unique(all(sel)), sel.end());
        for (auto ID : sel) {tmp += e[ID].w; merge(e[ID].u, e[ID].v);}
        for (auto ed : E) if (merge(ed.u, ed.v)) tmp += ed.w;
        ans = min(ans, tmp);
    }
    printf("%d\n", ans + add);
    return 0;
}

E - Isomerism

阅读理解，胖胖做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<map>
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;

int te,A,B,C,D;
map<string,int> f;

void readi(int &x){
	static string s;
	cin>>s;
	x=f[s];
}
int main(){
	f["-F"]=8;
	f["-Cl"]=7;
	f["-Br"]=6;
	f["-I"]=5;
	f["-CH3"]=4;
	f["-CH2CH3"]=3;
	f["-CH2CH2CH3"]=2;
	f["-H"]=1;
	for (scanf("%d",&te);te;te--){
		readi(A);readi(B);readi(C);readi(D);
		if (A==C || B==D) puts("None");
		else if (A==B || A==D || B==C || C==D){
			if (A==B || C==D) puts("Cis");
			else puts("Trans");
		} else {
			if (A>C && B>D || A<C && B<D) puts("Zasamman");
			else puts("Entgegen");
		}
	}
	return 0;
}

G - Photograph

\(n\ (n\le 10^5)\) 个人编号 \(1\sim n\) ，编号为 \(i\) 的人身高 \(h_i\) ，现在要去拍合照。

给定一个 \(1\sim n\) 的排列 \(p\) ，代表 \(n\) 个人来的顺序，初始没人，第 \(i\) 个加入的是编号为 \(p_i\) 的人。

每个人加入之后，都要新拍一张照片，也就是一共会拍 \(n\) 张照片。

拍照片时，所有人会按照编号从小到大排列，然后定义照片的和谐度为相邻两个人身高差值的平方和。

形式化的，对于第 \(k\) 张照片，假设将 \(p_1,p_2,\dots,p_k\) 从小到大排序后为 \(q_1,q_2,\dots, q_k\) ，和谐度为 \(\sum_{i=1}^{k-1}(h_{q_i}-h_{q_{i+1}})^2\)

现请你求出 \(n\) 张照片的和谐度之和。

接下来，\(Q\ (Q\le 100)\) 次询问，每次将序列向左 Shift \((k+lastans)\) 次，再求答案。

时间倒流，开始所有人都在，每次相当于把两个区间合并，链表维护。复杂度 \(O(nQ)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define M 10007
#define N 100007
#define mp make_pair

int h[N], p[N], l[N], r[N];

set<int> s;

int main() {
	int n = rd(), q = rd();
	for (int i = 1; i <= n; ++i) h[i] = rd();
	for (int i = 1; i <= n; ++i) p[i] = rd();
	ll ans = 0;
	auto sqr = [&](int x) {return x * x;};
	auto pre = [&](int x) {return x == 1 ? n : x - 1;};
	auto work = [&](int x) {
		x = pre(x);
		s.clear(); ans = 0;
		ll nw = 0;
		for (int i = 1; i < n; ++i) {
			l[i] = i - 1; r[i] = i + 1;
			nw += sqr(h[i + 1] - h[i]);
		}
		l[n] = n - 1;
		for (int i = 1; i <= n; ++i) {
			ans += nw;
			int id = p[x];
			if (l[id]) nw -= sqr(h[id] - h[l[id]]);
			if (r[id]) nw -= sqr(h[id] - h[r[id]]);
			if (l[id] && r[id]) nw += sqr(h[l[id]] - h[r[id]]);
			r[l[id]] = r[id];
			l[r[id]] = l[id]; 
			x = pre(x);
		} 
	};
	int st = 1;
	work(st); printf("%lld\n", ans);
	for (int i = 1; i <= q; ++i) {
		int k = (rd() + ans) % n;
		st = (st + k - 1) % n + 1;
		work(st); printf("%lld\n", ans);
	}
	return 0;	
}

**H - Absolute Space

构造一个大小不超过 \(100\) 的点集，满足对于其中任意一个点，集合中恰好都有 \(n\ (n\le 10)\) 个点与他距离为 \(1\) 。

首先对于 \(n\le 4\) 的情况：长度为 \(1\) 的线段；正三角形；正四面体；正八面体；

对于 \(n=k>4\) 的情况，很容易想到把 \(k-1\) 的解复制一份，使得每个点和原本的距离为 \(1\) ，但点数会超。

理性思考一下，这个过程其实是 \(n=1\) 的解和 \(n=k-1\) 的解的闵可夫斯基和。那换成 \(n=x\) 和 \(n=k-x\) 合并可不可以呢？

正确性：假设 \(A\) 是 \(n=k_1\) 的解，\(B\) 是 \(n=k_2\) 的解，现在相当于证明 \(\forall p_a\in A,p_b\in B\) ： \[ \sum_{a\in A,b\in B} [dis(a + b, p_a + p_b) = 1]=k_1+k_2 \] 首先注意到：1. \(a=pa\) ，会有 \(k_2\) 个 \(b\) 符合条件；2. \(b=pb\) ，会有 \(k_1\) 个 \(a\) 符合条件;

且这两个情况交集为空，所以已经构成了所求的 \(k_1+k_2\) 个点。

对于其他情况，只需要把 \(A\) 或 \(B\) 里所有点整体沿着三个轴都随机旋转一个角度，就可以避免恰好凑出距离 \(=1\) 的情况。

合法性：最小化闵可夫斯基和大小 \(=size[k-x]\times size[x]\) 时，所需的点数分别为：\(12,16,24,36,64,96\) 刚好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define pb push_back

const double eps = 1e-4;
#define z(x)   (abs((x)) <= eps)
#define sqr(x) ((x) * (x)) 

#define letp const P

struct P {
    double x, y, z;
    P operator + (letp &p) const {return {x + p.x, y + p.y, z + p.z};} 
    P operator - (letp &p) const {return {x - p.x, y - p.y, z - p.z};} 
    bool operator == (letp &p) const {return x == p.x && y == p.y && z == p.z;}
    P rotx(double ang) const { 
        double cosa = cos(ang), sina = sin(ang);
        return {x, y * cosa - z * sina, y * sina + z * cosa};
    }
    P roty(double ang) const { 
        double cosa = cos(ang), sina = sin(ang);
        return {x * cosa - z * sina, y, x * sina + z * cosa};
    } 
    P rotz(double ang) const { 
        double cosa = cos(ang), sina = sin(ang);
        return {x * cosa - y * sina, x * sina + y * cosa, z};
    } 
    inline double dis(letp &p) {
        return sqrt(sqr(x - p.x) + sqr(y - p.y) + sqr(z - p.z));
    }
};

inline bool check(vector<P> &s, int n) {
    for (auto x : s) {
        int cnt = 0;
        for (auto y : s) { 
            if (x == y) continue;
            double d = x.dis(y);
            if (z(d)) return false;
            if (z(d - 1.0)) ++cnt;
        }
        if (cnt != n) return false;
    }
    return true;
}

inline vector<P> random_rotate(vector<P> &s) {
    vector<P> res = s;
    double ang = 360.0 * rand() / RAND_MAX;
    for (auto &x : res) x = x.rotx(ang); 
    ang = 360.0 * rand() / RAND_MAX;
    for (auto &x : res) x = x.roty(ang); 
    ang = 360.0 * rand() / RAND_MAX;
    for (auto &x : res) x = x.rotz(ang); 
    return res;
}

vector<P> ans[11];

int main() {
    ans[1].pb({0, 0, 0}); ans[1].pb({1, 0, 0});
    ans[2] = ans[1]; ans[2].pb({0.5, sqrt(3) / 2, 0});
    ans[3] = ans[2]; ans[3].pb({0.5, sqrt(3) / 6, sqrt(6) / 3});
    ans[4].pb({0, 0, 0}); ans[4].pb({1, 0, 0}); 
    ans[4].pb({0, 1, 0}); ans[4].pb({1, 1, 0});
    ans[4].pb({0.5, 0.5, sqrt(2) / 2}); ans[4].pb({0.5, 0.5, -sqrt(2) / 2});
    for (int i = 5; i <= 10; ++i) {
        int x = 1, nw = 100;
        for (int j = 1; j < i; ++j)
            if (ans[j].size() * ans[i - j].size() < nw) {
                nw = ans[j].size() * ans[i - j].size(); x = j;
            }
        vector<P> p;
        while (true) {
            ans[i].clear();
            p = random_rotate(ans[x]);
            for (auto a : p)
                for (auto b : ans[i - x]) ans[i].pb(a + b);
            if (check(ans[i], i)) break;
        }
    }

    int n = rd();
    printf("%d\n", (int)ans[n].size());
    for (auto x : ans[n]) printf("%.10lf %.10lf %.10lf\n", x.x, x.y, x.z);
    return 0;
}

J - Let's Play Jigsaw Puzzles!

一个 \(m\times m\) 的矩阵填入 \(1\sim m^2\) ，给定每个权值的四邻接情况，恢复矩阵。

确定左上角之后 BFS 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 1007
#define mp make_pair

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int adj[N * N][4], ans[N][N];

queue<pii> q;

int main() {
	int n = rd();
	for (int i = 1, m = n * n; i <= m; ++i) 
		for (int j = 0; j < 4; ++j) adj[i][j] = rd();
	for (int i = 1, m = n * n; i <= m; ++i)
		if (adj[i][0] == -1 && adj[i][2] == -1) {
			ans[1][1] = i; q.push(mp(1, 1)); break;
		}
	while (!q.empty()) {
		auto [x, y] = q.front(); q.pop();
		int num = ans[x][y];
		for (int j = 0; j < 4; ++j)
			if (adj[num][j] != -1) {
				int tx = x + dx[j];
				int ty = y + dy[j];
				if (ans[tx][ty]) continue;
				ans[tx][ty] = adj[num][j]; 
				q.push(mp(tx, ty));
			} 
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d", ans[i][1]);
		for (int j = 2; j <= n; ++j) printf(" %d", ans[i][j]);
		puts("");
	}
	return 0;	
}

K - Browser Games

给定 \(n\) 个串 \(S_1,S_2,\dots,S_n\) ，对每个 \(k=1,2,\dots,n\) ，问最少选多少个字符串 \(|\{T_i\}|\) ，使得：

  • 对任意 \(1\le i\le k\) ，存在一个 \(T_j\) ，使得 \(T_j\) 是 \(S_i\) 的前缀
  • 对任意 \(k< i\le n\) ，不存在一个 \(T_j\) ，使得 \(T_j\) 是 \(S_i\) 的前缀

考虑把 Trie 树建出来，然后倒着一个一个撤销。初始答案就是根结点儿子个数。

每次撤销一个串，路径上的节点以后就都不能选了，且路径上所有点的其他分支都得被覆盖过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 50007
#define mp make_pair

inline int trans(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    if (c == '.') return 26;
    return 27;
}

int tot = 1;

struct node{bool tag, vis; int fa, tr[28];} c[3000007];

int Ans;

int insert(int *s, int len) {
    int nw = 1;
    for (int i = 1; i <= len; nw = c[nw].tr[s[i++]])
        if (!c[nw].tr[s[i]]) c[c[nw].tr[s[i]] = ++tot].fa = nw;
    return nw;
}

void del(int nw, int *s, int len) {
    while (nw != 1) {
        if (c[nw].tag) {c[nw].tag = false; --Ans;} // 若原本有标记则要撤销
        if (!c[nw].vis) { // 若第一次经过该点，则对所有其他儿子打标记
            c[nw].vis = true;
            for (int i = 0; i < 28; ++i)
                if (c[nw].tr[i] && !c[c[nw].tr[i]].vis) {++Ans; c[c[nw].tr[i]].tag = true;}
        }
        --len;
        nw = c[nw].fa;
    }
}

char S[N];

int s[N][60], pos[N];

int len[N], ans[N];

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        scanf("%s", S + 1);
        len[i] = strlen(S + 1);
        for (int j = 1; j <= len[i]; ++j) s[i][j] = trans(S[j]);
        pos[i] = insert(s[i], len[i]);
    }
    for (int i = 0; i < 28; ++i)
        if (c[1].tr[i]) {++Ans; c[c[1].tr[i]].tag = true;}
    ans[n] = Ans;
    for (int i = n; i; --i) {
        del(pos[i], s[i], len[i]);
        ans[i - 1] = Ans;
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;   
}

M - Tower of the Sorcerer

上取整整除分块 + 不可重 ST 表。赛后 1min 过了。