离线树状数组【洛谷P1972】

84 阅读 0 评论 56 点赞

我是靠谱客的博主飞快学姐，最近开发中收集的这篇文章主要介绍离线树状数组【洛谷P1972】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门：https://www.luogu.org/problemnew/show/P1972

离线的题目，并且是求区间问题。我们就离线树状数组吧。

线段树也是可以的，这题莫队70分，分块是和莫队一样的，就没写，估计也就70分。

我们来分析一下这个题目吧。

询问一段区间的种类数，并且没有更新操作。我们就分析一下怎么离线。

...

(五分钟后)

好了，经过分析可知，我们按询问区间的右端点排序，这样，所有询问，我们可以for一遍处理出该区间的信息。

(因为对于所有询问，每一个询问都是从左往右的嘛)。然后在每一个询问区间里面，我们都保留尽量靠右的数字，因为左边出现过的在右边也出现了，我们就把左边出现的直接舍掉就可以了。

然后我们保留一下这个询问区间的答案就完事了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int sump[maxn],psum[maxn];
int a[maxn];
int vis[maxn];
int ans[maxn];
int n;
struct node
{
	int l;
	int r;
	int id;	
}q[maxn];
bool cmp(node a,node b)
{
	return a.r<b.r;
}
void add(int p,int x)
{
	for(int i=p;i<=n;i+=(i & -i))
	{
		sump[i] += x;
		psum[i] += x*p;
	}
} 
void add_range(int l,int r,int x)
{
	add(l,x);
	add(r+1,-x);
}
int query(int p)
{
	int ans = 0;
	for(int i=p;i;i-=(i & -i))
	{
		ans += sump[i]*(p+1)-psum[i];
	}
	return ans;
}
int query_range(int l,int r)
{
	return query(r)-query(l-1);
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		memset(vis,0,sizeof(vis));
		memset(sump,0,sizeof(sump));
		memset(psum,0,sizeof(psum));
		memset(ans,0,sizeof(ans));
		int k;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",a+i);
		}
		for(int i=1;i<=k;i++)
		{
			scanf("%d%d",&q[i].l,&q[i].r);
			q[i].id = i;
		}
		sort(q+1,q+1+k,cmp);
		int l = 1;
		for(int i=1;i<=k;i++)
		{
			for(int j=l;j<=q[i].r;j++)
			{
				if(!vis[a[j]])
				{
					vis[a[j]] = j;
					add_range(j,j,1);
				}
				else
				{
					add_range(vis[a[j]],vis[a[j]],-1);
					add_range(j,j,1);
					vis[a[j]] = j;
				}
			}
			l = q[i].r+1; 
			ans[q[i].id] = query_range(q[i].l,q[i].r);
		}
		for(int i=1;i<=k;i++)
		{
			printf("%dn",ans[i]);
		}
	}
	return 0;
}

下面是70分的莫队

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int cnt[maxn];
int a[maxn];
int pos[maxn];
int ans[maxn];
int Ans = 0;
struct node
{
	int l;
	int r;
	int id;
}q[maxn];
bool cmp(node a,node b)
{
	if(pos[a.l]==pos[b.l])
	{
		return a.r<b.r;
	}
	return pos[a.l]<pos[b.l];
}
void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1)
	{
		Ans++;
	}
} 
void del(int x)
{
	cnt[a[x]]--;
	if(cnt[a[x]]==0)
	{
		Ans--;
	}
}

int main()
{
    int n,m;
	scanf("%d",&n);
	int block = sqrt(n);
	for(register int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
	}
	scanf("%d",&m);
	for(register int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id = i;
	}
	sort(q+1,q+1+m,cmp);
	int L = 0;
	int R = 0;
	for(register int i=1;i<=m;i++)
	{
		while(q[i].l<L)
		{
			L--;
			add(L);
		}
		while(q[i].l>L)
		{
			del(L);
			L++;
		}
		while(q[i].r<R)
		{
			del(R);
			R--;
		}
		while(q[i].r>R)
		{
			R++;
			add(R);
		}
		ans[q[i].id] = Ans;
	}
	for(register int i=1;i<=m;i++)
	{
		printf("%dn",ans[i]);
	}
	return 0;
}