D. PolandBall and Polygon BIT + 欧拉公式

http://codeforces.com/contest/755/problem/D

// 我也觉得非平面图不能用欧拉公式，但是也能过，不知道为什么。求大佬留言。

这题其实就是平面图，因为它有很多个交点。中途的交点使得图的阶数变大了

所以我的思路就是求出V、E、然后解出F。V - E + F = 2

其中每连接一条边，增加的交点就是其路径上的点被多少次经过。（不包括自己端点）

这个可以用BIT维护下。

然后当k > n - k的时候，需要反向一下，因为这样其实就相当于镜面对称一下而已，不然会wa的。

比如5 3 的时候，会翻车

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e6 + ;

LL c[maxn];

int n, k;

int lowbit(int x) {

    return x & (-x);

}

void add(int pos, int val) {

    while (pos <= n) {

        c[pos] += val;

        pos += lowbit(pos);

    }

}

LL query(int pos) {

    LL ans = ;

    while (pos > ) {

        ans += c[pos];

        pos -= lowbit(pos);

    }

    return ans;

}

void work() {

    scanf("%d%d", &n, &k);

    int be = ;

    LL e = n;

    LL v = n;

    k = min(k, n - k); //这个是必须的，试试5 3 就知道

    for (int i = ; i <= n; ++i) {

        int from = be;

        int to = be + k;

        if (to > n) {

            to -= n;

            LL addv = query(to - );

            if (from != n) {

                addv += query(n) - query(from);

            }

            e += addv;

            e += addv + ;

            v += addv;

            printf("%I64d ",  - v + e - );

            add(from, );

            add(to, );

            be = to;

        } else {

            LL addv = query(to - ) - query(from);

            e += addv;

            e += addv + ;

            v += addv;

            printf("%I64d ",  - v + e - );

            add(from, );

            add(to, );

            be = to;

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}