题解归档 - cf755D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf755D
• 本地来源：problems/cf755D/idea.md
• 题目链接：https://codeforces.com/contest/755/problem/D
• 原始标题：755D PolandBall and Polygon

思路

755D PolandBall and Polygon

题意

凸 (n) 边形顶点顺时针编号 (1..n)，(\gcd(n,k)=1)。从顶点 (1) 出发，每次从当前顶点 (x) 连向顺时针第 (k) 个顶点，重复 (n) 次。每次画完一条线段后，输出多边形内部被已有线段与边界划分的区域数。

关键观察

• 初始只有多边形内部 1 个区域；每新增一条弦，区域数增加「与已有弦在内部相交的条数 + 1」。
• 圆上两弦 ((a,b)) 与 ((c,d)) 相交 ⟺ 四个端点在圆周上交错（一端在顺时针弧 ((a,b)) 内、另一端在外）。
• 令 (k\leftarrow\min(k,n-k))，则每次跳跃弧长 (\le n/2)，相交判定可统一为：新弦 ((now,nex)) 与旧弦相交 ⟺ 旧弦恰有一个端点落在顺时针开弧 ((now,nex)) 上。

算法（树状数组）

维护 BIT：在顶点 (v) 上记录「已有弦端点落在 (v) 的次数」。

每步 (i=1..n)：

1. (nex=now+k)，若 (nex>n) 则 (nex-=n)。
2. (tmp) = 开弧 ((now,nex)) 上 BIT 前缀和（不跨 (n)：([now+1,nex-1])；跨 (n)：([now+1,n]+[1,nex-1])）。
3. (ans+=tmp+1)，输出 (ans)。
4. change(now,1); change(nex,1); now=nex。

样例

• (n=5,k=2)：(2\ 3\ 5\ 8\ 11)
• (n=10,k=3)：(2\ 3\ 4\ 6\ 9\ 12\ 16\ 21\ 26\ 31)

复杂度

• 时间：(O(n\log n))
• 空间：(O(n))

代码

来源：problems/cf755D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:57:33
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e6;
ll h[maxn+5],n,k,i,now,from,to,ans;
ll sum(ll x){
    ll sc=0;
    while(x>0){
        sc+=h[x];
        x-=x&-x;
    }
    return sc;
}
ll qry(ll a,ll b){
    if(a>b) return 0;
    return sum(b)-sum(a-1);
}
void change(ll x){
    for(;x<=n;x+=x&-x) h[x]++;
}
int main(){
    scanf("%lld%lld",&n,&k);
    k=min(k,n-k);
    now=1;
    ans=1;
    for(i=1;i<=n;i++){
        ans++;
        from=now-k+1;
        to=now+k-1;
        if(from<1) ans+=qry(from+n,n)+qry(1,to);
        else if(to>n) ans+=qry(from,n)+qry(1,to-n);
        else ans+=qry(from,to);
        change(now);
        now+=k;
        if(now>n) now-=n;
        if(i>1) printf(" ");
        printf("%lld",ans);
    }
    printf("\n");
    return 0;
}