Code Forces 755 D PolandBall and Polygon(思维+树状数组)

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <vector>#include <map>#include <iomanip>using namespace std;long long v[1000010];long long c[1000010];long long C(int i){	long long  temp = 0;	int index = i + 1 - (i&(-i));	while(index <= i)	{		temp+=v[index];		index++;	}	return temp;}long long SUM(int i){	long long s = 0;	while(i>0)	{		s+=c[i];		i -= (i&(-i));	}	return s;}void Update(int i,int add,int SIZE){	while(i<=SIZE)	{		c[i] += add;		i += (i&(-i));	}}int main(){	int n,k;	while(cin>>n>>k)	{		memset(v,0,sizeof(v));		k=min(k,n-k);		for(int i=1; i<=n; i++)		{			if(i == 1||i == k+1)				v[i] = 1;			else				v[i] = 0;			c[i] = C(i);		}		cout<<"2";		int index = k+1;		long long tempsum = 2;		for(int i=2; i<=n; i++)		{				if(index+k>n)				{					tempsum += SUM(n) - SUM(index);					tempsum += SUM((index+k)-n-1);					tempsum++;					Update(index,1,n);					index = (index+k)-n;					Update(index,1,n);				}				else				{					tempsum += SUM(index+k-1) - SUM(index);					tempsum++;					Update(index,1,n);					index = (index+k);					Update(index,1,n);				}			cout<<" "<<tempsum;		}		cout<<endl;	}}