题目链接：http://codeforces.com/contest/755/problem/D
题意：一个n边形，从1号点开始，每次走到x+k的位置如果x+k>n则到x+k-n的位置，问每次留下来的路径把这个多边形划分成了几个部分。
很明显只要求x到x+k位置之间的点有几个入度就行了，而且只要求小区间内除去两点剩下的点的入度即可。
不需要考虑x或x+k点到该点的入度因为更本不可能从x或x+k到该点。
所以可以将k值稍微优化一下全都统一到k<n/2，这不影响结果因为假设5个点1到3，k=2。5个点1到4，k=3。但是点的位置可以任意调的，
只要是四边形就行所以都是一样的。
这样就方便用线段树或者用树状数组单点更改与区间求和。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
const int M = 1e6 + 10;
struct TnT {
int l , r , sum;
}T[M << 2];
void build(int l , int r , int p) {
int mid = (l + r) >> 1;
T[p].l = l , T[p].r = r , T[p].sum = 0;
if(l == r) {
return ;
}
build(l , mid , p << 1);
build(mid + 1 , r , (p << 1) | 1);
}
void updata(int p , int pos) {
int mid = (T[p].l + T[p].r) >> 1;
if(T[p].l == T[p].r && T[p].l == pos) {
T[p].sum++;
return ;
}
if(mid < pos) {
updata((p << 1) | 1 , pos);
}
else {
updata(p << 1 , pos);
}
T[p].sum = T[p << 1].sum + T[(p << 1) | 1].sum;
}
int query(int l , int r , int p) {
int mid = (T[p].l + T[p].r) >> 1;
if(T[p].l == l && T[p].r == r) {
return T[p].sum;
}
if(mid < l) {
return query(l , r , (p << 1) | 1);
}
else if(mid >= r) {
return query(l , r , p << 1);
}
else {
return query(l , mid , p << 1) + query(mid + 1 , r , (p << 1) | 1);
}
}
int main() {
int n , k , sta = 1 , end;
cin >> n >> k;
build(1 , n , 1);
ll ans = 1;
if(k > (n/2))
k = n - k;
for(int i = 1 ; i <= n ; i++) {
end = sta + k;
if(end > n) {
end -= n;
}
if(sta < end) {
ans = ans + 1 + query(min(sta , end) , max(sta , end) , 1) - query(sta , sta , 1) - query(end , end , 1);
}
else {
ans = ans + 1 + query(1 , n , 1) - query(end , sta , 1);
}
updata(1 , sta);
updata(1 , end);
cout << ans << ' ';
sta = end;
}
return 0;
}