CF 755D - PolandBall and Polygon 题解

您已获得最佳的阅读体验！

题目地址：CF 755D

题目难度：提高+/省选-

给出一个边形，和距离。第一次连接和，第二次连接和，依次进行次，每次结束后输出边形被分割成了几个区域。

，保证和互质。

今天模拟赛 T2 原题，赛时多测卡线段树加上多测没清空喜爆零。同机房大佬 Brilliant11001 用惊天地泣鬼神纯数学做法 A 的，在此表示深深膜拜 %%%。

为了取模方便，本文是 0-index 的。

首先，根据互质关系可得，本题无需考虑重边的情况。因为在 0-index 下，题目可以看作是向连边，因此只有满足时才可能出现重边，这要求，而（互质），所以，且是的倍数时才会出现重边，对应次操作之后。本题中只考虑前次操作，因而不存在重边问题。

手搓可以发现第一个规律：具有对称性，即和作为步长时的答案是相同的，只是连边顺序相反而已。

接着研究，发现第二个规律——连边带来的贡献是当前边与已有边的相交次数加一。我们的核心任务就是维护当前边会与多少已连接的边相交。

假设当前待连的边是。仔细观察样例可发现，其实相交线段个数就是到（注意顺序，不是到）间内每个点的度数之和（多边形本身的边不计入度数）。因此对于每次操作，我们获得区间内所有点已经连出边的总数即可，注意特判右端点是否越过节点。贡献的产生如下图：

线段树的常数还是很大的，建议使用树状数组（或者上边大佬的数学做法）。

#include <bits/stdc++.h>
#define N 1000010
using namespace std;

typedef long long ll;

struct SegmentTree {
#define le(x) (x << 1)
#define ri(x) (x << 1 | 1)
#define leftSubtree(x) (tree[le(x)])
#define rightSubtree(x) (tree[ri(x)])
    int l, r, size;
    ll sum;
} tree[N << 2];

void pushup(int idx) {
    tree[idx].sum = leftSubtree(idx).sum + rightSubtree(idx).sum;
}

void build(int idx, int l, int r) {
    tree[idx].l = l, tree[idx].r = r;
    tree[idx].size = r - l + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(le(idx), l, mid);
    build(ri(idx), mid + 1, r);
    pushup(idx);
}

void modify(int idx, int uid) {
    if (tree[idx].size == 1 && tree[idx].l == uid) {
        tree[idx].sum++;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (uid <= mid) modify(le(idx), uid);
    if (uid > mid) modify(ri(idx), uid);
    pushup(idx);
}

ll query(int idx, int l, int r) {
    if (l <= tree[idx].l && tree[idx].r <= r) return tree[idx].sum;
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    ll ret = 0;
    if (l <= mid) ret += query(le(idx), l, r);
    if (r > mid) ret += query(ri(idx), l, r);
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, k;
    cin >> n >> k;
    k = min(k, n - k);
    build(1, 0, n - 1);
    int pos = 0;
    ll section = 1;
    for (int i = 1; i <= n; i++) {
        int L = (pos + 1) % n, R = (pos + k - 1 + n) % n; // 左右端点
        ll sum = R < L ? query(1, 0, R) + query(1, L, n - 1) : query(1, L, R); // 获得区间内每个点连出去多少条边，注意判断是否跨过节点 0
        modify(1, pos); // 为当前的线段端点累加 1
        modify(1, (pos + k) % n);
        section += sum + 1; // 图形总数
        pos = (pos + k) % n; // 跳到下一个位置
        cout << section << ' ';
    }

    return 0;
}

AC 记录