HDU-4777 Rabbit Kingdom（区间更新求和）

题目大意：给一个n个整数的数列，q次询问，每次询问区间[l,r]中与区间中其它数互质的数的个数.。

题目分析：离线处理，这里以询问区间的左端点从小到大的顺序为例。为了叙述方便，用f(l,r)表示区间[l,r]中与区间中其它数互质的数的个数.。每次用线段树或树状数组维护以 a(i)(1<=i<=n) 为左端点的所有区间的 f 值的前缀和。左端点从1~n，每变化一次，便做一次更新操作。这样，f(l,r)=sum(l)-sum(r+1)。对于数列中的每个元素a(i)，预处理出其左边第一个不与他互质的数li(i)，同样预处理出ri(i)。当左端点由a(i)变为a(i+1)时，要将区间[i+1,ri(i)-1]的 f 值都减1，同理，如果存在j>i并且li(j)=i，那么就要将区间[i+1,ri(j)-1]的 f 值都加1。

代码如下（用树状数组维护）：

# include<iostream>

# include<cstdio>

# include<map>

# include<set>

# include<vector>

# include<cstring>

# include<algorithm>

using namespace std;

const int N=200000;

struct Node

{

	int id,l,r;

};

Node nde[N+1];

int a[N+1];

int li[N+1];

int ri[N+1];

int mark[N+1];

int ans[N+1];

int sum[N+1];

vector<int>edge[N+1];

vector<int>v[N+1];

int n;

bool comp(const Node &a,const Node &b)

{

	return a.l<b.l;

}

void init()

{

	for(int i=2;i<=N;++i)

		for(int j=i;j<=N;j+=i)

			v[j].push_back(i);

}

int lowbit(int x)

{

	return x&(-x);

}

void add(int x,int val)

{

	while(x>=1){

		sum[x]+=val;

		x-=lowbit(x);

	}

}

int getSum(int x)

{

	int res=0;

	while(x<=n){

		res+=sum[x];

		x+=lowbit(x);

	}

	return res;

}

int main()

{

	init();

	int m;

	while(scanf("%d%d",&n,&m)&&(n+m))

	{

		for(int i=1;i<=n;++i){

			scanf("%d",a+i);

			edge[i].clear();

		}

		memset(mark,0,sizeof(mark));

		for(int i=1;i<=n;++i){

			li[i]=0;

			for(int j=0;j<v[a[i]].size();++j){

				li[i]=max(li[i],mark[v[a[i]][j]]);

				mark[v[a[i]][j]]=i;

			}

		}

		memset(mark,1,sizeof(mark));

		for(int i=n;i>=1;--i){

			ri[i]=n+1;

			for(int j=0;j<v[a[i]].size();++j){

				ri[i]=min(ri[i],mark[v[a[i]][j]]);

				mark[v[a[i]][j]]=i;

			}

		}

		memset(sum,0,sizeof(sum));

		for(int i=1;i<=n;++i){

			if(li[i]){

				edge[li[i]].push_back(i);

			}else{

				add(i,1);

				if(ri[i]<=n) add(ri[i],-1);

			}

		}

		for(int i=1;i<=m;++i){

			scanf("%d%d",&nde[i].l,&nde[i].r);

			nde[i].id=i;

		}

		int id=1;

		sort(nde+1,nde+m+1,comp);

		for(int i=1;i<=n&&id<=m;++i){

			while(nde[id].l==i){

				ans[nde[id].id]=(getSum(nde[id].l)-getSum(nde[id].r+1));

				++id;

			}

			add(i,-1);

			if(ri[i]<=n) add(ri[i],1);

			for(int j=0;j<edge[i].size();++j){

				int x=edge[i][j];

				add(x,1);

				if(ri[x]<=n) add(ri[x],-1);

			}

		}

		for(int i=1;i<=m;++i) printf("%d\n",ans[i]);

	}

	return 0;

}

巴特西

HDU-4777 Rabbit Kingdom（区间更新求和）

最新文章

热门文章