HDU - 5869 Different GCD Subarray Query —— 线段树离线处理

95 阅读 0 评论 63 点赞

我是靠谱客的博主安静电脑，最近开发中收集的这篇文章主要介绍HDU - 5869 Different GCD Subarray Query —— 线段树离线处理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

问区间L到R之间所有连续子序列的gcd共有多少种

思路：

和离线处理求区间不同的数的个数类似，先预处理出每个点向左的每个区间可以得到的gcd和最靠右的左端点，要注意的是从一个位置开始不断向左求gcd是一个值不断递减的过程（求的gcd次数越多，得到的结果就越小），所以如果有相同的值一定会连续出现，且第一次出现的一定是最靠右的。

预处理之后，将询问离线排序，用map维护每个gcd现在所在的最左端点并不断向右更新，线段树维护到询问端点之前所有可能形成的gcd的最右位置

#include <bits/stdc++.h>
using namespace std;
int n,q;
int num[100100];
map<int,int>mp;
int ans[100100];
struct node
{
	int l,r;
	int w;
};
struct node tree[100100*4];
struct qq
{
	int l,r;
	int id;
	bool operator < (const qq &a)const
	{
		return r<a.r;
	}
};
struct qq ques[100100];
struct nnode
{
	int w;
	int pos;
	nnode(int w_,int pos_)
	{
		w=w_;pos=pos_;
	}
};
vector< vector<struct nnode> >v;
void built(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	tree[i].w=0;
	if(l==r)
	return;
	int mid=(l+r)>>1;
	built(i<<1,l,mid);
	built(i<<1|1,mid+1,r);
}
void updata(int i,int x,int v)
{
	if(tree[i].l==tree[i].r)
	{
		tree[i].w+=v;
		return;
	}
	int mid=(tree[i].l+tree[i].r)>>1;
	if(x<=mid)
	updata(i<<1,x,v);
	else
	updata(i<<1|1,x,v);
	tree[i].w=tree[i<<1].w+tree[i<<1|1].w;
}
int query(int i,int l,int r)
{
	if(tree[i].l==l&&tree[i].r==r)
	{
		return tree[i].w;
	}
	int mid=(tree[i].l+tree[i].r)>>1;
	if(r<=mid)
	return query(i<<1,l,r);
	else if(l>mid)
	return query(i<<1|1,l,r);
	else
	return query(i<<1,l,mid)+query(i<<1|1,mid+1,r);
}
int main()
{
	while(scanf("%d%d",&n,&q)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&num[i]);
		}
		built(1,1,n);
		v.clear();
		v.resize(n+1);
		for(int i=1;i<=n;i++)
		{
			v[i].push_back(nnode(num[i],i));
			int x=num[i];
			for(int j=0;j<v[i-1].size();j++)
			{
				int k=__gcd(num[i],v[i-1][j].w);
				if(k!=x)
				{
					v[i].push_back(nnode(k,v[i-1][j].pos));
					x=k;
				}
			}
		}
		for(int i=1;i<=q;i++)
		{
			scanf("%d%d",&ques[i].l,&ques[i].r);
			ques[i].id=i;
		}
		sort(ques+1,ques+1+q);
		int j=1;
		mp.clear();
		for(int i=1;i<=q;i++)
		{
			while(j<=ques[i].r)
			{
				for(int k=0;k<v[j].size();k++)
				{
					if(mp[v[j][k].w]!=0)
					{
						updata(1,mp[v[j][k].w],-1);
					}
					updata(1,v[j][k].pos,1);
					mp[v[j][k].w]=v[j][k].pos;
				}
				j++;
			}
			ans[ques[i].id]=query(1,ques[i].l,ques[i].r);
		}
		for(int i=1;i<=q;i++)
		printf("%dn",ans[i]);
	}
}