题目：CF755D
洛谷
Codeforces

这是一道数据结构大水题。

打模拟赛的时候把这道题放到了 T4，做完 T1 就看这道题有思路就写出来了。

首先考虑如何暴力模拟计算答案，当每链接一条边 $(x, x + k)$ 时，被分割的区域数 $s$ 会增加 $u + 1$，其中 $u$ 是与这条边在正多边形中有交叉的线段数量。而题目保证边数（即点数）$n$ 与 $k$ 互质，说明在每一个点都被连接后才会回到初始节点，共链接 $n$ 条边。我们把每一次的连边存下来，在新的一次连边时判断有多少条边与此时的连边相交。暴力复杂度 $O(n^2)$，期望得分 $0$ 分。

考虑优化。时间复杂度的瓶颈是计算重复的边。想出了一个很奇怪的判断方法，用两颗树状数组储存每条边的左节点和右节点，由于 $k$ 是确认的，所以只用一个节点的位置就可以求出另一个节点。对于左节点与当前边 $(l, r)$ 相交时，统计左节点在区间 $[r - k + 1, r - 1]$ 的线段数量，右节点则统计 $[l + 1, l + k - 1]$。如果节点越界的话特判一下 $\pm n$ 即可。使用树状数组的话复杂度 $O(n \log n)$。

最开始要注意把 $k$ 赋值为 $\min(k, n - 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
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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define int long long
using namespace std;
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch > '9' || ch < '0') {
		if(ch == '-') f = -1; ch = getchar();
	}
	while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch - 48), ch = getchar();
	return x * f;
}
const int N = 2e6 + 10;

typedef pair<int, int> pii;
int n, k;
priority_queue <int> E[N];
vector <pii> V;
namespace Tree {
	int vall[N], valr[N];
	int lowbit(int x) {
		return x & -x;
	}
	int queryl(int x) {
		int ans = 0;
		while(x) {
			ans += vall[x];
			x -= lowbit(x);
		}
		return ans;
	}
	void modifyl(int x, int y) {
		while(x <= n) {
			vall[x] += y;
			x += lowbit(x);
		}
	}
	int queryr(int x) {
		int ans = 0;
		while(x) {
			ans += valr[x];
			x -= lowbit(x);
		}
		return ans;
	}
	void modifyr(int x, int y) {
		while(x <= n) {
			valr[x] += y;
			x += lowbit(x);
		}
	}
}
void solve();
signed main() {
	int T; T = 1;
	while(T--) solve();
	return 0;
}
using namespace Tree;
int calc1(int l, int r) {
	//[l, r] 闭区间
    //这里可能向左越界
	if(l >= 1 && r <= n) return queryl(r) - queryl(l - 1);
	else return queryl(n) - queryl(l - 1 + n) + queryl(r);
}
int calc2(int l, int r) {
    //这里可能向右越界
	if(l >= 1 && r <= n) return queryr(r) - queryr(l - 1);
	else return queryr(n) - queryr(l - 1) + queryr(r - n);
}
int SegmentJudge(int l, int r) {
	int ans = 0;
	if(l > r) swap(l, r);
	ans += calc1(r - k + 1, r - 1);
	ans += calc2(l + 1, l + k - 1);
	return ans;
}
void solve() {
	n = read(), k = read();
	k = min(k, n - k);
	int x = 1;
	int ans = 1;
	for(int i = 1; i <= n; i++) {
		int y = (x + k > n ? x + k - n: x + k);
		// x -> x + k
		ans += SegmentJudge(x, y) + 1;
		cout << ans << " ";
		Tree::modifyl(x, 1);
		Tree::modifyr(y, 1);
		x = y;
	}
	cout << endl;
	return;
}