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

每次新画一条对角线的时候，考虑其跨越了几条原有的对角线。

可以用树状数组区间修改点查询来维护多边形的顶点。答案每次增加 新对角线的左端点在多少个区间内+右端点在多少个区间内+1，每次把新画的对角线所覆盖的较小区间内部的每个点加1即可。注意，一定要是较小的区间，因为这样才能保证其左右端点不同时在区间内，不会重复统计。

#include
     
      #include
      
       using namespace std;typedef long long ll;int n,m;ll ans=1ll;int d[1000010];int Query(int p){int res=0; for(;p;p-=(p&(-p))) res+=d[p]; return res;}void add(int p,int v){for(;p<=n;p+=(p&(-p))) d[p]+=v;}void Update(int l,int r){	if(l
       
        n/2)	  m=n-m;	int U=1;	for(int i=1;i<=n;++i)	  {	  	int pre=U;	  	U+=m;	  	if(U>n)	  	  U-=n;	  	ans+=((ll)Query(pre));		ans+=((ll)Query(U)+1ll);	  	Update(pre,U);	  	printf("%I64d%c",ans,i==n ? '\n' : ' ');	  }	return 0;}