8VC Venture Cup 2017 – Elimination Round D. PolandBall and Polygon 树状数组+几何

Source

8VC Venture Cup 2017 - Elimination Round

My Solution

题意：给出一个凸n边形，然后给一个k，存在gcd(n, k) == 1,然后从顶点x = 1开始，在x 与 y = x + k;//(while(y > n) y -= n;) 间画一条线，然后 x = y，继续 y = x + k 画线，

没每画一条线图形中存在的中平面块数。

树状数组+几何

用ans表示画线前的平面块数，画一条xy线，则多出的平面块数为 线xy穿过的线的个数+1，

观察可以发现，xy穿过的线段的个数等价于 顺时针方向 x与y之间点的权值和，(每个点的权值为点所在的线段的条数)，

然后考虑到 k > n / 2时，这个结论就不行了，又由于k 与 n - k对称，所以令 k = n - k即可，

然后注意 ans 要用long long 才行，不然会溢出。

复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

LL Tree[maxn + 8];
inline LL lowbit(LL x)
{
    return (x & -x);
}
inline void add(LL x, LL val)
{
    for(LL i = x; i <= maxn; i += lowbit(i)) Tree[i] += val; } inline LL get(LL x) { LL sum = 0; for(LL i = x; i; i -= lowbit(i)) sum += Tree[i]; return (sum); } int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL n, k, ans = 2, x, y; cin >> n >> k;
    cout << ans; if(k > n/2) k = n - k;

    add(1, 1);add((1 + k), 1);
    x = 1 + k;
    for(int i = 2; i <= n; i++){ y = x + k; while(y > n) y -= n;
        if(y > x){
            ans += get(y-1) - get(x) + 1;
        }
        else{
            ans += get(y-1) + get(n) - get(x) + 1;
        }
        add(x, 1);
        add(y, 1);
        x = y;
        cout << " " << ans;
    }


    #ifdef LOCAL
    memset(Tree, 0, sizeof Tree);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx