首页 > 代码库 > 【树状数组】Codeforces Round #755 D. PolandBall and Polygon

【树状数组】Codeforces Round #755 D. PolandBall and Polygon

2024-09-01 08:53:34   216人阅读

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

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

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

#include<cstdio>
#include<algorithm>
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<r)
	  {
	  	if(l+1==r) return;
	  	add(l+1,1);
	  	if(r<=n) add(r,-1);
	  }
	else
	  {
	  	if(l<n)
	  	  add(l,1);
	  	add(1,1);
	  	add(r,-1);
	  }
}
int main()
{
//	freopen("d.in","r",stdin);
	scanf("%d%d",&n,&m);
	if(m>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;
}

【树状数组】Codeforces Round #755 D. PolandBall and Polygon


联系
我们