Codeforce 755D(树状数组)

本文主要是介绍Codeforce 755D(树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出一个N边形，从1点开始，每次顺时针走k个点(gcd(n,k)==1)，求每次将多边形分割成多少个区域

链接：点击打开链接

代码：

#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int siz=1000005;
int n,k;
long long bit[siz];
int lowbit(int x){return x&(-x);
}
void change(int x,int y){int i;for(i=x;i<=n;i+=lowbit(i))bit[i]+=y;
}
long long sum(int x){int i;long long ans=0;for(i=x;i>0;i-=lowbit(i))ans+=bit[i];return ans;
}
int main(){long long res;int i,u,v,l,r;while(scanf("%d%d",&n,&k)!=EOF){u=v=1,res=1;memset(bit,0,sizeof(bit));for(i=1;i<=n;i++){                      //主要就是求两个点中间点少的那一部分连出去了多少点u=v,v=u+k;                          //主要麻烦在询问的区间的端点是什么if(v>n)v-=n;l=u,r=v;if(k>n/2){                          //注意k比n/2大的时候与k比n/2小的时候情况是相反的l--,r++;if(l<=0)l+=n;if(r>n)r-=n;if(l<r)res+=(sum(n)-sum(r-1)+sum(l)+1);elseres+=(sum(l)-sum(r-1)+1);}else{l++,r--;if(l>n)l-=n;if(r<=0)r+=n;if(l<=r)res+=(sum(r)-sum(l-1)+1);elseres+=(sum(n)-sum(l-1)+sum(r)+1);}printf("%I64d ",res);change(u,1);change(v,1);}printf("\n");}return 0;
}

这篇关于Codeforce 755D(树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---